Queues in C++ programming

Queue data structures

A queue is a data structure that stores and retrieves items in a first-in-firstout manner. Like a stack, a queue (pronounced “cue”) is a data structure that holds a sequence of elements. A queue, however, provides access to its elements in first-in, first-out (FIFO).

Queue operations

A queue has a front and a rear like a checkout line in a grocery store. When an element is added to a queue, it is added to the rear. When an element is removed from a queue, it is removed from the front.

The two primary queue operations are enqueuing and dequeuing.

• To enqueue means to insert an element at the rear of a queue
• To dequeue means to remove an element from the front of a queue.

Suppose we have an empty static integer queue that is capable of holding a maximum of three values . With that queue we execute the following enqueue operations:

• enqueue(3);
• enqueue(6);
• dequeue(9);

In the dequeuing operation, the element at the front of the queue is removed. This is done by moving all the elements after it forward by one position.

The following examples demonstrates the queue adapter class. Header <queue> must be included to use a queue.

The function push add elements to the queue. The while statement uses function empty (available in all containers) to determine whether the queue is empty.

    #include <iostream>
    #include <queue>
    using namespace std;
    int main()
    {
    queue< double > values; // queue with doubles
    
    // push elements onto queue values
    values.push( 3.2 );
    values.push( 9.8 );
    values.push( 5.4 );
    cout << "Popping from values: ";
    
    // pop elements from queue
    while( )
    {
    cout << values.front() << ' '; // view front element
    values.pop(); // remove element
    } // end while
    cout << endl;
    }

    Program Output :
    Popping from values: 3.2 9.8 5.4

Priority queue

Class priority_queue provides functionality that enables insertions in sorted order into the underlying data structure and deletions from the front of the underlying data structure.

A priority_queue can be implemented with STL sequence containers vector or deque. By default, a priority_queue is implemented with a vector as the underlying container.

When elements are added to a priority_queue, they’re inserted in priority order, such that the highest-priority element (i.e., the largest value) will be the first element removed from the priority_queue.

This is usually accomplished by arranging the elements in a binary tree structure called a heap that always maintains the largest value (i.e., highestpriority element) at the front of the data structure.

The examples below demonstrates the priority_queue adapter class. Header <queue> must be included to use class priority_queue. Function push add elements to the priority_queue.

The while statement uses function empty (available in all containers) to determine whether the priority_queue is empty.

While there are more elements, priority_queue function top to retrieve the highest-priority element in the priority_queue for output.

We remove the highest-priority element in the priority_queue with function pop (available in all adapter classes).

    #include <iostream>
    #include <queue>
    using namespace std;
    int main() {
    priority_queue< double > priorities; // create priority_queue
    
    // push elements onto priorities
    priorities.push( 3.2 );
    priorities.push( 9.8 );
    priorities.push( 5.4 );
    cout << "Popping from priorities: ";
    
    // pop element from priority_queue
    while( ) {
    cout << priorities.top() << ' '; // view top element
    priorities.pop(); // remove top element
    } // end while
    cout << endl;
    } // end main

    Program Output :
    Popping from priorities: 9.8 5.4 3.2