Stack in C++

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 :

Illustration Of Stack Operations

push:

This method allows us to add an element to the stack. Adding an element in a Stack in C++ occurs only at its top because of the LIFO policy. Suppose we have added in our stack elements 1, 2, and 3 in the same order as stated. The addition of another element, say 4, will be done immediately following the last added element. In this case, 4 will be added after 3. Thus the new state of our stack becomes 1, 2, 3, and 4.

pop:

This method allows us to remove an element from the top of the stack. Suppose the initial state of a stack is 1,2, and 3, added in the same order as stated. When pop is performed, the latest element entered will be removed. The number 3 will be popped off the stack in this example.

top:

the pop method is used to obtain the latest element to have been pushed into the stack. As the name suggests, this element is retrieved from the top stack. Suppose we have a stack in which elements 1, 2, and 3 are added in the same sequence as mentioned. Now calling the top method will return the last pushed element from the stack. In our case, the number at the top is 3 and, therefore, will be returned by a top function call.

empty:

the empty function is used to determine whether the stack object is empty.

size:

size is a method that allows determining the number of elements present in the stack.

Methods Of Stack In C++

C++ stack class provides the following major methods :

Example Explaining Stack STL Functions

Output:

Time complexity

The time complexity of the stack methods we have discussed depends upon the type of container internally used in the stack object.

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

Space complexity

• push : constant.
• pop : constant.
• top : constant.
• size : constant.
• empty : constant.

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:

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

Inorder:

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

Code:

Output:

Preorder:

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

Code:

Output:

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 :