UNIT - II - Stacks

Data structures Lecture Notes Unit - II
UNIT – II
Stacks and Queues
2.1. STACKS:
A Stack is a linear list in which all additions and deletions are restricted to one end called to
top.
 It is also known as restrictive data structure.
 If you insert a data series into a stack and then remove it, the order of the data is reversed.
Data input as {5,10,15,20} is removed as {20,15,10,5}
 This reversing attribute is why stacks are known as the Last in First Out (LIFO) data
structure.
 Any situation we can add or remove an object at the top is a stack.
 If you want to remove any object other than the one at the top, you must first remove all
objects above it.
 A graphic representation of stack is shown in fig.
Definition:
A stack is a last – in – first – out (LIFO) data structure in which all insertions and deletions are
restricted to one end, called the top.
2.1.1 Basic Operations:

Three basic operations are push, pop, and stack top.
a. Push: It is used to insert data into the stack.
b. Pop: removes data from a stack and returns the data to the calling module.
c. Stack top: returns the data at the top of the stack without deleting the data from the stack.
a. Push:
 Push adds an item at the top of the stack
 After the push, the new item becomes the top
 The only problem with this simple operation is that there is room for the new item
 If there is not enough room, the stack is an overflow state and the item cannot be added.
 Figure shows the push stack operation
1
Prepared by: G. B. Hima Bindu, Asst. Prof., Dept. of IT, SVCET, CTR
b. Pop:
 When we pop a stack, we remove the item at the top of the stack and return it to the user.
 After removing the top item, the next older item in the stack becomes the top.
 When the last item in the stack is deleted, the stack must be set to its empty state.
 If pop is called when the stack is empty, it is in an underflow state.
 The pop stack operation is shown in fig.
c. Stack top:
 The stack top copies the item at the top of the stack; that is, it returns the data in top element
to the user but does not delete it.
 This operation is nothing but as reading the stack top.
 Stack top can also result in underflow if the stack is empty.
 The stack top operation is shown in figure.
2
3
2.1.2. Array representations of stacks:

Several data structures can be used to implement a stack. Here we implement a stack as an
array.
a. Pushing:
 Initially consider the elements in the stack are: 17, 23, 97, now top = 2 or count = 3
 After pushing the element 44 into the stack the top or count will be incremented by 1, then top = 3
or count = 4.
 For every push operation the top or count will be incremented by 1.
0 1 2 3 4 5 6 7
stack: 17 8
23 97 9 44
top = 3 or count = 4
 If the bottom of the stack is at location 0, then an empty stack is represented by top = -1 or count =
0
 To add (push) an element, either:
o Increment top and store the element in stack[top], or
o Store the element in stack[count] and increment count
b. Popping:
 To remove (pop) an element, either:
o Get the element from stack[top] and decrement top, or
o Decrement count and get the element in stack[count]
After Popping,
0 1 2 3 4 5 6 7
stack: 17 8
23 97 9 44
top = 2 or count = 3
When you pop an element, do you just leave the “deleted” element sitting in the array?
The surprising answer is, “it depends” on language.
 There are two stack errors that can occur:
o Underflow: trying to pop (or peek at) an empty stack
o Overflow: trying to push onto an already full stack
4
C Implementation:
Push operation:
int stack[MAX];
int top=-1;
void push(int ele)
{
if(top>MAX)
{
printf(“stack is full\n”);
exit(0);
}
stack[++top]=ele;
}
Pop operation:
void pop()
{
if(top==-1)
{
printf(“stack is empty\n”);
exit(0);
}
a=stack[top--];
printf(“the element popped is %d”,a);
}
Display elements in stack:
void display()
{
int k;
if(top==-1)
{
printf(“stack is empty\n”);
exit(0);
}
printf("\n\tElements present in the stack are:\n\t");
for(k=0;k<=top;k++)
printf("%d\t",stack[k]);
}
5
2.1.3 Stack Applications:

 Stack applications can be classified into four broad categories:
o Reversing Data: Examples are reverse a list, to convert a decimal number to its binary
equivalent
o Parsing Data: Example is to show how to match the parentheses in a source program
o Postponing Data Usage: Examples are to convert infix to postfix notation, to evaluate a
postfix expression
o Backtracking Steps: Example to choose between two or more paths.
2.1.3.1. Reversing Data:

 Reversing data requires that a given set of data be reordered so that the first and last element are
exchanged, with all of the positions between the first and last being relatively exchanged also.
 For ex, {1 2 3 4} becomes {4 3 2 1}
 Two different reversing applications are:
