Stack in C++ (STL)

Kabir Singh
Last Updated: May 23, 2022
Difficulty Level :
EASY

Introduction

Stacks can be visualized as containers in which we can store elements and remove them as well but only in the LIFO(Last in first out) order.

 

So this states that whenever we want to add an element to the stack it is added at the top and whenever we want to remove elements from the stack we start from the top itself.

So the element which was inserted in the last will be the first one to come out.

A stack can be easily implemented either through an array or a linked list. And all of these give us certain functions that we can use to access there specific elements

If you are wondering– how to replicate it in code. Don't worry, Coding Ninjas has you covered. To learn more, see C++ code for Stack Implementation using Arrays and C++ Code for Stack Implementation using Linked Lists to get a better understanding.

If you're already using C++ to solve problems, you’re probably aware of the Standard Template Library (STL), which is a handy tool that can save you a lot of time in coding contests due to the language's and libraries' wide capabilities.

The best part is that STL also helps with the implementation of stack in C++. Today’s article will show you how to use the STL to implement a stack in C++. For a quick brush up on stacks in C++, watch this video.

Let's define STL in a nutshell before moving on to its implementation.

What is STL?

When we consider problems that come under the topics of Advanced Data Structures, it is not recommended to write our own codes for some often used containers and algorithms like Stack, Maps, Binary Search, Vector etc.

So rather than coding our own searching or sorting algorithms, we can use readily available containers and algorithms that are present in the Standard Template Library(STL).

STL in C++ can be divided into three parts, which are as follows:

  • Containers: Pair, Vector, Forward-List, List, Stack, Queue, Priority Queue, Set, Map, Unordered-Set, Unordered-Map
  • Iterators
  • Generic Algorithms: Binary Search, Find, Reverse, Sort, Min, Max, Upper Bound, Lower Bound, etc.

 

Now, Let's get to the core of today's article: the stack in C++ (using STL)

How is a Stack Called?

In any program where we want to use a stack or do any operation on a stack in C++, all we need to do is add the header file “#include <stack>” first.  We then use the below syntax to define the stack.

std::stack<T> my_stack;

// or

std::stack<T, container> my_stack (container_instance);

 

Where:

  • T is the data type of elements in the stack like int, or char.
  • container is the data structure used to initialize your stack. This is optional and the stack uses an encapsulated object of either vector or deque (by default) or list (sequential container class) as its underlying container, providing a specific set of member functions to access its elements.
  • container_instance is the instance of container type.

This may appear complicated, but fear not! Next, we'll look at all of the operations that may be performed on a stack in STL, as well as the appropriate code.

Member Functions Related to Stack

push()-

When we use a container we either insert an element or remove an element from it. The push method allows us to insert elements into our stack. And every time we push an element to our stack it is always added to the top of the stack.

The syntax to the function is : 

  Stack_Name.push()

  Parameters :
  The element value which needs to be added is passed
        
  Return Value:
  Adds the value mentioned in the function on the top of the stack

 

Examples :

Input : stack01
        stack01.push(7);
Output : 7

Input : stack01

        stack01.push(5);

        stack01.push(6);
Output : 5 , 6

 

pop()-

 

When we use a container we either insert an element or remove an element from it. Pop method allows us to remove elements from our stack. And every time we pop an element from our stack it is always the top element that gets removed.

The syntax to the function is : 

  Stack_Name.pop()

  Parameters :
  No parameter is passed
        
  Return Value:
  Removes the top most value of the stack 

 

Examples :

Input :   stack01 = 7, 8, 9

          stack01.pop();

Output :  7, 8

 

Input :   stack01 = 7, 8, 9, 10, 11

          stack01.pop();

Output :  7, 8, 9, 10

 

Now we have 5 operations that come in handy when we are working on stacks. But how? How can we implement all these operations?

Let’s understand now!

empty() -

 

As stacks are containers they either can have some elements in them or can be totally empty. This empty() function can be used to find the same. 

The syntax to the empty function is : 

Stack_Name.empty()

  Parameters :
  There are no parameters Passed.
        
  Return Value:
  True, If our stack is empty.
  False, If our stack is not empty.

 

Examples : 

Input : stack01
        stack01.empty();
Output : True

Input : stack01 = 7,19,21;
        stack01.empty();
Output : False

 

size()-

