STACK

What is a Stack?
A stack is a linear structure in which items may be added or removed only at one end.
Everyday examples of such a structure: a stack of dishes, a stack of pennies and a stack of
folded towels. Observe that an item may be added or removed only from the top of any of
the stacks. This means, in particular, that the last item to be added to a stack is the first item
to be removed. Accordingly, stacks are also called last-in first-out (LIFO) lists. Other names
used for stacks are "piles" and "push-down lists."
Definitions:
A stack is a list of elements in which an element may be inserted or deleted only at one
end, called top of the stack. This means, in particular, that elements are removed from a
stack in the reverse order of that in which they were inserted into the stack.
Special terminology is used for two basic operations associated with stacks:

(a) "Push" is the term used to insert an element into a stack.

(b) "Pop" is the term used to delete an element from a stack.

Postponed Decisions
Stacks are frequently used to indicate the order of the processing of data when certain steps
of the processing must be postponed until other conditions are fulfilled. This is illustrated as
follows.
Suppose that while processing some project A we are required to move on to project B,
whose completion is required in order to complete project A. Then we place the folder
containing the data of A onto a stack, as pictured in Fig. (a), and begin to process B.
However, suppose that while processing B we are led to project C, for the same reason. Then
we place B on the stack above A, as pictured in Fig. (b), and begin to process C.
Furthermore, suppose that while processing C we are likewise led to project D. Then we
place C on the stack above B, as pictured in Fig. (c), and begin to process D.

On the other hand, suppose we are able to complete the processing of project D. Then the
only project we may continue to process is project C, which is on top of the stack. Hence we
remove folder C from the stack, leaving the stack as pictured in Fig. (d), and continue to
process
C. Similarly, after completing the processing of C, we remove folder B from the stack,
leaving the stack as pictured in Fig. (e), and continue to process B. Finally, after completing

Instructor: Deepak Sharma (9873600359) Page 1

the processing of B, we remove the last folder, A, from the stack, leaving the empty stack
pictured in Fig. ( f), and continue the processing of our original project A.

MEMORY REPRESENTATION OF STACKS:-

There are two types of representation:-

1. Array Representation.
2. Linked List Representation.

ARRAY REPRESENTATION OF STACKS [Static Representation]

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 = -1 will indicate that the stack is
empty.
The operation of adding (pushing) an item onto a stack and the operation of removing
(popping) an item from a stack may be implemented, respectively, by the following
procedures, called PUSH and POP. In executing the procedure PUSH, one must first test
whether there is room in the stack for the new item; if not, then we have the condition known
as overflow. Analogously, in executing the procedure POP, one must first test whether there
is an element in the stack to be deleted; if not, then we have the condition known as
underflow.
Algorithm for inserting an element into a stack using Array [Algorithm for PUSH
operation using Array]:-
Push ( ):
Description: Here STACK is an array with MAX locations. TOP points to the top most
element and ITEM is the value to be inserted.
1. If (TOP == MAX - 1) Then [Check for overflow]
2. Print: Overflow
3. Else
4. Set TOP = TOP + 1 [Increment TOP by 1]
5. Set STACK[TOP] = ITEM [Assign ITEM to top of
STACK]
6. Print: ITEM
inserted [End of
If]
7. Exit

Algorithm for deleting an element from a stack using Array [Algorithm for POP
operation using Array]:-
Pop ( ):
Description: Here STACK is an array with MAX locations. TOP points to the top
most element.
1. If (TOP == -1) Then [Check for underflow]
2. Print: Underflow

Instructor: Deepak Sharma (9873600359) Page 2

3. Else
4. Set ITEM = STACK[TOP] [Assign top of STACK to ITEM]
5. Set TOP = TOP - 1 [Decrement TOP by 1]
6. Print: ITEM
deleted [End of If]
7. Exit

Implementation of STACK using Array representation:-

/*Operations performed on Stack using Arrays*/
#include<stdio.h>
#include<conio.h>
#define MAXSIZE 10
void push();
int pop();
void traverse();
int stack[MAXSIZE];
int Top=-1;

void main()
{
int choice; char ch;
do
{
clrscr();
printf("\n1. PUSH ");
printf("\n2. POP ");
printf("\n3. TRAVERSE ");
printf("\nEnter your choice");
scanf("%d",&choice);
switch(choice)
{
case 1: push();
break;
case 2: printf("\nThe deleted element is %d",pop());
break;
case 3: traverse();
break;
default: printf("\nYou Entered Wrong Choice");
}
printf("\nDo You Wish To Continue (Y/N)");
fflush(stdin);
scanf("%c",&ch);
}
while(ch=='Y' || ch=='y');
}

Instructor: Deepak Sharma (9873600359) Page 3

