Stack is a linear data structure where the elements could be inserted or retrieved only at one end, called the ‘top’ of the stack. Stack implements “First In Last Out/ Last In First Out” (FILO/ LIFO) order on its data elements, that is elements inserted first into the stack would be retrieved last from the stack or vice-versa.

Inserting an element into a stack is called ‘push’ , retrieving an element from the stack is termed as pop operation.

Algorithm for push and pop operations on a stack.

Stack s is an array of size element top is the position/index of last inserted element initially top =-1
Push operation on a stack

1.START Push (Element e)
2.If top = size -1 Then          ( If top is the last element index)
3.Display “STACK OVERFLOW”
4.Goto END
5.END If
6.top:=top+1                         (Increment the ‘top’ of the Stack s by 1)
7.s[top]:=e                             (assign the element at the ‘top’ position of the Stack)
8.END PUSH

Pop operation on a stack

1.START POP()
2.If top=-1 Then
3.Display “STACK UNDERFLOW”
4.Goto END
5.END If
6.Element e:=s[top]
7.top:=top-1                           (Decrement the ‘top’ of the Stack s by 1)
8.Return e
9.END POP

/************** C – Implementation of Stack ************************/

The code for implementing stack :- Stack

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define size 6

int stack[size];
int top=-1;

void push(int val)
{
if(top ==size-1)
printf(“stack overflow\n”);

else
{
top++;
stack[top]=val;
printf(“the value is pushed\n”);
}
}

int pop()
{
int value;

if(top==-1)
{
//printf(“stact underflow\n”);
return -9999;
}

else
{
value= stack[top];
top–;
return value;             //return stack[top–];
}
}

void display()
{
int i;
printf(“\nstack\n”);
for(i=top;i>=0;i–)
{
printf(“%d\n”,stack[i]);
}
printf(“\n\n”);
}

void main()
{
int value,choice;
clrscr();
while(1)
{
printf(” press 1 for Push\n press 2 for pop\n press 3 for display\n press 4 for exit\n\n”);
printf(“\nenter your choice:”);
scanf(“%d”,&choice);

switch(choice)
{
case 1:
printf(“enter the value which is to be pushed\n”);
scanf(“%d”,&value);
push(value);
break;

case 2:
value= pop();
if (value== -9999 && top == -1)
printf(“stack underflow\n\n\n”);
else
printf(“the poped data is %d\n”,value);

break;

case 3:
display();
break;

case 4:
exit(0);
break;

default: printf(“invalid choice\n”);

}//end of switch
}//end of while
//return 0;
getch();
}

/************** C – Implementation of Stack ************************/

Algorithm for push and pop operations on a stack.

Let us consider the following stack type.

type STACK is [

ELEMENT ITEM[SIZE]

INTEGER TOP

]

Let S is a STACK of SIZE = 100 elements, initially S.top:=-1

Push operation on a stack

1.START PUSH (STACK S, ELEMENT e)

2.IF  S.TOP := SIZE-1 THEN

3.DISPLAY “STACK OVERFLOW”

4.GOTO END

5.END IF

6.  S.TOP := S.TOP + 1                            //INCREMENT THE TOP OF THE STACK S BY 1

7.S.ITEM [S.TOP] : = e                          //ASSIGN THE ELEMENT AT THE TOP POSITION OF THE STACK

8.END OPERATION PUSH

Pop operation on a stack

1.START POP (STACK S)

2.IF S.TOP = -1 THEN

3.DISPLAY “STACK UNDERFLOW”

4.GOTO END

5.END IF

6.ELEMENT e:=S.ITEM[S.TOP]

7.S.TOP:=S.TOP-1                             //DECREMENT THE TOP OF THE STACK S BY 1

8.RETURN e

9.END OPERATION POP

/********** C – Implementation of Stack Using Pointer ***************/

The code for implementing stack :- StackUsingPointer

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define size 6

typedef struct
{
int item[size];
int top;
}Stack;

void push(Stack *sp,int val)
{
if(sp->top ==size-1)
printf(“stack overflow\n”);

else
{
sp->top++;
sp->item[sp->top]=val;
printf(“the value is pushed\n”);
}
}

int pop(Stack *sp)
{
int value;

if(sp->top==-1)
{
//printf(“stact underflow\n”);
return -9999;
}

else
{
value= sp->item[sp->top];
sp->top–;
return value;
}
}

