Home » Stacks | Introduction to Data Structures

Data structuresAlgorithms

Stacks | Introduction to Data Structures

Arpit Jain

May 8, 2021

0

SaveSavedRemoved 0

Topics to be covered:

• Definition of stacks
• Operations on stacks with algorithms
• Performance
• Applications of Stacks

Definition:

A stack is a linear collection of items that allows addition and deletion operations only from one end called the top of the stack.

Stack has the capacity to enlarge and compress the its size. It is also known as dynamic data structure.

Stack works on the principle of LIFO( Last In First Out) or FILO( First In Last Out).

Example: Heap of books in which we can extract or put a book only on the top.

Operations on Stack

1. PUSH operation
2. POP operation

1. PUSH:

• This adds an item on the top of the stack.
• If there is a bound on the size of the stack(say N) then as soon as the top becomes equal to N, the stack is said to be full.

Algorithm for Push Operation

Algorithm Push()
{
   Step

        1. If (Top >= N) then { prompt ("Stack Full"); exit)
        2. Top Top + 1;
        3. Stack [Top] = item;
        4. Stop
}

where

 Stack[N] represents a stack of N locations.
 The top keeps track of the top of the stack, i.e., the location where additions
and deletions are made.
 Item is used to store the item to be pushed from the stack.

2. POP:

 The pop operation removes an item from the top of the stack
 If more pop operations are done on the stack as shown then a stage will come when there will be no items left on the stack. This condition is called stack empty.

Algorithm for Pop Operation

algorithm pop()
{
   Step
         1. if (Top<0) then prompt ("Stack empty");
             else
               Item = Stack [Top];
               Top = Top - 1;
          2. stop
}

where

 Stack[N] represents a stack of N locations.
 The top keeps track of the top of the stack, i.e., the location where additions and
deletions are made.
 Item is used to store the item to be popped from the stack.

Performance

For the stack of ‘n’ elements:

1.) The space complexity of the stack is O(n).
2.) The time complexity of each operation is O(1).
3.) The size of the stack must be defined earlier when implemented using an array. Therefore, the size cannot be changed.

Applications of Stacks

1.) Evaluation of the arithmetic expression.
2.) Undo operation of a document editor or a similar environment.
3.) Implementation of recursive procedures.
4.) Backtracking.
5.) Keeping track of the page-visited history of a web user.

6.) Example: What’s app , G-mail, etc. also uses the stack as the newest message show us on the top.

You, can try the practical of this topic on virtual labs. https://ds1-iiith.vlabs.ac.in/exp/stacks-queues/index.html