ETH_Informatik/Informatik_I/Exercise_10/Task_3

Task 3: Dynamic Queue

• Task 3: Dynamic Queue
  • Input & Output
• Solution

Task 3: Dynamic Queue

Your objective is to implement your own queue class with integer values as a dynamic data structure.

A queue provides the two basic operations: enqueue and dequeue. The operation enqueue adds a new element to the back of the queue. The operation dequeue removes the first element from the queue:

A common way to implement a queue is using a linked list, as the one that was shown in the lecture. In order to be able to both enqueue and dequeue, we need to access respectively the first and last elements of the list.

Procedure: The queue declaration is already provided. Your task is to fill the missing definitions for the required functions, marked by comments // TODO in queue.cpp. Function annotations (pre- and postconditions), found along declarations in the header queue.h, explain what each function is supposed to do. You may (and probably will have to) add auxiliary non-member functions in queue.cpp in order to implement some of the functions.

A class invariant helps to detect implementation problems early. For this queue, we have the following class invariant: Either both pointers first and last are set to nullptr or both are not set to nullptr. The invariant is checked after every operation. If the invariant is not satisfied, the program exits.

Subtasks:

1. Implement the default constructor of class Queue.
2. Implement the queue operations: member functions enqueue, dequeue and is_empty.
3. Implement the member function print_reverse to print the content of a queue to std::cout in reverse order. To output the queue content (output operator), use the following format: bracket open ([) , zero or more integer numbers separated by spaces, bracket close (]). E.g., the empty queue must be output like this: [], the queue containing elements 13, 7, and 42 (from first to last): [42 7 13].

The function print_reverse must be implemented through an auxiliary function traversing the queue recursively, from a Node pointer given as argument. In particular, the implementation of print_reverse must not use loop structures. We provide implementation of function print printing the content of a queue in regular order as a reference.

Optional: Think of ways to implement print and print_reverse with loops instead of recursion (do not change your submission). In particular, try to find a way to implement print_reverse that does not make use of unbounded auxiliary storage.

Input & Output

The main function of the program initially creates an empty queue and enters an endless loop where the following operations can be executed:

• enqueue x: adds x to the end of the queue
• dequeue: removes the first element from the queue and prints it to the console.
• is_empty: prints 1 to the console if the queue is empty, otherwise 0.
• print: prints the queue (in regular order) to the console.
• print_reverse: prints the queue in reverse order to the console.
• end: quits the program

Example:

is_empty
1
enqueue 5
enqueue 7
print
[5 7]
print_reverse
[7 5]
is_empty
0
dequeue
5
dequeue
7
is_empty
1
end

Note: Invariant checking is already done outside the class, so there is no need to invoke the check_invariant() method in your code.

Solution

#include "queue.h"
#include <cassert>
#include <iostream>

/////////////////////////////////////////////////////////////////////////////
// IMPLEMENTATION
/////////////////////////////////////////////////////////////////////////////

Queue::Queue() /*TODO*/ {
  first = nullptr;
  last = nullptr;
}

void Queue::enqueue(int value) {
  Node *enqVal = new Node(value, nullptr);
  if (first == nullptr) {
    first = enqVal;
    last = enqVal;
  } else {
    last->next = enqVal;
    last = enqVal;
  }
}

int Queue::dequeue() {
  const int n = first->value;
  first = first->next;
  if (is_empty()) {
    last = nullptr;
  }
  return n;
}

bool Queue::is_empty() const {
  if (first == nullptr)
    return true;
  else
    return false;
}

void rec_print_reverse(Node *refLast, Node *last, Queue &revQueue) {
  if (refLast == last) {
    revQueue.enqueue(refLast->value);
    return;
  }
  rec_print_reverse(refLast->next, last, revQueue);
  revQueue.enqueue(refLast->value);
}

void Queue::print_reverse() const {
  Queue revQueue;
  if (first == nullptr)
    revQueue.print();
  else {
    Node *refLast = first;

    rec_print_reverse(refLast, last, revQueue);
    revQueue.print();
  }
}

// PRE: -
// POST: print the sequence of integers in nodes reachable from n,
//       in order, with one space before each integer.
void print_node(Node *n) {
  if (n != nullptr) {
    std::cout << " " << n->value;
    print_node(n->next);
  }
}

void Queue::print() const {
  std::cout << "[";
  if (first != nullptr) {
    std::cout << first->value;
    print_node(first->next);
  }
  std::cout << "]";
}

---

Made by JirR02 in Switzerland 🇨🇭