void display(Stack *sp)
{
int i;
printf(“\nstack\n”);
for(i=sp->top;i>=0;i–)
{
printf(“%d\n”,sp->item[i]);
}
}

void main()
{
Stack s;
int value,choice;
s.top=-1;
clrscr();
while(1)
{
printf(” press 1 for Push\n press 2 for pop\n press 3 for display\n press 4 for exit\n\n”);
scanf(“%d”,&choice);

switch(choice)
{
case 1:
printf(“enter the value which is to be pushed\n”);
scanf(“%d”,&value);
push(&s,value);
break;

case 2:
value= pop(&s);
if (value== -9999 && s.top == -1)
printf(“stack underflow\n\n\n”);
else
printf(“the poped data is %d\n”,value);

break;

case 3:
display(&s);
break;

case 4:
exit(0);
break;

default: printf(“invalid choice\n”);

}//end of switch
}//end of while
//return 0;
getch();
}

/********** C – Implementation of Stack Using Pointer ***************/

Applications of Stack :-

Three applications of stacks are presented here.

  1. Expression evaluation
  2. Backtracking (game playing, finding paths, exhaustive searching)
  3. Memory management, run-time environment for nested language features.

Expression evaluation

In particular we will consider arithmetic expressions.  Understand that there are boolean and logical expressions that can be evaluated in the same way.  Control structures can also be treated similarly in a compiler.

This study of arithmetic expression evaluation is an example of problem solving where you solve a simpler problem and then transform the actual problem to the simpler one.

Aside: The NP-Complete problem. There are a set of apparently intractable problems: finding the shortest route in a graph (Traveling Salesman Problem), bin packing, linear programming, etc. that are similar enough that if a polynomial solution is ever found (exponential solutions abound) for one of these problems, then the solution can be applied to all problems.

Infix, Prefix and Postfix Notation

We are accustomed to write arithmetic expressions with the operation between the two operands: a+b or c/d.  If we write a+b*c, however, we have to apply precedence rules to avoid the ambiguous evaluation (add first or multiply first?).

There’s no real reason to put the operation between the variables or values.  They can just as well precede or follow the operands.  You should note the advantage of prefix and postfix: the need for precedence rules and parentheses are eliminated.

Infix Prefix Postfix
a + b + a b a b +
a + b * c + a * b c a b c * +
(a + b) * (c – d) * + a b – c d a b + c d – *
b * b – 4 * a * c
40 – 3 * 5 + 1

Postfix expressions are easily evaluated with the aid of a stack.

Postfix Evaluation Algorithm

Assume we have a string of operands and operators, an informal, by hand process is

  1. Scan the expression left to right
  2. Skip  values or variables (operands)
  3. When an operator is found, apply the operation to the preceding two operands
  4. Replace the two operands and operator with the calculated value (three symbols are replaced with one operand)
  5. Continue scanning until only a value remains–the result of the expression

The time complexity is O(n) because each operand is scanned once, and each operation is performed once.

A more formal algorithm:

create a new stack
while(input stream is not empty){
   token = getNextToken();
   if(token instanceof operand){
       push(token);
   } else if (token instance of operator)
       op2 = pop();
       op1 = pop();
       result = calc(token, op1, op2);
       push(result);
   }
}
return pop();

Demonstration with 2 3 4 + * 5 –

Infix transformation to Postfix