void push()
{
int item;
if(Top == MAXSIZE - 1)
{
printf("\nThe Stack Is Full");
getch();
exit(0);
}
else
{
printf("Enter the element to be inserted");
scanf("%d",&item);
Top= Top+1;
stack[Top] = item;
}
}
int pop()
{
int item;
if(Top == -1)
{
printf("The stack is Empty");
getch();
exit(0);
}
else
{
item = stack[Top];
Top = Top-1;
}
return(item);
}
void traverse()
{
int i;
if(Top == -1)
{
printf("The Stack is
Empty"); getch();
exit(0);
}
e
l
s

Instructor: Deepak Sharma (9873600359) Page 4

 e
{
for(i=Top;i>=0;i--)
{
printf("Traverse the
element");
printf("\n%d",stack[i]);
}
}
}

LINKED REPRESENTATION OF STACKS:-

Another way to represent stack in memory is linked list representation or Dynamic
representation. In this representation we need a pointer Variable TOP, which contains the
location of the top element of the stack; and we do not need to check for the overflow
condition in this representation because of dynamic nature of linked list. The condition TOP
= NULL will indicate that the stack is empty [underflow condition].
Algorithm for inserting an element into a stack using Linked List [Algorithm for
PUSH operation using Linked List]:-

Push ( ): Adding a new element on the top of STACK.

Description: Here STACK is a linked list without any fixed location and we don’t need to
check overflow condition. TOP is a node pointer points to the top most element(i.e. node)
and ITEM is the value to be inserted. TEMP is a temporary node pointer.
1. Allocate memory to TEMP.
2. If (TEMP == NULL) [If memory is not available (Overflow)]
3. Print: STACK is full.
4. else
5. TEMP->data = ITEM [Allocate ITEM to data part of TEMP]
6. TEMP->link=TOP [Assign TOP to link part of TEMP]
7. TOP=TEMP [Change the value of TOP by TEMP]
[End of If]
8. Exit

Algorithm for deleting an element from a stack using Linked List [Algorithm for POP
operation using Linked List]:-

Pop ( ): Deleting an element from the top of STACK.

Description: Here STACK is a linked list without any fixed location. TOP is a node
pointer points to the top most element(i.e. node) and ITEM is the value to be deleted.
TEMP is a temporary node pointer. STACK is empty[underflow condition] when TOP
is NULL.

1. If (TOP == NULL) [Underflow]

2. Print: STACK is Empty.

Instructor: Deepak Sharma (9873600359) Page 5

3. else
4. TEMP = TOP
5. ITEM = TEMP->data [Allocate data part of TEMP to ITEM]
6. TOP = TOP->link [Assign link part of next node to TOP]
7. Release memory allocated to TEMP
[End of If]
8. Exit
Implementation of Stack Using Linked List:-
#include <stdio.h>
struct node
{
int info;
struct node *link;
};
void push ( struct node **, int ) ;
int pop ( struct node ** ) ;
void display(struct node **);

void main()
{
struct node *top = NULL ;
int ch, item;
do
{
printf("\n\n1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1:
printf("\nEnter value to be inserted: ");
scanf("%d", &item);
push(&top, item);
break;
case 2:
item=pop(&top);
printf ( "\n Item popped: %d", item) ;
break;
case 3:
display(&top);
break;
case 4:
exit(0);

Instructor: Deepak Sharma (9873600359) Page 6

default:
printf("Invalid choice. Please try again.\n");
}
} while(1);
getch();
}
/* adds a new node to the stack as linked list [PUSH Operation] */
void push ( struct node **top, int item )
{
struct node *temp ;
temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
if ( temp == NULL )
printf ( "\nStack is full." ) ;
temp -> data = item ;
temp -> link = *top ;
*top = temp ;
}
/* pops an element from the stack */
int pop ( struct node **top )
{
struct node *temp ;
int item ;
if ( *top == NULL )
{
printf ( "\nStack is empty." ) ;
return NULL ;
}
temp = *top ;
item = temp -> data ;
*top = (*top ) -> link ;
free ( temp ) ;
return item ;
}
void display(struct node *top)
{
struct node *ptr;
if (top == NULL)
printf("\n\nStack is empty\n");

Instructor: Deepak Sharma (9873600359) Page 7

else
{
ptr = top;
while(ptr != NULL)
{
printf("\n\n%d", ptr->info);
ptr = ptr->link;
}
}
}

Instructor: Deepak Sharma (9873600359) Page 8

APPLICATION OF STACKS: POLISH NOTATION
For most common arithmetic operations, the operator symbol is placed between its two
operands. For example,
A+B, C-D, E*F, G/H

This is called infix notation. With this notation, we must distinguish

between (A+B)*C and A + (B * C)
by using either parentheses or some operator-precedence convention such as the usual
precedence levels discussed above. Accordingly, the order of the operators and operands in
an arithmetic expression does not uniquely determine the order in which the operations are to
be performed.
Polish notation, named after the Polish mathematician Jan Lukasiewicz, refers to the
notation in which the operator symbol is placed before its two operands. For example,
+AB -CD *EF /GH

We translate, step by step, the following infix expressions into Polish notation using brackets
[ ] to indicate a partial translation:
(A + B) *C= [+AB]*C =
*+ABC A + (B*C) = A +
[*BC] = +A*BC
(A + B) / (C - D) = [+ AB] / [ - CD] = / + AB - CD

The fundamental property of Polish notation is that the order in which the operations are to
be performed is completely determined by the positions of the operators and operands in the
expression. Accordingly, one never needs parentheses when writing, expressions in Polish
notation.
Reverse Polish notation refers to the analogous notation in which the operator symbol is
placed after its two operands:
AB+, CD-, EF*, GH/

Again, one never needs parentheses to determine the order of the operations in any
arithmetic expression written in reverse Polish notation. This notation is frequently called
postfix (or suffix) notation, whereas prefix notation is the term used for Polish notation,
discussed in the preceding paragraph.
The computer usually evaluates an arithmetic expression written in infix notation in two
steps. First, it converts the expression to postfix notation, and then it evaluates the postfix
expression. In each step, the stack is the main tool that is used to accomplish the given task.
Algorithm for Converting Infix to Postfix Notation:-
Let Q be an arithmetic expression written in infix notation. Besides operands and
operators, Q may also contain left and right parentheses. We assume that the operators in Q
consist only of exponentiations (↑), multiplications (*), divisions (/), additions (+) and
subtractions (-), and that they have the usual three levels of precedence as given below:
1. exponentiations (↑)
2. multiplications (*), divisions (/)
3. additions (+) and subtractions (-)

We also assume that operators on the same level, including exponentiations, are

Instructor: Deepak Sharma (9873600359) Page 9

performed from left to right unless otherwise indicated by parentheses.
The following algorithm transforms the infix expression Q into its equivalent postfix
expression P. The algorithm uses a stack to temporarily hold operators and left parentheses.
The postfix expression P will be constructed from left to right using the operands from Q and
the operators, which are removed from STACK. We begin by pushing a left parenthesis
onto STACK and adding a right parenthesis at the end of Q. The algorithm is completed
when STACK is empty.
Description: Here Q is an arithmetic expression written in infix notation and P is the
equivalent postfix expression generated by this algorithm.

1. Push “(“ left parenthesis onto stack.

2. Add “)” right parenthesis to the end of expression Q.
3. Scan Q from left to right and repeat step 4 for each element of Q until the stack
becomes empty.
4. If the scanned element is:
(a) an operand then add it to P.
(b) a left parenthesis then push it onto stack.
(c) an operator then:
(i) Pop from stack and add to P each operator which has the same or higher
precedence then the scanned operator.
(ii) Add newly scanned operator to stack.
(d) a right parenthesis then:
(i) Pop from stack and add to P each operator until a left parenthesis is
encountered.
(ii) Remove the left parenthesis.
[End of Step 4 If]
[End of step 3 For Loop]
5. Exit.

Instructor: Deepak Sharma (9873600359) Page 10

EXAMPLE : Convert the following infix expression Q into equivalent postfix notation

Q: A+(B*C- (D/E↑F)*G)*H

Final Postfix expression is : A B C * D E F ↑ / G * - H * +

Evaluation of a Postfix Expression:

Suppose P is a arithmetic expression written in postfix notation. The following algorithm,
which uses a STACK to hold operands, evaluates P.

Evaluate ( ):
Description: Here P is a postfix expression and this algorithm evaluates it.

1. Add a “)” right parenthesis at the end of P.

2. Scan P from left to right and repeat steps 3 & 4 for each element of P until “)” is
encountered.
3. If an operand is encountered, push it onto stack.
4. If an operator opr is encountered then:
(a) Pop the top two elements from stack, where A is the top element and B is the

