Stack Data Structure
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). There are many real-life examples of a stack. Consider an example of plates stacked over one another in the canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO(Last In First Out)/FILO(First In Last Out) order. A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to implement stack using arrays, which makes it a fixed size stack implementation. Basic Operations Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from these basic stuffs, a stack is used for the following two primary operations − push() − Pushing (storing) an element on the stack. pop() − Removing (accessing) an element from the stack. When data is PUSHed onto stack. To use a stack efficiently, we need to check the status of stack as well. For the same purpose, the following functionality is added to stacks − peek() − get the top data element of the stack, without removing it. isFull() − check if stack is full. isEmpty() − check if stack is empty. At all times, we maintain a pointer to the last PUSHed data on the stack. As this pointer always represents the top of the stack, hence named top. The top pointer provides top value of the stack without actually removing it. Push Operation The process of putting a new data element onto stack is known as a Push Operation. Push operation involves a series of steps − Step 1 − Checks if the stack is full. Step 2 − If the stack is full, produces an error and exit. Step 3 − If the stack is not full, increments top to point next empty space. Step 4 − Adds data element to the stack location, where top is pointing. Step 5 − Returns success. If the linked list is used to implement the stack, then in step 3, we need to allocate space dynamically. Pop Operation Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of pop() operation, the data element is not actually removed, instead top is decremented to a lower position in the stack to point to the next value. But in linked-list implementation, pop() actually removes data element and deallocates memory space. A Pop operation may involve the following steps − Step 1 − Checks if the stack is empty. Step 2 − If the stack is empty, produces an error and exit. Step 3 − If the stack is not empty, accesses the data element at which top is pointing. Step 4 − Decreases the value of top by 1. Step 5 − Returns success. ARRAY REPRESENTATION OF STACKS Stacks may be represented in the computer in various ways, usually by means of a one-way list or a linear array. Unless otherwise stated or implied, each of our stacks will be maintained by a linear array STACK; a pointer variable TOP, which contains the location of the top element of the stack; and a variable MAXSTK which gives the maximum number of elements that can be held by the stack. The condition TOP = 0 or TOP = NULL will indicate that the stack is empty. Algorithm for Push & Pop PUSH(STACK, TOP, MAXSTK, ITEM) This procedure pushes an ITEM onto a stack. 1. [Stack already filled?) If TOP = MAXSTK, then: Print: OVERFLOW, and Return. 2. Set TOP := TOP + 1. [Increases TOP by 1.] 3. Set STACK[TOP] := ITEM. [Inserts ITEM in new TOP position.] 4. Return. POP(STACK, TOP, ITEM) This procedure deletes the top element of STACK and assigns it to the variable ITEM. 1. [Stack has an item to be removed?] If TOP = Q, then: Print: UNDERFLOW, and Return. 2. Set ITEM := STACK[TOP]. (Assigns TOP element to ITEM.] 3. Set TOP := TOP — 1. [Decreases TOP by 1.] 4. Return. Frequently, TOP and MAXSTK are global variables; hence the procedures may be called using only PUSH(STACK, ITEM) and POP(STACK, ITEM) respectively. Note that the value of TOP is changed before the insertion in PUSH but the value of TOP is changed after the deletion in POP. Stack Push Operation using Array For PUSH Operation Click Here
Stack Pop Operation using Array For POP Operation click here
0 Comments