o Reverse a list
o Convert decimal to binary
Reverse a list:
 One of the applications of a stack is to reverse a list of items
 For ex, reads a list of integers and prints them in reverse
 This program reverses a list of integers with the following steps;
o Read from the keyboard
o Push them into a stack
o Retrieving them one by one
Program:
#include<stdio.h>
#include<conio.h>
#define MAX 20
int top=-1;
void push(int ele);
int pop();
int emptystack();
int stkarr[MAX];
void main()
{
int ele,dele;
clrscr();
printf("enter the elements into the stack and press at last^z\n");
while((scanf("%d",&ele))!=EOF)
push(ele);
printf("The list of numbers reversed:\n");
6
while(!emptystack())
{
dele=pop();
printf("%d\t",dele);
}
getch();
}
void push(int ele)
{
if(top==MAX-1)
{
printf("stack is full\n");
exit(0);
}
stkarr[++top]=ele;
}
int pop()
{
int dele;
if(top==-1)
{
printf("stack is empty\n");
exit(0);
}
return(stkarr[top--]);
}
int emptystack()
{
if(top==-1)
return 1;
else
return 0;
}
Output:
Enter the elements into the stack and press at last ^z
56789
The list of numbers reversed:
9 8 7 6 5
Convert decimal to binary:
 The following simple code segment transfers a decimal number into a binary number:
1. read (number)
2. loop (number>0)
7
1. set digit to number modulo 2

2. print (digit)
3. set number to quotient of number/2
3. end loop
 This code has a problem, it creates the binary number backward
 Thus, 19 becomes 11001 rather than 10011
 We can solve this using a stack
 Instead of printing the binary digit as soon as it is produced, we push it into the stack
 Then after the number has been completely converted, we simply pop the stack and print the
results one digit at a time in a line
 The program is as shown
#include<stdio.h>
#include<conio.h>
#define MAX 20
int top=-1;
void push(int ele);
int pop();
int emptystack();
int stkarr[MAX];
void main()
{
int num,digit;
clrscr();
printf("enter the decimal number to be converted into binary\n");
scanf("%d",&num);
while(num>0)
{
digit=num%2;
push(digit);
num=num/2;
}
printf("The binary number is:\n");
while(!emptystack())
{
digit=pop();
printf("%d",digit);
}
getch();
}
void push(int ele)
{
8
if(top==MAX-1)
{
printf("stack is full\n");
exit(0);
}
stkarr[++top]=ele;
}
int pop()
{
int dele;
if(top==-1)
{
printf("stack is empty\n");
exit(0);
}
return(stkarr[top--]);
}
int emptystack()
{
if(top==-1)
return 1;
else
return 0;
}
Output:
Enter an integer: 45
The binary number is: 101101
2.1.3.2. Postponement
 A Stack can be useful when the application requires that the use of data be postponed for a
while.
 Two stack postpone applications are:
1. infix to postfix transformation
2. Postfix expression evaluation
Infix to postfix transformation
 Infix notation: Infix notation is the common arithmetic and logical formula notation, in
which operators are written infix-style between the operands they act on
E.g. A + B
 Postfix notation: In Postfix notation, the operator comes after the Operand.
 For example, the Infix expression A+B will be written as AB+ in its Postfix Notation.
 Postfix is also called ‘Reverse Polish Notation’
9
 One disadvantage with the infix notation is that we need to use parentheses to control the
evaluation of the operators.
 In postfix notation we do not need parentheses.
 Infix to postfix can be done in two ways:
o Manual transformation
o Algorithmic transformation
i) Manual Transformation:
The rules for manually converting infix to postfix expressions are as follows:
1. Fully parenthesize the expression using any explicit parentheses and the arithmetic precedence
– multiply and divide before add and subtract.
2. Change all infix notations in each parenthesis to postfix notation, starting from the innermost
expressions. Conversion to postfix notation is done by moving the operator to the location of
the expressions closing parenthesis.
3. Removing all parentheses
Example:
A+B*C
Step1 results in
(A+(B*C))
Step2 moves the multiply operator after c
(A (BC*)+)
and then moves the addition operator to between the last two closing parentheses. This change is
made because the closing parenthesis for the plus sign is the last parenthesis. We know have
( A ( B C *) + )
Finally , step 3 moves the parentheses
ABC*+
More complex example
This example is not only longer but it already has one set of parentheses to override the default
evaluation order.
( A + B) * C + D + E * F – G
Step1 adds parentheses
( ( ( ( ( A + B ) * C ) + D ) + ( E * F ) ) – G)
Step2 then moves the operators .
( ( ( ( ( A B + ) C * ) D + ) ( E F * ) + ) G -)
Step3 removes the parentheses.
AB+C*D+EF*+G–
ii) Algorithmic Transformation
 The manual operation would be difficult to implement in a computer
 Another technique is that we can easily implement with a stack.
 Simple example:
