Stack Pop Operation- using Array and Linked List

Deletion operation in a Stack is called Pop. Stack is LIFO (Last In First Out) structure, so the element added at the top of the stack is the one to be deleted first. The end where the deletion takes place in a Stack is called TOP or TOS (Top of Stack).

It’s like removing a coin from a stack of coins or a book from a stack of book. In computer terms completing execution of a function call and removing it from the top of pending function calls, redoing editing actions in a word editor with undo command and clicking back button in browser to move back to previous pages opened by a user following hyperlinks.

You have already learnt Push action in a stack using a Linear array and a Linear Linked List. So, next we will discuss how Stack Pop operation is implemented in both these implementations of a Stack data Structure.

Stack Pop Operation using an Array

Pop means deleting an element from the top of the stack. In the linear Array representation of a Stack, a variable TOP is maintained to store the index of the last added element.

To stack pop an element first the topmost element is stored in a variable and then the TOP variable is decremented to remove the element from stack. If current value of TOP is equal to -1 (STACK is empty) then no element can be popped. This is the state of Underflow of Stack occurs.

Algorithm POP_ARRAY(STACK, TOP, ITEM)
Step 1 	[If underflow, Exit algorithm. Pop not possible]
        IF TOP==-1 	 Then Exit
Step 2	[Store topmost element at TOP, to be deleted]  
        ITEM=STACK[TOP]
Step 3	[Decrement TOP variable to remove the element] 
        TOP=TOP-1
Step 4  Exit

Pop Operation using a Linked List

In dynamic Linked List representation of a Stack, a pointer TOP is maintained to store the address of the last added element as a linked list node.

To pop element in this implementation, the element whose address is preserved in TOP pointer, is given in PTR, a pointer, to store it for any processing after deletion.

TOP pointer is updated with the address of the next node stored in LINK of TOP. This way by updating the TOP pointer, the Stack Pop operation is implemented.

Algorithm POP_DYNAMIC (TOP, ITEM)
Step 1 	[Check TOP for empty Stack- underflow]  
        If TOP==NULL, Exit as stack is empty
Step 2	[Store topmost element in ITEM variable]
        PTR= TOP
        ITEM=PTR->DATA
Step 3	[Update TOP of the stack] 
        TOP=TOP->LINK
Step 4 	Exit