Amu_Ke_Fundye

Stacks

A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the TOP of the stack. It is a LIFO (Last In First Out) kind of data structure.

Operations on Stack

• Push: Adds an item onto the stack. PUSH (s, i); Adds the item i to the top of stack.
• Pop: Removes the most-recently-pushed item from the stack. POP (s); Removes the top element and returns it as a function value.
• size(): It returns the number of elements in the queue.
• isEmpty(): It returns true if queue is empty.

Implementation of Stack

A stack can be implemented in two ways: Using Array and Using Linked list.

But since array sized is defined at compile time, it can’t grow dynamically. Therefore, an attempt to insert/push an element into stack (which is implemented through array) can cause a stack overflow situation, if it is already full.

Go, to avoid the above mentioned problem we need to use linked list to implement a stack, because linked list can grow dynamically and shrink at runtime.

1. Push and Pop Implementation Using Array:

void push( ) {
if(top==max)
printf(“\nOverflow”);
else {
int element;
printf(“\nEnter Element:”);
scanf(“%d”,&element);
printf(“\nElement(%d) has been pushed at %d”, element, top);
stack[top++]=element;
}
}

void pop( ) {
if(top==-1)
printf(“\nUnderflow”);
else
{
top–;
printf(“\nELement has been popped out!”);
}
}

2. Push and Pop Implementation Using Linked List:

struct node {
int data;
struct node *prev;
}*top=NULL, *temp=NULL;

void push( ) {
temp = (struct node*)malloc(sizeof(struct node*));
printf(“\nEnter Data:”);
scanf(“%d”,&temp->data);
temp->prev=NULL;
if(top==NULL) {
top=temp;
}
else {
temp->prev=top;
top=temp;
}
}

void pop( ) {
temp=top->prev;
top=temp;
printf(“\nDeleted: %d”,top->prev);
}

Applications of Stack

• Backtracking: This is a process when you need to access the most recent data element in a series of elements.
• Depth first Search can be implemented.
• The function call mechanism.
• Simulation of Recursive calls: The compiler uses one such data structure called stack for implementing normal as well as recursive function calls.
• Parsing: Syntax analysis of compiler uses stack in parsing the program.
• Web browsers store the addresses of recently visited sites on a stack.
• The undo-mechanism in an editor.
• Expression Evaluation: How a stack can be used for checking on syntax of an expression.
  • Infix expression: It is the one, where the binary operator comes between the operands. 
    e. g., A + B * C.
  • Postfix expression: Here, the binary operator comes after the operands.
    e.g., ABC * +
  • Prefix expression: Here, the binary operator proceeds the operands. 
    e.g.,+ A * BC
  • This prefix expression is equivalent to A + (B * C) infix expression. Prefix notation is also known as Polish notation. Postfix notation is also known as suffix or Reverse Polish notation.
• Reversing a List: First push all the elements of string in stack and then pop elements.
• Expression conversion: Infix to Postfix, Infix to Prefix, Postfix to Infix, and Prefix to Infix
• Implementation of Towers of Hanoi
• Computation of a cycle in the graph

Example-1: Implementation of Towers of Hanoi

Let A, B, and C be three stacks. Initially, B and C are empty, but A is not.
Job is to move the contents of A onto B without ever putting any object x on top of another object that was above x in the initial setup for A.

void TOH (int n, Stack A, Stack B, Stack C) {
if (n == 1) B.push (A.pop());
else {
TOH (n – 1, A, C, B); // n-1 go from A onto C
B.push (A.pop());
TOH (n – 1, C, B, A); // n-1 go from C onto B
}
}

Example-2: Evaluate the following postfix notation of expression: 15 3 2 + / 7 + 2 *

 Regards 

Amrut Jagdish Gupta