A * B converts to A B *
 We can read the operands and output them in order.
10
 The problem becomes how to handle the multiply operator; we need to postpone putting it
in the output until we have read the right operand B.
 In this case we push operator into a stack and, after the whole infix expression has been
read, pop the stack and put the operator in the postfix expression
 Complex Expression:
A * B + C converts to A B * C +
 If we were to simply put the operators into the stack as we did earlier and then pop them to
the postfix expression after all of the operands had been read, we would get the wrong
answer.
 Some how we must pair the two operators with their correct operands.
 One possible rule might be to postpone an operator only until we get another operator .
 Then before we push the second operator, we could pop the first one and place it in the
output expression.
 This logic works in this case, but it won’t for others.
 Consider the following Example:
A + B * C Converts to A B C * +
 Infix expression use a precedence rule to determine how to group the operands and
operators in an expression.
 We can use the same rule to convert infix to postfix
 When we need to push an operator into the stack, if its priority is higher than the operator
at the top of the stack, we go ahead and push it into the stack.
 Conversely , if the operator at the top of the stack has a higher priority than the current
operator, it is popped and placed in the output expression. Using this rule with the above
expression, we would take the following actions:
1. Copy operand A to output expression
2. Push operator + into stack
3. Copy operand B to output expression
4. Push Operator * into stack (priority of * is higher than +.)
5. Copy operand C to output expression
6. Pop operator * and copy to output expression
7. Pop Operator + and copy to output expression
 Priority
