Stack in C++
C++ has a library known as Standard Template Library(STL). It provides built-in implementations of common data structures, such as dynamic arrays, linked lists, stacks, queues, heaps , etc. The stack template class in C++ STL provides an easy-to-use stack implementation. It has all the standard features such as push, pop, top, size, empty, etc., which a user could need.
Syntax Of Using Stack In C++
- stack is the name of the stack template keyword we use to construct a stack object.
- type is a valid C++ data type passed as an argument to the stack template. It indicates the data type of the elements stored in the stack.
- stackName is the name of the stack object that we have created.
To be able to use the stack in C++, one needs to include its header as follows :
C++ Stack Template Parameters
Stack template in C++ takes the following 2 parameters:
The type is a valid C++ data type passed as an argument to the stack template. It indicates the data type of the elements stored in the stack.
Passing an argument value for this parameter is optional. It represents the C++ container data structure to be maintained and used internally by our stack object. Either of C++ std::vector, std::list or std::deque can be used as the container for the stack. The default value of the optional argument is C++ std::deque.
Functions in C++ Stack
C++ stack class provides the following major methods :
|Item should necessarily be of the same data type as the type provided to the stack template during the construction of our object stackName.
|Removes an element from the top of the stack, if present.
|Return the top element from the stack, if present.
|Same type as stack template object stackName
|Returns whether or not the stack object is empty.
|Returns the number of elements present in the stack object.
Example Explaining Stack STL Functions
The space complexity of all the stack methods is generally constant where time complexities are
- push : A push_back call is made to the underlying container.
- For vector, time complexity will be amortized (O(n)).
- For list, time complexity will be constant.
- For deque, time complexity will be constant.
- pop : A pop_back call is made to the underlying container. The time complexity for pop_back on any of the three types of containers we had discussed is constant.
- top : constant.
- size : constant.
- empty : constant.
Applications Of C++ Stack:
Infix to postfix expressions using stack
Infix expression is an expression of the form x op y, where op is an operator in-between the pair of operands. Postfix expression is an expression of the form x y op, where the operator op is followed for the pair of operands.
Problem statement: To convert a given infix expression to its postfix form.
Expression parsing and evaluation using stack in C++
Problem statement: Given in the form of a string an arithmetic expression. Evaluate it and return its value as the answer.
Usage of the stack in tree traversals
Problem statement: Given a binary tree, perform inorder traversal upon the tree without recursion.
Problem statement: Given a binary tree, perform preorder traversal upon the tree without recursion.
Problem statement: Given a binary tree, perform postorder traversal upon the tree without recursion.
Algorithms for sorting a stack.
Problem : Given an array of integers, sort it using stack iteratively.
Solving the popular Towers Of Hanoi problem using stack
Problem: Given 3 poles, p1, p2, and p3. There are a number of disks put on the pole p1. They need to be transferred from p1 to p3 using p2 as an intermediary (Auxiliary support pole).
- The stack is a data structure that operates on the LIFO (Last In First Out) principle. It is used in solving a variety of problems.
- Among the many useful methods of stack class that C++ provides, the most common are push, pop, empty, size, and top.
- Stack is used for solving various problems such as infix to postfix, postfix to prefix, the prefix to infix, Tower of Hanoi, arithmetic expression calculation, etc.