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;
}
};
Implementation with linked nodes
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
Jordi Petit, Salvador Roura, Jordi Cortadella
© Universitat Politècnica de Catalunya, 2024