Instructor: Deepak Sharma (9873600359) Page 11

 next to top element.
(b) Evaluate B opr A.
(c) Place the result of (b) back on
stack. [End of Step 4 If]
[End of step 2 For Loop]
5. Set VALUE equal to the top element on the stack.
6. Exit.

Example: Consider the following arithmetic expression P written in postfix

notation: P : 5, 6, 2, +, *, 12, 4, /, -, )

Convert the following from Infix to Postfix Expression.

1. (A-B) * (D/E)
2. (A + B ^ D) / ( E – F ) + G
3. A * ( B + D ) / E – F * ( G + H / K)
4. 12 / ( 7 – 3 ) + 2 * ( 1 + 5 )
5. (( A + B) * D) ^ (E – F)
6. (A-B) /((D+E) * F)
7. ((A+B)/D) $ ((E – F) * G)
8. 5 + 3 $ 2 – 8 / 4 * 3 +6
9. 6 + 2 $ 3 + 9 / 3 - 4 * 5
10. 4 $ 2 * 3 - 3 + 8 / 4 / ( 1 + 1 )
11. ( A + B ^ D) / ( E – F) + G
12. ( A + B ) * ( C $ ( D – E ) + F ) / G $ ( H – J )
NOTE :- After converting the infix to postfix expression. Evaluate the postfix
expression for expression number 4, 8, 9, 10.

