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.

Example :

C++ Stack Template Parameters

Stack template in C++ takes the following 2 parameters:

1. Data type:

   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.

2. container:

   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.

Example:

Output:

Functions in C++ Stack

C++ stack class provides the following major methods :

Example Explaining Stack STL Functions

Output:

Time complexity

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.
  1. For vector, time complexity will be amortized (O(n)).
  2. For list, time complexity will be constant.
  3. 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.

C++ Code:

Output:

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.

Code:

Output:

Usage of the stack in tree traversals

1. Inorder:

Problem statement: Given a binary tree, perform inorder traversal upon the tree without recursion.

Code:

Output:

2. Preorder:

Problem statement: Given a binary tree, perform preorder traversal upon the tree without recursion.

Code :

Output:

3. Postorder

Problem statement: Given a binary tree, perform postorder traversal upon the tree without recursion.

Code:

Output :

Algorithms for sorting a stack.

Problem : Given an array of integers, sort it using stack iteratively.

Code :

Output:

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).

Code:

Related Topics

• Reversing a Stack Using Recursion
• Infix to Postfix Using Stack