Stacks
Stack is a type of container adaptor data structure designed to operate in LIFO(Last In First Out) technique of operation, where a new component is combined at one end and (top) an element is detached from that end only that is stack elements are added as well as removed from one end only. Stack uses an encapsulated object of either deque (by default) vector or list (sequential container class) as its underlying container, giving a specific set of member functions to access its elements.
The stack can be formed from different sequence containers. If the container is not given it uses the default deque container. Container adapters do not support iterators hence we cannot use them for changing the data. Though, they support push() and pop() member functions for data insertion and deletion.
The std::stack allows elements to be added and deleated or removed from one end only.
Stack Syntax:-
For creating a stack, we must incorporate the <stack> header file in our program code:
template <class Type, class Container = deque<Type> > class stack;Type – Elements contained in the std::stack.
Container – is the Type of underlying container object.
These are the basic operations that are performed:
- Push: Appends an item in the stack. If the stack is full, then it is said to be an Overflow condition. Time Complexity: O(1)
- Pop: Eliminates an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition. Time Complexity: O(1)
- Peek or Top: Returns the top element of the stack.
- isEmpty: Returns true if the stack is empty, else false. Time Complexity: O(1)
- size: Returns the size of the stack – Time Complexity: O(1)
Member types
Following member types can be used as parameters or return type by member functions.
| Sr.No. | Member types | Definition |
|---|---|---|
| 1 | value_type | T (First parameter of the template) |
| 2 | container_type | Second parameter of the template |
| 3 | size_type | size_t |
| 4 | reference | value_type& |
| 5 | const_reference | const value_type& |
Constructors
| Sr.No. | Method & Description |
|---|---|
| 1 | stack::stack default constructor creates an empty stack object, with zero elements. |
| 2 | stack::stack copy constructor builds a stack with a copy of each element present in another stack. |
| 3 | stack::stack move constructor forms a stack with the contents of other using move semantics. |
Destructor
| Sr.No. | Method & Description |
|---|---|
| 1 | stack::~stack Demolishes stack by deallocating container memory. |
Member functions
| Sr. No. | Method & Description |
|---|---|
| 1 | stack::emplace Constructs and includes a new element at the top of the stack. |
| 2 | stack::empty Tests whether the stack is empty or not. |
| 3 | stack::operator= copy version attributes new contents to the stack by replacing old ones. |
| 4 | stack::operator= move version Assigns new contents to the stack by substituting old ones. |
| 5 | stack::pop Eliminates a top element from the stack. |
| 6 | stack::push copy version Inserts a new element at the top of the stack. |
| 7 | stack::push move version Inserts a new element at the top of the stack. |
| 8 | stack::size Returns the total number of elements present in the stack. |
| 9 | stack::swap Exchanges the contents of the stack with contents of another stack. |
| 10 | stack::top Returns a reference to the highest element of the stack. |
Implementation:
There are two ways to implement a stack:
- Using array
- Using linked list
Example: Swap Function
This method swaps the elements of the two stacks.
#include <iostream>
#include <stack>
using namespace std;
int main ()
{
stack<int> s;
// pushing elements into stack
s.push(2);
s.push(3);
s.push(4);
cout << s.top(); // prints 4, as 4 is the topmost element
cout << s.size(); // prints 3, as there are 3 elements in
}
Applications of stack
- Symbol Balancing
- Conversions of Infix to Postfix/Prefix
- Features like Redo/Undo at many places like editors, photoshop.
- Feature of forwarding and backward in web browsers.
- Backtracking is one of the algorithm designing techniques. Some examples of backtracking are the Knight-Tour problem, N-Queen problem.
- Used in Graph Algorithms like Topological Sorting.
- Used In CPU Memory management
- String reversal is also one application of stack.
- Used in many algorithms like tree traversals, Tower of Hanoi, histogram problem, stock span problem.
