Unit 4

Stacks and Queues

Objectives
Stack

 What is Stack

 Characteristics of a stack

 examples of stack

 Primitive operations on stack

 Describe stack using arrays (Sequential Organization)

 Describe stack using linked list (Linked organization)

 List applications of stack

What is Stack

 Stack is an ordered list but the access, insertion & deletion of

elements are restricted by some rules.
 Elements are inserted and deleted from same end. It is also
called as LIFO.
 Definition:
 A stack is an ordered list in which all insertions & deletions
are made at one end called the top.
 Ex. Make stack of 10,20,30,40,50,60.
 Here 10 will be the bottommost element & 60 will be the
topmost element.
Characteristics of stacks:

 Data can only be placed on the top of the stack.

 Data can only be removed from the top of the stack.
 Data can only be removed from the bottom of the stack if
there is only one item on the stack.
 Data can not be removed from the middle of the stack
without first removing all items from the top.
Example of stack:
 Stack of coins
 Stack of chairs
 Tower of Hanoi etc.
Primitive operations on stack:
 To create a stack
 To insert an element on to the stack
 To remove element from the stack
 To check which element is at the top of the stack.
 To check whether stack is empty or not
 To check whether stack is full or not
To create a stack

 This function creates a stack in memory

 Creation of stack can be either using array or link list
To insert an element on to the stack

 This function inserts a new element at the top of the

stack

 Push (e) : A function which places e onto the stack if

stack is not full
To remove element from the stack

 This function deletes/removes element from the top of

the stack

 Pop( ) : A function which takes out an item from the top

of the stack if stack is not empty
To check whether stack is empty or not
 Stack_Full( ) : A Boolean function which returns 1 if stack s is
full.
 Stack_Empty ( ) : A boolean function which returns 1 if stack is
empty
Representation of stack using arrays
There are the two different ways for representing stack as an
array.
Way I:
int stack[100],top=-1;
Here stack is nothing but an array of integers and top is a
most recent index of that array.

Initially
top=-1 0 1 2 3 4 5…………………. 99
 Way II: Use structure:
 Struct stack
{
int s[100];
int top;
}st;

Normally we use this representation for representing

stack as an array. because here we are binding or co-
relating top variable with stack elements.
Stack & top are associated with each other.
Stack Operations
 Implement stack using arrays with Push( ), Pop( ),
Stack_Empty( ), Stack_Full( ) functions
Stack empty operation:
int stempty()
{
if(st.top==-1)
return 1;
else
return 0;
}
Stack full operation:
int stfull()
{
if(st.top==size-1)
return 1;
else
return 0;
}
Push element to stack
void push(int item) // if stack is not full
{
st.top++;
st.s[st.top]=item;
}
Pop element from stack
int pop() //if stack is not empty
{
int item;
item=st.s[st.top];
st.top- - ;
return(item);
}
Display elements of stack
void display()
{
int i;
if(stempty())
cout<<“stack is empty”;
else
{
for(i=st.top;i>=0;i--)
cout<<st.s[i];
}
}
Check top element
int readtop() //if stack is not empty
{
int item;
item=st.s[st.top];
return(item);
}
 Program for implementation of stack using array.
Need of stack using linked list
 drawback of stack using arrays
i.Size is restricted
ii. Memory is wasted

For overcoming this disadvantages we will use representation

of stack using link list
 When we use concept of link list nodes are created
dynamically as it is needed so we will not check
memory full condition here.
Representation of stack using linked list

Struct stack
{
int data
struct stack * next;
}node;
Representation of stack using linked list

top
Isempty(): if (top==NULL)
Isfull(): Not Applicable for LL implementation
40
Push(): //Similar to insert_beg() of SLL
-if isempty() then top=current_node 30
-else insert_beg nod
Pop(): //Similar to delete_beg() of SLLe 20
-if isempty() then don’t call pop()
-else if last node then top=NULL 10
10 NULL
Null
-else delete_beg()
Stack using linked list
Implemetation of stack using linked list
Implicit and explicit stack
 Implicit stack: built-in , used in function call and return,
recursion etc.
 Explicit stack: push-pop functions are called by user, eg-
assembly language
Stack Applications
 Expression conversion
 Expression Evaluation
 Reversing a string
 Tree traversal( inorder, preorder, postorder)
 Graph traversal ( DFS)
 Checking if expression contains balanced parenthesis or
not
 Undo button, Back button of browser
