# Queues

## Implementation with circular buffer

The elements of the queue are stored in a circular buffer whose capacity is fixed and set at construction time. Elements are read at position r and written at position w. Both indexes are incremented one unit, wrapping around when they reach the right border.

DIBUIX. FER ANIMACIÓ

#include <cassert>
#include <vector>
using namespace std;

template <typename T>
class Queue {

/** Circular buffer. */
vector<T> v;

/** Index of the first element: position to read. */
int r;

/** Index past the last element: position to write. */
int w;

/** Number of elements in the queue. */
int n;

public:

/** Builds an empty queue with some capacity. */
Queue(int capacity=1000)
:   v(capacity),
r(0),
w(0),
n(0)
{   }

/** Returns the number of elements in the queue. */
int size () const {
return n;
}

/** Returns the capacity of the queue. */
int capacity () const {
return v.size();
}

/** Tells whether the queue is empty. */
bool empty () const {
return size() == 0;
}

/** Tells whether the queue is full. */
bool full () const {
return size() == capacity();
}

/** Inserts a new element at the end of the queue, after its current end element.
Precondition: the queue is not full.
*/
void push (const T& x) {
++n;
assert(not full());
v[w] = x;
inc(w);
}

/** Removes the first element of the queue.
Precondition: the queue is not empty.
*/
void pop () {
assert(not empty());
inc(r);
--n;
}

/** Returns the first element of the queue.
Precondition: the queue is not empty.
*/
T top () const {
assert(not empty());
return v[r];
}

private:

/** Increments x circularly. */
void inc (int& x) {
if (++x == capacity()) x = 0;
}
};


The elements of the queue are stored in a linked list. They enter the list in one end-point and leave it from the other end-point. In the code, first refers to the first node of the list and last refers to the last node of the list. Here is a snapshot for a list with elements [1,2,3,4], where 1 is the first element to be served (i.e., the one that entered first):

first           last
↓               ↓
1 ⟶ 2 ⟶ 3 ⟶ 4 ─┤


In the case of an empty queue, both first and last are null. In the case of a queue with a single element, both point to the same node.

#include <cassert>
using namespace std;

template <typename T>
class Queue {

/** A Node stores an element and a pointer down to the next node in the queue. */
struct Node {
T elem;
Node* next;
};

/** Pointer to the first node of the queue. Null if the queue is empty. */
Node* first;

/** Pointer to the last node of the queue. Null if the queue is empty. */
Node* last;

/** Number of elements in the queue. */
int n;

public:

/** Builds an empty queue. */
Queue ()
:   first(nullptr),
last(nullptr),
n(0)
{   }

/** Copy constructor. */
Queue (const Queue& q) {
copy(q);
}

/** Assigment operator. */
Queue& operator= (const Queue& q) {
if (&q != this) {
free();
copy(q);
}
return *this;
}

/** Destructor. */
~Queue () {
free();
}

/** Returns the number of elements in the queue. */
int size () const {
return n;
}

/** Tells whether the queue is empty. */
bool empty () const {
return size() == 0;
}

/** Inserts a new element at the last of the queue, after its current last element. */
void push (const T& x) {
Node* p = new Node {x, nullptr};
if (n++ == 0) first = last = p;
else last = last->next = p;
}

/** Removes the first element of the queue.
Precondition: the queue is not empty.
*/
void pop () {
assert(not empty());
Node* old = first;
first = first->next;
delete old;
if (--n == 0) last = nullptr;
}

/** Returns the first element of the queue.
Precondition: the queue is not empty.
*/
T top () const {
assert(not empty());
return first->elem;
}

private:

/** Copies the queue q. */
void copy (const Queue& q) {
n = q.n;
if (n == 0) {
first = last = nullptr;
} else {
Node* p1 = q.first;
Node* p2 = first = new Node {p1->elem};
while (p1->next) {
p1 = p1->next;
p2 = p2->next = new Node {p1->elem};
}
p2->next = nullptr;
last = p2;
}   }

/** Frees the linked list of nodes in the queue. */
void free () {
Node* p = first;
while (p) {
Node* old = p;
p = p->next;
delete old;
}   }

};   Lliçons.jutge.org