Stacks and Queues for app.codility.com/programmers Explained in C++

Category of Article : Technology | Computers and Software | Algorithms

By: Chrysanthus Date Published: 4 Jul 2025

A data structure is like an array. However, its size can grow or shrink, unlike the size of an array, which can neither grow nor shrink. A typical data structure also has attributes (associated data variables) and methods (associated functions). In this tutorial (lesson), is described two data structures used for storage of elements. In C++, the two data structures of interest here, are called, the stack and the queue container adapters. Both structures have the push() and pop() methods. The push() method behaves in the same way for both structures, but the pop() method behaves differently by acting at opposite ends of the data structures.

Stack

The stack container adapter (or stack for short), is a data structure in which the insertion of a new element takes place at the top, and the deletion (removal) of an element, also takes place from the top. The idea of the stack can be illustrated by plates stacked on top of one another. Each new plate is placed on top of the stack of plates (operation push), and plates can only be taken off the top of the stack (operation pop). This is a Last-In-First-Out (LIFO) data structure.

Use of push() and pop() methods for the Stack

The following program pushes the list of integers,

4, 8, 6, 3

one-by-one onto a stack, and then pops them out one-by-one from the top of the stack. The stack begins with the number 4 and then ends with the number 3. So, in the popping operations, 3 will be sent out first. The program is:

    #include <iostream>
    #include <stack>
    using namespace std;

    int main(int argc, char **argv)
    {
        stack<int> stk;

        stk.push(4); stk.push(8); stk.push(6); stk.push(3);
        
        int int1 = stk.top(); stk.pop();
        int int2 = stk.top(); stk.pop();
        int int3 = stk.top(); stk.pop();
        int int4 = stk.top(); stk.pop();
        
        cout << int1 << ", " << int2 << ", " << int3 << ", " << int4 << endl;

        return 0;
    }

The output is:

3, 6, 8, 4

in reverse order, as expected, since it is last-in-first-out. The top() method copies out the last (top) element, while the pop() method removes the last (top) element and throws it away. pop() returns void. push() also returns void. Note the use of the dot operator, between the name of the stack, stk and the method, push() or top() or pop().

Note as well: The push() or top() or pop() method takes O(1) time. The sequence of operations for the whole list takes O(n) time, with pushing or with popping.

Queue

The queue container adapter (or queue for short), is a data structure in which a new element is inserted at the back, but an old element is removed from the front, in order. The idea of the queue can be illustrated by a line of customers at a grocery store. New people join the back of the queue (push operation) and the next person to be served, is the one in front (pop operation), of the line (queue). After serving, he/she goes away. This is a First-In-First-Out (FIFO) data structure.

Use of push() and front() methods for the Queue

The following program pushes the list of integers,

4, 8, 6, 3

one-by-one into a queue from the back, and then pops (fronts) them out one-by-one from the front of the queue. The queue begins with the number 4 and then ends with the number 3. So, in the popping (fronting) operations, 4 will be sent out first. The program is:

    #include <iostream>
    #include <queue>
    using namespace std;

    int main(int argc, char **argv)
    {
        queue<int> qu;

        qu.push(4); qu.push(8); qu.push(6); qu.push(3);
        
        int int1 = qu.front(); qu.pop();
        int int2 = qu.front(); qu.pop();
        int int3 = qu.front(); qu.pop();
        int int4 = qu.front(); qu.pop();
        
        cout << int1 << ", " << int2 << ", " << int3 << ", " << int4 << endl;

        return 0;
    }

The output is:

4, 8, 6, 3

in same order, as expected, since it is first-in-first-out. The front() method copies out the first (top) element, while the pop() method removes the first (front) element and throws it. pop() returns void. push() also returns void. Note the use of the dot operator, between the name of the queue, qu and the method, push() or front() or pop().

Note as well: The push() or front() or pop() method takes O(1) time. The sequence of operations for the whole list takes O(n) time, with pushing or with popping.

The size() method for the Stack and the Queue

A stack or a queue object, has the size() method. This returns the length of the stack or queue object. The following program illustrates this:

    #include <iostream>
    #include <stack>
    #include <queue>
    using namespace std;

    int main(int argc, char **argv)
    {
        stack<int> stk;
        stk.push(4); stk.push(8); stk.push(6); stk.push(3);
    
        queue<int> qu;
        qu.push(4); qu.push(8); qu.push(6); qu.push(3);
        
        cout << "The size of the stack is: " << stk.size() << " and the size of the queue is: " << qu.size() << endl;

        return 0;
    }

The output is:

The size of the stack is: 4 and the size of the queue is: 4

Conclusion

A data structure is like an array. However, its size can grow or shrink, unlike the size of an array, which can neither grow nor shrink. A typical data structure also has properties (associated data variables) and methods (associated functions). The stack is a Last-In-First-Out data structure. The queue is a First-In-First-Out data structure.

The rest of the 17 lessons, with explanation of lessons, explanation of tasks, and explanation of solutions, can be found at (click): Explanations in C++ for the 17 Algorithm Lessons at https://app.codility.com/programmers with Problems and Solutions

Cousins

NEXT

Broad Network

Series Articles