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