Implement std::stack in C++

Operations of Stack 

Now that you are aware of how stack stores data. Let's move to what basic operations a stack offers. Let's fit these operations in some functions.

1. push(): The push() function is used to insert data in the stack. Whatever data is added, it's on top. 
2. pop(): The pop() deletes one element from the stack. Of course, that element is the topmost one. 
3. top(): The top() function gives the value of the element which is present at the top of the stack. It is sometimes called peek(). 

In stack, you cannot access any random element. There is a sequence to that. Only the topmost element can be operated upon. That's the reason it is kept as a different data structure in itself.

Also Read - C++ Interview Questions

Implementation of Stacks

In this section, let's try to implement a stack.
There are two basic ways in which stacks are implemented. 

• The first one is using arrays/vectors. 
• The second one is using a linked list. 

One more thing: It is not necessary that elements are stored in contiguous memory locations, therefore, we should have some mechanism with which we can access the elements in the order we insert them. In other words, it should be implemented such that all operations should be performed as efficiently as possible.

Implementing stack using array/vector

Before we start implementing, I would like to make it clear that here the term arrays and vectors may be used interchangeably as by now you know that vectors are nothing but resizable arrays only.  
In case, the number of elements is known beforehand, use an array to store elements else use vectors.

Let’s first use Arrays:

Assuming that the maximum number of elements that our stack can hold is N (here 3). Since we are implementing it in C++, let’s use classes for it.
 

Defining the class: 

#include <bits/stdc++.h>
using namespace std;
#define size 3 
class Stack
{
	int top;
	int stack_arr[size];
	public:
		Stack()
		{
			top=0;
		}
		void push(int value);
		void pop();
		void peek();
}; 

You can also try this code with Online C++ Compiler

Run Code

Here, the variable ‘top’ keeps track of the topmost element and checks if the stack is full to its capacity. Functions push(), pop() and peek() are its member functions.
This implementation is specifically for the ‘int’ data type. It can be made similarly for other data types. Templates can also be used to make it generic. For the sake of understandability and simplicity, we have avoided using it.  
Now, let’s implement all the member functions.
 

• Implementing push() function

void Stack::push(int value) 
{
	if(top==size)      //Checking if stack is already full
	{
		cout<<"Stack is full\n";
	}
	else
	{
		stack_arr[top]=value;
		top++;
		cout<<"Element inserted successfully\n";
	}
}

You can also try this code with Online C++ Compiler

Run Code

Here, first, we check if the stack is not already full. If so, we add the value of the data and make the ‘top’ variable pointing to the new element as it is on the top now. Whatever action is taken is conveyed to the user(like a good programmer would do!). Time-complexity of this function is O(1).
 

• Implementing pop() function

void Stack::pop() 
{
	if(top==0)//Checking if stack is already empty
	{
		cout<<"Stack already empty\n"; 
	}
	else
	{
		top--; //shifting top 
		cout<<"Element deleted successfully\n";
	}
}

You can also try this code with Online C++ Compiler

Run Code

Here, in case the stack is not empty, the topmost element is deleted. You may argue that we cannot delete values from an array. Yes, that's true! We can’t. We are actually not deleting it, we are just giving the user the feeling that it has been deleted by shifting the position of the ‘top’ variable. Also, we convey the message to the user about whatever action is taken. Time-complexity of this function is O(1).
 

• Implementing peek() function

void Stack::peek() 
{
	if(top==0)//If stack is empty 
	{
		cout<<"Stack is empty\n";
	} 
	else
	{
		cout<<"The topmost element of stack is "<<stack_arr[top-1]<<"\n";
	}
}

You can also try this code with Online C++ Compiler

Run Code

It simply checks if the stack is not empty and then displays the topmost element. We have used ‘top-1’ because if you observe, ‘top’ points to the position where the next incoming element should be inserted. Time-complexity of this function is O(1).

Let’s dry run this:
Creating an object of class Stack:

push(1)

push(2),push(3)

push(4)

“The stack is full” 

peek()

“The topmost element of the stack is 3”

pop(),pop(),pop(),pop()

“Element deleted successfully” 
“Element deleted successfully” 
“Element deleted successfully” 
“Stack already empty”

Now let’s discuss Vectors:

The difference while using vectors is that now no more variable like ’top’ is required. As deleting an element in a vector from memory is possible. We no longer have to abstractly remove the element, instead, the element is actually deleted. So, directly push_back() and pop_back() functions can be employed here.  

One feature that we get using vectors is size does not need to be initialized beforehand, but then it comes with a cost of time complexity of what vectors have. You might have observed that while implementing the LIFO or FILO property was taken utmost care, after all that’s the speciality of the stack. The reason that arrays/vectors are considered as one of the effective data structures to implement stacks is that elements are stored one after the other, which makes the implementation of all the operations easy and efficient. 

Implementing stack using LinkedList

A brief about LinkedList

A LinkedList can be thought of as a set of nodes where one node is pointing to the other. That’s how they remain together and represent data sequentially. There is some technique through which nodes have the ability to point to other nodes(Usually through pointers).  
What we use while implementing the stack is a singly linked list, where each node can point to one node only and point to the next node. It forms a linear structure somehow like shown below:

Implementation 

Here, also we will implement it with the help of the class. When we are using LinkedList for achieving this task, we don’t need to specify the size as dynamic allocation is happening. You will understand this as we move forward.

So defining the class below: 

#include <bits/stdc++.h>
using namespace std;
class node           //defining the node class
{
	int value; 
	node *next;     //pointer to next node
}; 
class Stack
{
	node *top;
	public:
		Stack()
		{
			top=NULL;
		}
		void push(int val);
		void pop();
		void peek();
}; 

You can also try this code with Online C++ Compiler

Run Code

Here, an extra class called ‘node’ has been created that stores the value of every node(i.e., An element) and also points to the next node. 
node *top is the initialization that keeps track of the last inserted element. Member functions have the same functionality as earlier. 
 

1. Implementing push() function

void Stack::push(int val)
{
	node *temp=new node(val);        //creating a new node
	if(top==NULL)//Checking is stack is empty
	{
		top=temp;
	}
	else
	{
		temp->next=top;
		top=temp;
	} 
	cout<<"Insertion successful\n";
}

You can also try this code with Online C++ Compiler

Run Code

At first, we check if the stack is empty using the condition “if(top==NULL)”. Our task is to make incoming elements top to maintain the LIFO property. Time-complexity of this operation is O(1).
 

2. Implementing pop() function

void Stack::pop()
{
	if(top==NULL)
	{
		cout<<"Stack is empty\n";
	}
	else
	{
		node *temp=top;
		top=top->next; 
		delete(temp);
		cout<<"Deletion successful\n";
	}
}

You can also try this code with Online C++ Compiler

Run Code

Here also, in case the stack is not already empty, the node with the most recent element is deleted, and accordingly, the top is updated. Time-complexity of this operation is O(1).
 

3. Implementing pop() function 

void Stack::peek()
{
	if(top==NULL) 
	{
		cout<<"Stack already empty\n";
	}
	else
	{
		cout<<"The topmost element is "<<top->value<<"\n";
	}
}

You can also try this code with Online C++ Compiler

Run Code

It again checks for the emptiness of the stack and then displays the topmost value in the stack. Time-complexity of this operation is O(1).
Since there is extensive use of pointers, one needs to be very careful as they sometimes mess up the whole code if not used with utmost precision.

Apart from these two data structures, there are many others through which stack can be implemented. Some are queue, dequeue, etc. But these are the most basic ones and even beginners can easily understand them.

Must Read Stack Operations

Frequently Asked Questions

1. Is stack a linear data structure?
   Yes, stack stores data in a linear fashion.
    
2. What are real-life scenarios where the stack is present or used?
   Piles of plates and piles of books are two examples of stacks. Even water in a glass is a kind of stack.
    
3. Can stack only be implemented through data structures other than arrays/vectors and singly-linked lists?
   Yes,  data structures like queue, deque, doubly LinkedList can also be used for its implementation of a stack.

Conclusion

This article explains how a stack, which is present as a library function in C++, can be implemented from scratch. Different data structures that help in doing so and their complexities. 

Check out this problem - Check If A String Is Palindrome

Also read -  Decimal to Binary c++

We hope that this blog has helped you enhance your knowledge regarding stacks and if you would like to learn more, check out our articles on stacks in C++. You can also consider our Mern Stack Course to give your career an edge over others.

Do upvote our blog to help other ninjas grow. 

Happy Coding!