Expressions:
 Expression is a string of operands and operators.
 Operands are some numeric values.
 Operators are of two types unary and binary
 Unary operators are + and -.
 Binary operators are =,-,+,/,*
Types of Expressions:
 There are 3 types
1.Infix Expression.
2.Postfix Expression
3.Prefix Expression
1.Infix Expression.
 Here the arrangement of operators is as follows
Infix Expression=op1 operator op2
For Ex.
(a + b)
(a + b)*(c - d)
(a + b / e)* (d + f)

In Infix Expression parenthesis are used.

2.Postfix Expression

 Postfix Expression= op1 op2 operator

 Ex.
 a b+
 ab+cd-*
 a b e /+ d f + *
 In postfix expression parenthesis are not used
3.Prefix Expression

 Prefix Expression =operator op1 op2

 Ex.
 +ab
 *+ab–cd
 * +a/be+df
 In prefix expression parenthesis are not used
Convert (a + b / e)* (d + f)
postfix and prefix

 a b e /+ d f + *
 * +a/be+df
Convert A*B+(C-D/E)
postfix and prefix

 Postfix: AB*CDE/-+
 Prifix: +*AB-C/DE
Conversion from Infix to postfix
Expression.
 When we want to convert expressions the most important thing we should know
priorities of the operators.
 This helps in determining the order of evaluation of operands.

Operator Precedence in
Expression
^ 3
*,/ 2
+,- 1
( 4
Rules for Converting Infix to Postfix:

1. The expression is to be read from left to right.

2. Read one character at a time from Infix Expression
3. Make use of stack to store the operators.
4. There should not be any parenthesis in the postfix form.
Algorithm to convert infix expression to
Postfix
 Read expression from left to right.
 If ch ( i.e. current symbol in input string ) is operand then print it in
output string
 If ch is ‘(‘ then push it onto the stack
 If ch is a first operator or first operator after ‘(‘ then push it onto the
stack.
 If priority of ch <= that of element on the top of stack, then pop the
top element & push the ch onto the stack.
 If priority of ch > that of top element then push ch on the stack
 At the end of input string pop all entries from the stack till it becomes
empty & write them into the output string.
 If ch is a ‘) then pop all the entries from the stack and add them into
the output string till you encounter ‘(‘
Ex.A * B + C $
Input Stack Output

None empty none

A empty A

* * A
B * AB
+ POP * and PUSH AB*
C + AB*C

$ empty AB*C+
(a + b ) * (c - d) $
 Answer a b + c d - *
Conversion of infix to postfix
 Test above algorithm for following expression
 Given infix expression is
 A*B+(C-D/E)
 Postfix expression is
 AB*CDE/-+
Conversion of infix to postfix
 Test above algorithm for following expression
 Given infix expression is
 A*B+(C/D-E)
 Postfix expression is
 AB*CD/E-+
Algorithm for evaluation of postfix
expression
1.Read the postfix expression character by character from left to right.
2.If character represents operand, then push it onto the stack
3.Otherwise if it is an operator, pop two operands as op2 & op1 and
perform arithmetic operations.
+ then result = op1 + op2
- then result = op1 – op2
* then result = op1 * op2
/ then result= op1 / op2
4.Push the result onto the stack
5.Repeat step 1-4 till the postfix expression is not over.
6.Pop the result from the top of the stack and print it.
Evaluation of postfix expression
 Evaluate following postfix expression using above algorithm
 5+2*3==523*+
 Answer=11
 623+-382/+*2^3+
 Answer is 52
Evaluation of postfix expression
 Evaluate following postfix expression using above algorithm
 248+-8+
 Answer: -2
 234*+
 Answer: 14
Conversion of infix to prefix
 Algorithm:
i. Take s which is stack contains operators
ii. p[ ] character string which holds result
iii. infix[ ] string containing expression
iv. n= strlen(infix)
v. n=n-1, k=n points to last character
vi. If i/p is an operand copy it in p
p[k]= infix[n];
k- - ; n- -;
vii. If infix[n] is operator then
a.) if s is empty push operator in s
b.)if s is not empty then check whether priority of current
operator is greater than that of operator on top of stack, if so
push this operator onto s else
c.) pop operator from stack and place them in p till current
operators priority becomes greater than the operator on top of
the stack or stack become empty and push current operator
onto stack
viii.If n>=0 repeat step vi.
ix. Pop all the elements of s and place it in p.
x. Print p
xi. Stop.
Conversion of infix to prefix A*B+C

 OUTPUT: +*ABC
 Infix: A*B+(C-D/E)
 Answer: +*AB-C/DE