o Priority 2: * /
o Priority 1: + -
o Priority 0: (
 One more complex example is

A + (B * C) – D / E
 Let the incoming the Infix expression be:
A * (B + C) – D / E
Stage 1: Stack is empty and we only have the Infix Expression.
11
Stage 2
 The first token is Operand A Operands are Appended to the Output as it is.
Stage 3
 Next token is * Since Stack is empty (top==NULL) it is pushed into the Stack
Stage 4
 Next token is ( the precedence of open-parenthesis, when it is to go inside, is maximum.

 But when another operator is to come on the top of ‘(‘ then its precedence is least.
12
Stage 5
 Next token, B is an operand which will go to the Output expression as it is
Stage 6
 Next token, + is operator, We consider the precedence of top element in the Stack, ‘(‘. The
outgoing precedence of open parenthesis is the least (refer point 4. Above). So + gets pushed
into the Stack
Stage 7
 Next token, C, is appended to the output
13
Stage 8
 Next token ), means that pop all the elements from Stack and append them to the output
expression till we read an opening parenthesis.
Stage 9
 Next token, -, is an operator. The precedence of operator on the top of Stack ‘*‘ is more
than that of Minus. So we pop multiply and append it to output expression. Then push
minus in the Stack.
Stage 10
 Next, Operand ‘D‘ gets appended to the output.
14
Stage 11
 Next, we will insert the division operator into the Stack because its precedence is more than
that of minus.
Stage 12
 The last token, E, is an operand, so we insert it to the output Expression as it is.
Stage 13
 The input Expression is complete now. So we pop the Stack and Append it to the Output
Expression as we pop it.
15
Algorithm: Convert infix to postfix

Algorithm inToPostFix (formula)
Convert infix formula to postfix
Pre formula is infix notation that has been edited to ensure that there are no syntactical
errors
Post Postfix formula has been formatted as a string
Return Postfix formula
1 Create stack ( stack)
2 loop (for each character in formula )
1 if ( Character is open paranthesis)
1 pushStack (stack, character)
2 elseif ( character is close paranthesis )
1 popStack ( stack. Character )
2 loop ( Character not open paranthesis )
1 concatenate character to postFixExpr
2 popStack (stack, character )
3 end loop
3 elseif ( character is operator )
Test priority of token to token at top of stack
1 popstack ( stack, topToken)
2 loop ( not emptyStack (stack) AND priority ( character ) < = priority ( topToken ) )
1 popStack ( stack, tokenOut )
2 concatenate tokenOut to postFixExpr
3 stackTop ( stack,, topToken )
3 end loop
4 pushStack ( stack, token )
4 else
character is operand
1 Concatenate token to postFixExpr
5 end if
3 end loop
Input formula is empty. Pop stack to postfix
4 loop ( not emptyStack ( Stack ) )
1 popStack ( stack, character )
2 concatenate token to postFixExpr
5 end loop
6 return postFix
end inToPostFix
16
C Implementation
#include<stdio.h>
#include<conio.h>
#include <ctype.h>
#define SIZE 50
char s[SIZE];
int top=-1;
void push(char elem)
{
s[++top]=elem;
}
char pop()
{
return(s[top--]);
}
int pr(char elem)
{
switch(elem)
{
case '#': return 0;
case '(': return 1;
case '+':
case '-': return 2;
case '*':
case '/': return 3;
}
}
void main()
{
char infx[50],pofx[50],ch;
int i=0,k=0;
clrscr();
printf("\n\nRead the Infix Expression ? ");
scanf("%s",infx);
push('#');
while((ch=infx[i++])!='\0')
{
if( ch == '(') push(ch);
else
if( ch == ')')
{
while( s[top] != '(')
17
pofx[k++]=pop();
pop(); /* Remove ( */
}
else
if(isalnum(ch)) pofx[k++]=ch;
else
{ /* Operator */
while( pr(ch) <= pr(s[top]))
pofx[k++]=pop();
push(ch);
}
}
while( s[top] != '#')
pofx[k++]=pop();
pofx[k]='\0';
printf("\n\nGiven Infix Expn: %s Postfix Expn: %s\n",infx,pofx);
getch();
}
Output:
Read the infix expression?
(a+b)*(c-d)/e
Given Infix Expn: (a+b)*(c-d)/e Postfix Expn: ab+cd-*e/
Evaluation of postfix expression

 Fundamental principles followed while evaluating the postfix expression :
1.Read the expression from left to right.
2.If there comes an operand , push it into the stack.
3.If there comes an operator , pop operand 1 and operand 2 and then :
A . Push ‘(‘
B . Push ‘operand 2’
C . Push ‘operator’
D . Push ‘operand 1’
E . Push ‘)’
Advantages of Postfix Expression:
 Postfix notation is easier to work with. In a postfix expression operands appear before the
operators, there is no need of operator precedence and other rules. In postfix expression the
topmost operands are popped off and operator is applied and the result is again pushed to the stack
and thus finally the stack contains a single value at the end of the process.
 In postfix expression, there are no parentheses and therefore the order of evaluation will be
determined by the positions of the operators and related operands in the expression.
Algorithm: Evaluate a Postfix Expression
18
Pre a valid expression

Post postfix value computed
Return value of expression
createstack (stack)
/* scan the input string reading one element */
while (not end of input) {
symb = next input character;
if (symb is an operand)
push(opndstk, symb)
else {
/* symb is an operator */
opnd2 = pop(opndstk);
opnd1 = pop(opndstk);
value = result of applying symb to opnd1 and opnd2;
push(opndstk, value);
} /* end else */
} /* end while */
return (pop(opndstk));
Example:
Postfix Expression: 6 2 3 + - 3 8 2 / + * 2 $ 3 +
symb opnd1 opnd2 value opndstk
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
8 6 5 1 1,3,8
2 6 5 1 1,3,8,2
/ 8 2 4 1,3,4
+ 3 4 7 1,7
* 1 7 7 7
2 1 7 7 7,2
$ 7 2 49 49
3 7 2 49 49,3
19
+ 49 3 52 52
Algorithm for Postfix Expression :

1. Read the element.
2. If element is an operand then:
Push the element into the stack.
3. If element is an operator then :
Pop two operands from the stack.
Evaluate expression formed by two operand and the operator.
4. If no more elements then:
Pop the result
Else
Goto step 1.
Push the result of expression in the stack end.
How to evaluate postfix (manually)
Going from left to right, if you see an operator, apply it to the previous two operands (numbers)
Example:
A B C * D / + E F - -
((A+
(B*C)/
D)-(E-
F))
Equivalent infix: A+ B * C / D– (E– F)
Ex: 43*67+5-+)
Push the opening

bracket ‘(‘ into the
stack .
20
Operand ‘4’ push it

into the stack

into the stack.
Now comes Operator
‘*’
Pop operand ‘3’ and

‘4’
Evaluate the
expression
4*3 =12
Pus it into the
stack

into the stack
21
6
Operand ‘7’ and
‘6’
Are popped
=13
Push it into the
stack
into the stack
Operands ‘5’
and ‘13’ are
popped
We get ‘8’
8
Operator ‘+’
20
22
20
Now , pop the
element till the
opening bracket
)
AND THE FINAL
ANSWRER IS
’20’
C Implementation
#include<stdio.h>
#include<conio.h>
#define SIZE 50
char s[SIZE];
int top=-1;
{
s[++top]=elem;
}
char pop()
{
return(s[top--]);
}
int cal(int elem1,char op,int elem2)
{
switch(op)
{
23
case '+':return(elem1+elem2);
case '-':return(elem1-elem2);
case '*':return(elem1*elem2);
case '/': return(elem1/elem2);
}
}
void main()
{
char pofx[50],ch;
int i=0,opnd2,opnd1,val;
clrscr();
printf("\n\nRead the Postfix Expression ? ");
scanf("%s",pofx);
while((ch=pofx[i++])!='\0')
{
if(isdigit(ch))
{
ch=pofx[i-1]-'0';
push(ch);
}
else
{
opnd2=pop();
opnd1=pop();
val=cal(opnd1,ch,opnd2);
push(val);
}
}
val=pop();
printf("the result of evaluation of postfix expression is:%d",val);
getch();
}
2.1.4. Other Applications:
Parsing
 Parsing is any logic that breaks data into independent pieces for further processing
 For ex, to translate a source program to machine language, a compiler must parse the program into
individual parts such as keywords, names and tokens.
 One common programming problem is unmatched parentheses in an algebraic expression
 When parentheses are unmatched, two types of errors can occur: Opening parenthesis can be
missing or the closing parenthesis can be missing
 These two errors are shown in fig.
24
 In algorithm, we parse a source program to ensure that all of the parentheses are properly paired
Algorithm: Parse parentheses
Algorithm parseParens
This algorithms reads a source program and parses it to make sure all opning – closing parentheses are
paired
1. loop (more data)
1. read (character)
2. if (opening parenthesis)
1. pushstack (stack, character)
3. else
1. if (closing parenthesis)
1. if (emptystack(stack))
1. print (error: closing parenthesis not matched)
2. else
1. popstack (stack)
3. end if
2. end if
4. end if
2. end loop
3. if (not emptystack (stack))
1. print (error: opening parenthesis not matched)
end parseParens
C Implementation
#include<stdio.h>
#include<conio.h>
#define SIZE 50
char s[SIZE];
int top=-1;
{
s[++top]=elem;
}
char pop()
{
return(s[top--]);
}
int emptystack()
{
if(top==-1)
25
return 1;
else
return 0;
}
void main()
{
char pofx[50],ch;
int i=0,x,j,opnd1,opnd2,val;
clrscr();
printf("\n\nRead the Postfix Expression ? ");
scanf("%s",pofx);
while((ch=pofx[i++])!='\0')
{
if(ch=='(')
push(ch);
else
if(ch==')')
{
if(emptystack())
printf("error:closing parenthesis is not matched\n");
else
{
pop();
}
}
}
if(!emptystack())
printf("error: opening parenthesis not matched\n");
getch();
}
Output:
Read the Postfix Expression?
((A+B)*c
error:opening parenthesis is not matched
26

UNIT - II - Stacks

Uploaded by

Copyright:

Available Formats

UNIT - II - Stacks

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

UNIT - II - Stacks

Uploaded by

Copyright:

Available Formats

Data structures Lecture Notes Unit - II

Stacks and Queues

2.1.1 Basic Operations:

2.1.2. Array representations of stacks:

2.1.3 Stack Applications:

2.1.3.1. Reversing Data:

1. set digit to number modulo 2

 One more complex example is

 The first token is Operand A Operands are Appended to the Output as it is.

 Next token is ( the precedence of open-parenthesis, when it is to go inside, is maximum.

 Next token, B is an operand which will go to the Output expression as it is

 Next token, C, is appended to the output

 Next, Operand ‘D‘ gets appended to the output.

 The last token, E, is an operand, so we insert it to the output Expression as it is.

Algorithm: Convert infix to postfix

Evaluation of postfix expression

Algorithm: Evaluate a Postfix Expression

Pre a valid expression

Algorithm for Postfix Expression :

Push the opening

Operand ‘4’ push it

Operand ‘3’ push it

Pop operand ‘3’ and

Operand ‘6’ push it

You might also like