Instructor: Deepak Sharma (9873600359) Page 12

 NOTE:- Solution of all of the above questions are discussed in class, do as per class
notes.

NOTE: Applications of STACK are

 Converting Infix to Postfix Notation.

 Evaluation of a Postfix Expression.
 Recursion.
Convert the Following expression into equivalent Prefix expression

Given Expression is : 5 + 3 $ 2 – 8 / 4 * 3 +6

Direction: Right to Left

S. Symbol Operator Stack Final Prefix Expression(P)

No. Scanned

1 6 Empty 6

2 + + 6

3 3 + 36

4 * +* 36

5 4 +* 436

6 / + */ 436

7 8 + */ 8436

8 - +- */8436

9 2 +- 2*/8436

10 $ +-$ 2*/8436

11 3 +-$ 32*/8436

12 + +-+ $32*/8436

13 5 +-+ 5$32*/8436

14 Empty Empty + - + 5$32*/8436

Instructor: Deepak Sharma (9873600359) Page 13

Alternate Method [Verification Method]:-
5+3$2–8/4*3+6
= 5 + [$32] – 8 / 4 * 3 + 6
= 5 + [$32] – [/84] * 3 + 6
= 5 + [$32] – [*/843] + 6
= [+5$32] – [*/843] + 6
= [ – + 5$32*/843] + 6
=+–+5$32*/8436
Evaluate the following Prefix Expression:-
+–+5$32*/8436
S. No. Symbol Final Stack
Scanned
1 6 6

2 3 6,3

3 4 6 , 3, 4

4 8 6 , 3, 4, 8

5 / 6 , 3, 2

6 * 6, 6

7 2 6, 6, 2

8 3 6, 6, 2, 3

9 $ 6, 6, 9

10 5 6, 6, 9, 5

11 + 6, 6, 14

12 - 6, 8

13 + 14 [Final Vaue]

Instructor: Deepak Sharma (9873600359) Page 14

/* Program to copy the contents of one stack into another stack */
#include <stdio.h>
#include <conio.h>
#define MAX 10
struct stack
{
int arr[MAX] ;
int top ;
};

void initstack ( struct stack * ) ;

void push ( struct stack *, int item ) ;
int pop ( struct stack * ) ;

void main( )
{
struct stack s, temp, final;
int i ;
clrscr( ) ;
initstack ( &s ) ; initstack ( &temp ) ; initstack ( &final ) ;
push ( &s, 11 ) ; push ( &s, 23 ) ; push ( &s, -8 ) ; push ( &s, 16 ) ;
push ( &s, 27 ) ; push ( &s, 14 ) ; push ( &s, 20 ) ; push ( &s, 39 ) ;
push ( &s, 2 ) ; push ( &s, 15 ) ;
printf("Elements of Source Stack are:\n");
for(i=s.top; i >= 0; i--)
{
printf("%d\t",s.arr[i]);
}
while(s.top >= 0)
{
i = pop ( &s ) ;
push ( &temp, i ) ;
}
printf("Elements of Intermediate Stack are:\n");
for(i=temp.top; i >= 0; i--)
{
printf("%d\t", temp.arr[i]);
}
while(temp.top >= 0)
{
i = pop ( &temp ) ;
push ( &final, i ) ;
}
printf("Elements of Destination Stack are:\n");
for(i=final.top; i >= 0; i--)
{
Instructor: Deepak Sharma (9873600359) Page 15
 printf("%d\t",final.arr[i]);
}
getch( ) ;
}

/* intializes the stack */

void initstack ( struct stack *s )
{
s -> top = -1 ;
}
/* adds an element to the stack */
void push ( struct stack *s, int item )
{
if ( s -> top == MAX - 1 )
{
printf ( "\nStack is full." ) ;
return ;
}
s -> top++ ;
s -> arr[s ->top] = item ;
}

/* removes an element from the stack */

int pop ( struct stack *s )
{
int data ;
if ( s -> top == -1 )
{
printf ( "\nStack is empty." ) ;
return NULL ;
}
data = s -> arr[s -> top] ;
s -> top-- ;
return data ;
}

Instructor: Deepak Sharma (9873600359) Page 16