About Stacks

Lists permit the insertion or deletion of an element to occur only at one end. A linear list belonging to this subclass is called a stack. They are also referred to as pushdown lists.

The insertion operation is referred to as PUSH and the deletion operation as POP. The most accessible element in a stack is known as the TOP of the stack.

Since insertion and deletion operations are performed at one end of stack, the elements can only be removed in the opposite order from that in which they were added to the stack. Such a linear list is frequently referred to as a LIFO ( Last-In First-Out ) LIST.  

An example of stack is the “in” tray of a busy executive. The files pile up in the tray and whenever the executive has time to clear the files, he/she takes it off from the top. That is, files are added at the top and removed from the top. Therefore stacks are sometimes referred to as LIFO structure.

A pointer TOP

A pointer TOP keeps track of the top element in the stack. Initially when the stack is empty, TOP has a value of –1 and when the stack contains a single element, TOP has a value of 0 ( Zero ) and so on. Each time a new element is inserted in the stack, the pointer is incremented by 1. The pointer decrements by 1 each time a deletion is made from the stack.

STACK STRUCTURE

D = { d , F , A }

Where,

d : Array or a node (structure)
d = { a , TOP }
Here, a : Simple array or structure

TOP : Index or Pointer

F : PUSH, POP, DISPLAY, MODIFY

A : EMPTY, OVERFLOW, UNDERFLOW

ALGORITHM : STACK

Procedure PUSH(S,TOP,X) : This procedure inserts an element X to the top of the stack which is represented by a vector S consisting MAX elements with a pointer TOP denoting the top element in the stack.

STEP 1 : [Check for stack underflow]
              If (TOP>=max-1)
              then write(stack overflow)
               Return
STEP 2 : [Increment TOP]
              TOP <-- TOP+1
STEP 3 : [Insert element]
              S[TOP] <-- X
STEP 4 : [Finished]
               Return

The first step of this algorithm checks for an overflow condition. If such a condition exists, then the insertion can't be performed and an appropriate error message results.

Procedure POP(S,TOP,X) : This procedure removes top element from the stack.
STEP 1 : [Check for the underflow on stack]
              If (TOP<0)
              then write(stack underflow)  
              Return
STEP 2 : [Hold the former top element of stack into X]
               X <-- S[TOP]
STEP 3 : [Decrement the TOP pointer or index by 1]
              TOP <-- TOP-1
STEP 4 : [finished-Return the popped item from the stack]
              Return(X)

As Underflow condition is checked for in the first step of the algorithm. If such a condition exists, then the deletion cannot be performed and an appropriate error message results.

Procedure Display(S,TOP) : This procedure displays the contents of the stack i.e., vector S.

STEP 1 : [check for empty on stack]
              if (TOP==-1)
              then write('stack empty')
              Return
STEP 2 : [Repeat through STEP 3 from i=TOP to 0]
              Repeat through STEP 3 for i=TOP to 0 STEP-1]
STEP 3 : [Display the stack content]
              write (S[i])
STEP 4 : [Finished]
              Return

The first step of this algorithm checks for an empty condition. If such a condition exists, then the contents of the stack cannot be displayed and an appropriate error message results.

Complete Source code of Stack written in C.