Stacks And Queues In STL

Learn The Implementation Of Stacks And Queues In STL With Examples.

Stacks and queues are two containers in STL which are very basic in nature. They are the simplest containers which have wide applications in software programming.

In this tutorial, we will see a detailed implementation of both these containers in STL. We will also go through the various operations supported by stack and queue with examples.

=> Watch Out The Simple C++ Training Series Here.

Stacks

Stack container in STL is a type of container adaptors. It is used to replicate a stack data structure in C++. Stack container is a set of elements in which the elements are inserted at one end and are also deleted at the same end.

This common point of addition and deletion is known as “Top of the stack”.

The pictorial representation of stack is shown below.

As shown in the above representation, the stack is a container in which elements are added and deleted from the same end called Top of the stack.

Since addition and deletion happen at the same end, we can say that stack container is LIFO (last in, first out) type of work. This means, that the element added first will be the last one to be deleted.

In order to implement stack container, we need to include the header <stack> in our program.

#include<stack>

The general declaration syntax for stack container is:

stack<objectType> stackName;

Stack Operations

Next, let us discuss the various operations that stack container in STL supports.

• push: push operation is used to insert an element in the stack. This operation always adds elements at the top of the stack.

Consider an empty stack mystack of type integer.

Next, let’s add element 1 to the stack.

Then, we add element 3 to the stack.

According to the representation, as a result of a push operation, an element is added at the top of the stack. After every push operation, the size of the stack is increased by 1.

• pop: pop operation is used to remove an element from the stack. The element removed is the one that is pointed to by the top of the stack. As a result of the pop operation, the stack size is reduced by 1.

Let us see how the pop operation looks like:

Consider the stack mystack as above in which we have already pushed 2 elements.

Now let us call the function pop(). When this call is executed, the element at the top of the stack is removed and the ‘Top’ points to the next element as shown below.

If we again call pop(), then the next element (in this case 1) will be removed thereby resulting in an empty stack.

• top: Returns the topmost element of the stack.
• empty: Checks if the stack is empty or not.
• size: Returns the size of the stack i.e. the number of elements in the stack.

Further Reading => Frequently Asked Stack Developer Interview Questions

Given below is an example of Stack implementation to better understand the operations.

#include <iostream>
#include <stack>
using namespace std;
void printStack(stack <int> stk)
{
   while (!stk.empty())
      {
         cout << '\t' << stk.top();
         stk.pop();
      }
   cout << '\n';
}
 
int main ()
{
   stack <int> oddstk;
   oddstk.push(1);
   oddstk.push(3);
   oddstk.push(5);
   oddstk.push(7);
   oddstk.push(9);
 
   cout << "The stack is : ";
   printStack(oddstk);
 
   cout << "\nSize of stack: " << oddstk.size();
   cout << "\nTop of stack: " << oddstk.top();
   cout << "\noddstk.pop() : ";
   oddstk.pop();
   printStack(oddstk);
   cout<<"\nAnother pop(): ";
   oddstk.pop();
   printStack(oddstk);
   return 0;
}

The above example clearly shows the push operation that generates a stack. It also shows the stack after two consecutive pop operations.

Thus we have seen stack and its operations in STL. Further, in this tutorial, we will see the detailed implementation of yet another simple STL container which is “Queue”.

Queue

The queue is yet another container in STL which is very simple and useful too. Queue container is a replica of the queue data structure in C++. Unlike stack, in the queue container, there are two ends, i.e. front, and back.

Elements are added to the queue at the back while deleted from the front of the queue. In general, queue uses FIFO (First in, First Out) type of arrangement.

To implement a queue container in a program, we have to include a header <queue> in the code.

#include <queue>

The general syntax for declaration of the queue is:

queue<objectType> queue_name;

We declare the queue container as follows:

Queue<int> myqueue;

Queue Operations

Now, we will see the various operations supported by the queue.

• push: Function ‘push’ adds the element at the end of the queue i.e. at the back of the queue.
• pop: Function ‘pop’ removes the first element of the queue i.e. the element at the front of the queue.

Let us understand the push and pop functions of the queue.

Consider an empty queue declared above myqueue. Now we push an even number 2 in the queue with the operation

myqueue.push(2);

Now the queue will look like:

Next, we add ‘4’ to the queue with call ‘myqueue.push(4)’.

Now the queue looks as shown below:

As seen above, the elements are pushed into the queue from the rear end or back.

Now let us pop operation on myqueue.

myqueue.pop();

So as we see, when pop() is called, element in the front of the queue is removed. This means that the first element that is entered the queue is the first element to be out of the queue.

• front: This function returns a reference to the first element of the queue.
• back: Back returns a reference to the last element in the queue.
• empty: Checks if the queue is empty.
• size: Returns the size of the queue i.e. the number of elements in the queue.

Given below is an Example program that demonstrates the operations used by the queue container.

#include <iostream>
#include <queue>
using namespace std;
void printQueue(queue <int> myqueue)
{
   queue <int> secqueue = myqueue;
   while (!secqueue.empty())
   {
      cout << '\t' << secqueue.front();
      secqueue.pop();
   }
   cout << '\n';
}
int main()
   {
      queue <int> myqueue;
      myqueue.push(2);
      myqueue.push(4);
      myqueue.push(6);
      myqueue.push(8);
      cout << "The queue myqueue is : ";
      printQueue(myqueue);
      cout << "\nmyqueue.size() : " << myqueue.size();
      cout << "\nmyqueue.front() : " << myqueue.front();
      cout << "\nmyqueue.back() : " << myqueue.back();
      cout << "\nmyqueue.pop() : ";
      myqueue.pop();
      printQueue(myqueue);
      return 0;
   }

Output:

The queue myqueue is :            2           4             6            8

myqueue.size() : 4

myqueue.front() : 2

myqueue.back() : 8

myqueue.pop() :        4            6            8

As shown above, we declare a queue container first. Then using the push operation we add the first four even numbers into it. After that we pop the element from the queue and display the changed queue.

Conclusion

With this, we have come to the end of this tutorial on stacks and queues. As already mentioned these are the simplest containers that we have in STL. Another variation of the queue container is known as “Priority Queue”.

In our upcoming tutorial, we will discuss more on Priority Queue in STL!!

=> Visit Here To Learn C++ From Scratch.