Operations on stacks: The following operations are performed on stacks.
- Creating an empty stack
- PUSH (STACK. ITEM) – to push element ITEM onto stack STACK
- POP (STACK) to access and remove the top element of the stack STACK
- PEEK (STACK) to access the top element of the stack STACK without removing the top element from the stack. Also called PEEP
Note – Before learning about Operations on the stack if you don’t have knowledge about stack then read this post.
Stack in Data Structures and Algorithms
ADT STACK
A stack of elements of type T is a finite sequence of elements of T together with the operations
- Initialize the stack to be empty.
- Determine if the stack is empty or not.
- Determine if the stack is full or not.
- If the stack is not full, insert a new node at one end of the stack, called its top.
- If the stack is not empty, then retrieve the node at its top.
- If the stack is not empty delete the node at its top.
Creating an empty stack
Before we can use a stack it is to be initialized. As the index of array elements can take any value in the range 1 to MAXSTACK the purpose of initializing the stack is served by assigning the value 0 (sentinel value) to the top variable.
Push operation
Before the push operation if the stack is full then the value of the top will be equal to MAXSTACK and then the push operation can’t be performed. If the stack is not full, then the top value will be the index of the element currently on the top. Therefore before we place the value onto the stack the value of the top is incremented so that it points to the new top of the stack, where the incoming element is placed.
PUSH Algorithm
PUSH (STACK, TOP, MAXSTK, ITEM)
This procedure adds a new ITEM at the TOP of a stack
1. [Stack already filled?]
If TOP = MAXSTK. then Write OVERFLOW. and Return.
2. Set ITEM=STACK[TOP] [Assigns TOP element to ITEM]
3. Set TOP:=TOP – 1 [Decreases TOP by 1.]
4. Return.
Pop operation
Before the pop operation if the stack is empty then the value of the top will be equal to O (sentinel value) and then the pop operation can’t be performed. The element on the top of the stack is assigned to a local variable, which later on will be returned. After assigning the top element to a local variable the variable top is decremented so that it points to the new top.
Pop Algorithm
POP(STACK, TOP, ITEM)
This procedure removes the TOP element of STACK and assigns it to the variable ITEM.
1. [Stack has an item to be removed?]
If TOP = 0, then: Write UNDERFLOW and Return.
2. Set ITEM:=STACK[TOP]. [Assign TOP element to ITEM.]
3. Set TOP:=TOP-1. [Decreases TOP by 1.]
4. Return
Testing stack for underflow
Before we remove an item from a stack it is necessary to test whether the stack will have some elements i.e. to test whether the stack is empty or not. If it is not empty then the pop operation can be performed to remove the top element. This test is performed by comparing the top value with the sentinel value 0.
Testing stack for overflow
Before we insert a new item onto the stack it is necessary to test whether the stack still has some space to accommodate the incoming element Le. to test whether the stack is filled or not. If it is not full then the push operation can be performed to insert the element at top of the stack. This test is performed by comparing the value of the top with the value MAXSTACK, the largest index value that the top can take.
Accessing the top element (PEEK or PEEP)
There may be instances where we want to access the top element of the stack without removing it from the stack (i.e. without popping it)
Peek Algorithm
PEEK (STACK, TOP, ITEM)
This procedure shows the top element of STACK without removing it and assigns it to the variable ITEM.
1. [Stack has an item to be shown?]
If TOP = 0, then: Write UNDERFLOW, and Return.
2. Set ITEM:=STACK[TOP]. [Assigns TOP element to ITEM.]
3. Return.
Efficiency
All of these operations run in O (1) time.
Also, read