The second operation or function that we can perform on a stack is the size(). This function returns the size of our stack or the count of the elements that are present in our container.

The syntax to the function is : 

  Stack_Name.size()

  Parameters :
  There are no parameters Passed.
        
  Return Value:
  Number of elements present in the container

 

Examples :

Input : stack01 = 7,8,9
        stack01.size();
Output : 3

Input : stack01 = 10,11,12,13,14,15
        stack01.size();
Output : 6

 

top()-

 

As stack follows last in first out order of elements, the last element i.e the newest element always stays on the top of the stack.

To return that element(newly added) we use this top() function.

 The syntax to our top function comes as follows:

Stack_Name.top()

Parameters :
There are no parameters Passed.

 

Return Value :

Element that is on the top of the stack

 

 Examples :

Input  : stack01.push(1);
        stack01.push(2);
        stackname.top();
Output : 2

Input  : stack01.push(7);
        stack01.push(9);
        stack01.push(4);
        stack01.top();
Output : 4

 

Implementation of Stack in C++ using STL 

// C++ program to implement
// push(), pop(), top(), empty(), size() operations
#include <iostream>
#include <stack>
using namespace std;

int main()
{
    stack<int> stack01;
    stack01.push(7);
    stack01.push(8);
    stack01.push(9);
    stack01.push(10);
    // Stack becomes 7, 8, 9, 10

    stack01.pop();
    stack01.pop();
    // Stack becomes 7, 8

    if(stack01.empty()){
        cout << "true"<<endl;
        //our stack isn't empty so we'll not get true
    }
    else{
        cout << "False" << endl;
        //our stack isn't empty so we'll get false
    }

    cout << stack01.top() << endl;
    //we have 8 as output as 8 is on the top

    cout << stack01.size() << endl;
    //we will get 2 as the size as we have 7 and 8 in our stack
}

 

Output - 

False
8    
2    

 

Explanation

Let’s see why this code works now!

  • We use the usual header file and an extra header file “#include <stack>”.
  • Using namespace std; makes it easier to use the classes without calling them.
  • Making a main() function states that the entire logic of the code will be coded inside this function.
  • Creating an integer stack makes us eligible to store integer values in the container.
  • Use push() to add elements in the stack -
  • Add 7 to the stack
  • Add 8 to the stack
  • Add 9 to the stack
  • Add 10 to the stack 
  • Pop() one element from the stack. 10 gets removed from the stack.
  • Pop one more element from the stack. 9 gets removed from the stack.
  • Using empty() we check if the stack is empty or not (we get false because our stack is not empty).
  • Use a top() function to return the topmost element of our stack. (Our topmost element is 8).
  • Size() is used to return the size of our stack. We get 2 as our stack has only 2 elements left.
  • End the main function.

Complexity Analysis

The functions associated with stack are: 

empty() – Returns whether the stack is empty – Time Complexity: O(1) 

size() – Returns the size of the stack – Time Complexity: O(1) 

top() – Returns a reference to the topmost element of the stack – Time Complexity : O(1) 

push(ele) – Adds the element ‘ele’ at the top of the stack – Time Complexity : O(1) 

pop()– Deletes the top most element of the stack – Time Complexity : O(1) 

Frequently Asked Questions

  1. What is STL in C++?
    STL - Standard Template Library can be defined as a software library that stores pre-written codes of frequently used data structures like a stack, maps, set, searching, sorting etc.
     
  2. What is a stack?
    A stack can be defined as a container that can be used to store elements of similar data types. It follows the Last in First out principle(LIFO) for storing and retrieving elements.
     
  3. What does top do in a stack?
    Top function returns the topmost element of the stack. This means the last element that was added in the stack will be returned.  
        
  4. How can we add a new stack in c++?
    We can add a stack in c++ by :
    Adding the <stack> header file to our program.
    Using the syntax - (stack<Datatype> Stack_Name)

Conclusion

This article has cleared most of the doubts about the stack in C++( using STL) and the functions that are used on the stack as well. 

Don’t know if STL is a good thing to learn?

Simple Answer - Yes!

As you start solving advanced data structure problems you will end up using containers and algorithms which are already present in STL just like stack and it becomes easy to solve the problems then.

If you want to solve some problems on the stack like the minimum stack problem and sharpen your skills you can refer to CodeStudio.

Happy Learning!

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think