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. 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. LINKED REPRESENTATION OF STACKS Stacks can be representation using a one-way list or singly linked list. The linked representation of a stack, commonly termed linked stack is a stack that is implemented using a singly linked list. The INFO fields of the nodes hold the elements of the stack and the LINK fields hold pointers to the neighboring element in the stack. The START pointer of the linked list behaves as the TOP pointer variable of the stack and the null pointer of the last node in the list signals the bottom of stack. A push operation into STACK is accomplished by inserting a node into the front or start of the list and a pop operation is undertaken by deleting the node pointed to by the START pointer. The array representation of stack calls for the maintenance of a variable MAXSTK which gives the maximum number of elements that can be held by the stack. Also, it calls for the checking of OVERFLOW in the case of push operation (TOP=MAXSTK) and UNDERFLOW in the case of pop operation (TOP=O). In contrast, the linked representation of stacks is free of these requirements. There is no limitation on the capacity of the linked stack and hence it can support as many push operations (insertion of nodes) as the free-storage list ( the AVAIL list) can support. This dispenses with the need to maintain the MAXSTK variable and consequently on the checking of OVERFLOW of the linked stack during a push operation. Push Algorithm in stack using Linked List PUSH_LINKSTACK(INFO, LINK, TOP, AVAIL, ITEM) This procedure pushes an ITEM into a linked stack 1. [Available space?] If AVAIL = NULL, then Write OVERFLOW and Exit 2. [Remove first node from AVAIL list] Set NEW = AVAIL and AVAIL = LINK[AVAIL]. 3. Set INFO[NEW] = ITEM [ Copies ITEM into new node) 4. Set LINK[NEW] = TOP [New node points to the original top node in the stack] 5. Set TOP = NEW [Reset TOP to point to the new node at the top of the stack] 6. Exit. Pop Algorithm in stack using Linked List POP_LINKSTACK(INFO, LINK, TOP, AVAIL, ITEM) This procedure deletes the top element of a linked stack and assigns it to the variable ITEM 1. [Stack has an item to be removed?) IF TOP = NULL then Write: UNDERFLOW and Exit. 2. Set ITEM := INFO[TOP] [Copies the top element of stack into ITEM ] 3. Set TEMP := TOP and TOP = LINK[TOP] [Remember the old value of the TOP pointer in TEMP and reset TOP to point to the next element in the stack ] 4. [Return deleted node to the AVAIL list] Set LINK(TEMPJ = AVAIL and AVAIL = TEMP. 5. Exit. Stack PUSH Operation using Linked List
0 Comments