This process uses a stack as well.  We have to hold information that’s expressed inside parentheses while scanning to find the closing ‘)’. We also have to hold information on operations that are of lower precedence on the stack.  The algorithm is:

  1. Create an empty stack and an empty postfix output string/stream
  2. Scan the infix input string/stream left to right
  3. If the current input token is an operand, simply append it to the output string (note the examples above that the operands remain in the same order)
  4. If the current input token is an operator, pop off all operators that have equal or higher precedence and append them to the output string; push the operator onto the stack.  The order of popping is the order in the output.
  5. If the current input token is ‘(‘, push it onto the stack
  6. If the current input token is ‘)’, pop off all operators and append them to the output string until a ‘(‘ is popped; discard the ‘(‘.
  7. If the end of the input string is found, pop all operators and append them to the output string.

This algorithm doesn’t handle errors in the input, although careful analysis of parenthesis or lack of parenthesis could point to such error determination.

Apply the algorithm to the above expressions.

Backtracking

Backtracking is used in algorithms in which there are steps along some path (state) from some starting point to some goal.

  • Find your way through a maze.
  • Find a path from one point in a graph (roadmap) to another point.
  • Play a game in which there are moves to be made (checkers, chess).

In all of these cases, there are choices to be made among a number of options.  We need some way to remember these decision points in case we want/need to come back and try the alternative

Consider the maze.  At a point where a choice is made, we may discover that the choice leads to a dead-end.  We want to retrace back to that decision point and then try the other (next) alternative.

Again, stacks can be used as part of the solution.  Recursion is another, typically more favored, solution, which is actually implemented by a stack.

Memory Management

Any modern computer environment uses a stack as the primary memory management model for a running program.  Whether it’s native code (x86, Sun, VAX) or JVM, a stack is at the center of the run-time environment for Java, C++, Ada, FORTRAN, etc.

The discussion of JVM in the text is consistent with NT, Solaris, VMS, Unix runtime environments.

Each program that is running in a computer system has its own memory allocation containing the typical layout as shown below.

Call and return process

When a method/function is called

  1. An activation record is created; its size depends on the number and size of the local variables and parameters.
  2. The Base Pointer value is saved in the special location reserved for it
  3. The Program Counter value is saved in the Return Address location
  4. The Base Pointer is now reset to the new base (top of the call stack prior to the creation of the AR)
  5. The Program Counter is set to the location of the first bytecode of the method being called
  6. Copies the calling parameters into the Parameter region
  7. Initializes local variables in the local variable region

While the method executes, the local variables and parameters are simply found by adding a constant associated with each variable/parameter to the Base Pointer.

When a method returns

  1. Get the program counter from the activation record and replace what’s in the PC
  2. Get the base pointer value from the AR and replace what’s in the BP
  3. Pop the AR entirely from the stack.

Towers of Hanoi

Towers of Hanoi

One of the most interesting applications of stacks can be found in solving a puzzle called Tower of Hanoi. According to an old Brahmin story, the existence of the universe is calculated in terms of the time taken by a number of monks, who are working all the time, to move 64 disks from one pole to another. But there are some rules about how this should be done, which are:

  1. move only one disk at a time.
  2. for temporary storage, a third pole may be used.
  3. a disk of larger diameter may not be placed on a disk of smaller diameter.

Assume that A is first tower, B is second tower & C is third tower.

Towers of Hanoi step 1

Towers of Hanoi step 2

Towers of Hanoi step 3

Towers of Hanoi step 4

Tower of Hanoi

Output: (when there are 3 disks)

Let 1 be the smallest disk, 2 be the disk of medium size and 3 be the largest disk.

Move disk From peg To peg
1 A C
2 A B
1 C B
3 A C
1 B A
2 B C
1 A C

The C++ code for this solution can be implemented in two ways:

First implementation (using stacks implicitly by recursion)

#include <stdio.h>

void TowersofHanoi(int n, int a, int b, int c)
{
    if(n > 0)
    {
        TowersofHanoi(n-1, a, c, b);   //recursion
        printf("> Move top disk from tower %d to tower %d.\n", a, b);
        TowersofHanoi(n-1, c, b, a);   //recursion
    }
}

Second implementation (using stacks explicitly)

// Global variable , tower [1:3] are three towers
arrayStack<int> tower[4];

void TowerofHanoi(int n)
{
    // Preprocessor for moveAndShow.
    for (int d = n; d > 0; d--)        //initialize
        tower[1].push(d);              //add disk d to tower 1
    moveAndShow(n, 1, 2, 3);           /*move n disks from tower 1 to tower 3 using 
                                       tower 2 as intermediate tower*/  
}

void moveAndShow(int n, int a, int b, int c)
{
    // Move the top n disks from tower a to tower b showing states.
    // Use tower c for intermediate storage.
    if(n > 0)
    {
        moveAndShow(n-1, a, c, b);     //recursion
        int d = tower[a].top();        //move a disc from top of tower x to top of 
        tower[a].pop();                //tower y
        tower[c].push(d);
        showState();                   //show state of 3 towers
        moveAndShow(n-1, b, a, c);     //recursion
    }
}

However complexity for above written implementations is O(2^n). So it’s obvious that problem can only be solved for small values of n (generally n <= 30).

In case of the monks, the number of turns taken to transfer 64 disks, by following the above rules, will be 18,446,744,073,709,551,615; which will surely take a lot of time!

Advertisements