After understanding the basic concepts of Stack in Data Structure, the next step is to learn about its operations. Insertion operation in a Stack is called Push.
Stack is LIFO (Last In First Out) structure, so the element added at the end is the one to be deleted before any other element. The end where the insertions and deletions take place in a Stack Data structure is called TOP or TOS (Top of Stack).
It’s like adding a plate on stack of plates, a book on a stack of book. In computer terms adding a function call on the top of previous function calls waiting to be completed, storing editing actions in a word editor for redo or undo and stacking up the pages opened by a user by clicking hyperlinks.
You have already learnt that a stack can be implemented using a Linear array and a Linear Linked List. So, we will discuss how Push operation is implemented in both these implementations of a Stack data Structure.
Push Operation in Stack Implementation using an Array
Push means adding an element at 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. This index is calculated by incrementing the current value of the TOP variable.
If current value of TOP is equal to MAX (size of the STACK) then no new element can be pushed and condition of Overflow of Stack Data Structure occurs. A new element is added at this calculated index like you added an element in a linear array at the end.
Algorithm PUSH_ARRAY(STACK, TOP, MAX,ITEM) Step 1 [Increment TOP] TOP=TOP+1 Step 2 [If Overflow happened, Exit algorithm. Push not possible] IF TOP==MAX Then Exit Step 3 [Push element at new top] STACK[TOP]=ITEM Step 4 Exit
Push Operation in Implementation using a Linked List
In dynamic Linked List representation of a Stack data structure, a pointer TOP is maintained to store the address of the last added element as a linked list node.
To push element in this implementation, first a new node is created and identified by pointer NEW. The item to be pushed is stored in the DATA part of the node. The LINK part of NEW is assigned TOP pointer and TOP pointer is assigned the NEW pointer. This way by updating the pointers, the push operation is implemented.
Algorithm PUSH_DYNAMIC (TOP, ITEM) Step 1 [CREATE the new Node] Fetch Memory required for a Node and Store its address in NEW pointer Step 2 [If NEW is null exit the algorithm since memory is not available to push is new element] IF NEW==NULL Then Exit Step 3 [Push element at top of stack] NEW->LINK= TOP TOP=NEW Step 4 Exit
Be First to Comment