Hi everyone

In this tutorial we will talk about Stack

So, What is stack actually?

Stack is a Last In First Out(LIFO) data structure.

STL Stack also works the same way

STL stack container’s underlying data structure deque (Double Ended Queue)

Header File Inclusion for stack

#include <stack>

Declaration

#include <stack>

stack <int> lifoList;

Insertion

push() method

With push() method we insert data into a stack. In a stack data is always inserted at the end.

lifoList.push(64);
lifoList.push(32);
lifoList.push(78);
lifoList.push(45);
lifoList.push(42);
lifoList.push(28);
lifoList.push(12);

After Insertion stack will look like this —

emplace() method

We can also insert values to stack with emplace() method —

lifoList.emplace(25)
lifoList.emplace(35)

After Insertion stack will look like this —

35
25
12
28
42
45
78
32
64

Accessing the element

top() method
top() method of stack returns top element of the stack

// this will output the top element from stack 
cout << lifoList.top() << endl;

Output will be – 35

Deletion

pop() method

Stack’s pop() method removes top element from stack

// removing element 35, now current top 25
lifoList.pop();

// removing element 25, now current top 12
lifoList.pop();

// removing element 12, now current top 28
lifoList.pop();

// removing element 28, now current top 42
lifoList.pop();

// removing element 42, now current top 45
lifoList.pop();

// removing element 45, now current top 78
lifoList.pop();

After Deletion stack will look like this —

Swapping

swap() method

There is a scenario that, someone need to swap values between two stack and if he is thinking about creating

auxiliary stacks. There is a good news for him. We don’t need to create auxiliary stacks if we are using STL stack.

STL stack has a method named swap(), which swaps values of two stack data structures —

stack <int> listOne;
listOne.push(128);
listOne.push(64);
listOne.push(32);

After Insertion listOne will look like this —

128

stack <int> listTwo;
listTwo.push(1);
listTwo.push(2);
listTwo.push(4);

After Insertion listTwo will look like this —

Now, let’s swap the elements of two stack —

// swapping values between two stacks
listOne.swap(listTwo)

After Swapping listOne will look like this —

After Swapping listTwo will look like this —

128

Time Complexity

Operation	Description	Time Complexity
push()	Inserts a element at the top of the stack	O(1)
emplace()	Inserts a element at the top of the stack	O(1)
top()	Returns the top element of the stack	O(1)
pop()	Removes the top element from the stack	O(1)
size()	Returns the number of elements of the stack	O(1)
empty()	Returns a bool value False if vector is not empty True if vector is empty	O(1)
swap()	Swap the elements of two stacks	O(n)

Applications

- - DFS Algorithm
  - Arithmetic Expression Evaluation and Conversion
  - String reversal
  - Parenthesis Checking
  - Backtracking

In the next tutorial we will talk about Queue which is a sequential container.

Until then
Happy Coding 💻 🎵