Chapter 2.

The Stack and Queue

Table of Contents
Stack....................................................................................................................................................... 2

Queue ..................................................................................................................................................... 4

1. Linear queue................................................................................................................................ 4

2. Circular Queue ............................................................................................................................ 5

3. Priority queue .............................................................................................................................. 6

Stack application: Evaluation of infix, postfix and prefix expressions ................................................. 6

Pravin Sangroula [IOE Purwanchal Campus][[email protected]] Page 1

 Chapter 2. The Stack and Queue

Stack

 Stack is an ordered collection of data in which insertion and deletion operation is performed
at only one end called the top of the stack.
 Stack operation follows LIFO approach
 Stack operations
o Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow
condition.
o Pop: Removes an item from the stack. The items are popped in the reversed order in
which they are pushed. If the stack is empty, then it is said to be an Underflow
condition.
 Initial value of top is -1.

 ADT specification of Stack

abstract typedef <<elType>> STACK (elType);

abstract empty(s)
STACK(elType) s;
postcondition empty == (len(s) == 0) // len(s) returns the length of s

abstract eltype pop(s)

STACK(elType) s;
precondition empty(s) == FALSE
postcondition pop == first(s); //first(s) gives the first element of s
s == sub(s, 1, len(s) -1) //sub(s,1,len(s)-1) gives substring of s (1 to len(s)-1)

abstract push(s, elt)

STACK(eltype) s;
elType elt;
postcondition s == <elt> + s //<elt> + s concatenates ‘elt’ and s

Pravin Sangroula [IOE Purwanchal Campus][[email protected]] Page 2

 Chapter 2. The Stack and Queue

 Algorithm
Push
1. Start
2. if(top=size-1)
print “stack is full”
otherwise,
i. Increase top by 1
ii. Read data and store at top position
3. Stop
Pop
1. Start
2. if(top=-1)
print “stack is empty”
otherwise,
decrease top by 1
3. Stop

//implementation in c
struct stack
{
int data[size];
int top;
}

Pravin Sangroula [IOE Purwanchal Campus][[email protected]] Page 3

 Chapter 2. The Stack and Queue

Queue

 Queue is an ordered collection of data in which data can be inserted from one end called rear
and that can be removed from another end called front of the queue.
 It follows FIFO system.
 Queue operations
o enqueue: Adds an item to the queue. If the queue is full, then it is said to be an
Overflow condition.
o dequeue: Removes an item from the queue. The items are popped in the same order in
which they are pushed. If the queue is empty, then it is said to be an Underflow
condition.

1. Linear queue
o Initial condition: front=0 and rear=-1
o Algorithm
Insert
1. Start
2. if(rear=qsize-1)
print “queue is full”
otherwise,
i. Increase rear by 1
ii. Read data and store at rear position of the queue
3. Stop
Delete(without shift)
1. Start
2. if(rear<front)
print “queue is empty”
otherwise,
i. Increase front by 1
3. Stop

Pravin Sangroula [IOE Purwanchal Campus][[email protected]] Page 4

 Chapter 2. The Stack and Queue

Delete(with shift)
1. Start
2. if(rear<front)
print “queue is empty”
otherwise,
i. shift all the elements from front+1 to rear by 1 position towards front
ii. Decrease rear by 1
3. Stop

2. Circular Queue
o Initial condition: front=0 and rear=0
o Algorithm
Insert
1. Start
2. If((rear+1) % qsize=front)
print “queue is full”
otherwise,
i. Increase rear as rear= (rear+1) % qsize
ii. Read data and store at rear position of the queue
3. Stop
Delete
1. Start
2. if(rear=front)
print “queue is empty”
otherwise,
front=(front+1) % qsize
3. Stop

Pravin Sangroula [IOE Purwanchal Campus][[email protected]] Page 5

 Chapter 2. The Stack and Queue

3. Priority queue
o Priority Queue is an extension of queue with following properties.
o Every item has a priority associated with it.
o An element with high priority is dequeued before an element with low priority.
o Two elements have the same priority, they are served according to their order in
the queue.
o An ascending priority queue is a collection of items into which items can be inserted
arbitrarily and from which only the smallest item can be removed.
o A descending priority queue is similar but allows deletion of only the largest item.
o For example
o A stack may be viewed as descending priority queue whose elements are ordered
by the time of insertion. The element that was inserted last has the greatest
insertion-time value and is the only item that can be retrieved.
o Similarly, a queue may be viewed as ascending priority queue whose elements are
ordered by the time of insertion.

Stack application: Evaluation of infix, postfix and prefix expressions

 An expression is defined as number of operands or data items combined with several

operators.
 Three types of notation for an expression:
o Infix notation
 An expression where operators are used in-between operands.
 e.g. a - b + c
 It is easy for us humans to read, write, and speak in infix notation but the same
does not go well with computing devices.
o Prefix notation
 An expression where the operator is written ahead of operands.
 e.g. +ab
o Postfix notation
 An expression where the operator is written after the operands.
 e.g. ab+

Pravin Sangroula [IOE Purwanchal Campus][[email protected]] Page 6

 Chapter 2. The Stack and Queue

 Algorithm to convert infix to postfix

Let Infix be a string that stores infix expression and Postfix be a string that stores the postfix
result.

Scan the Infix Expression character from left to right.

1. Start
2. If character is operand
append it to Postfix
3. If character is operator
3.1 If stack is empty OR stack’s top is ’(’ OR precedence of character > precedence of stack’s
top
push character to the stack.
3.2 Else
While stack’s top is operator AND precedence of stack’s top >= precedence of
character
append the operator from stack to Postfix and pop it from stack
Push character to the stack
4. If character is ‘(‘
push character to the stack.
5. If character is ‘)’
append the operator from stack to Postfix and pop it from stack until stack’s top is ‘(‘
pop ‘(‘ from stack
6. Repeat 2 to 5 until infix expression is scanned.
7. Append the operator from stack to Postfix and pop it from stack until stack is empty.
8. Stop

Pravin Sangroula [IOE Purwanchal Campus][[email protected]] Page 7

 Chapter 2. The Stack and Queue

 Example 1: Infix expression: “(A+B)*C”

Symbol Postfix Stack
( (
A A (
+ A (+
B AB (+
) AB+
* AB+ *
C AB+C *
AB+C*
Example 2: A+(B*C-(D/E^F)*G)*H
Symbol Postfix Stack
A A
+ A +
( A +(
B AB +(
* AB +(*
C ABC +(*
- ABC* +(-
( ABC* +(-(
D ABC*D +(-(
/ ABC*D +(-(/
E ABC*DE +(-(/
^ ABC*DE +(-(/^
F ABC*DEF +(-(/^
) ABC*DEF^/ +(-
* ABC*DEF^/ +(-*
G ABC*DEF^/G +(-*
) ABC*DEF^/G*- +
* ABC*DEF^/G*- +*
H ABC*DEF^/G*-H +*
ABC*DEF^/G*-H*+

Pravin Sangroula [IOE Purwanchal Campus][[email protected]] Page 8

 Chapter 2. The Stack and Queue

 Algorithm to evaluate postfix expression.

Scan the Postfix Expression character from left to right.
1. Start
2. If character is number
push on the stack
3. If character is operator(op)
a. Val1=pop
b. Val2=pop
c. Perform result=val2 op val1
d. Push the result into stack
4. Repeat 2 to 3 until postfix expression is scanned.
5. Output the result
6. Stop
Example 1: AB+C*
Let A=1, B=2 and C=3

2 3
1 1 3 3 9

1+2 3*3

Ans=9

Pravin Sangroula [IOE Purwanchal Campus][[email protected]] Page 9

 Chapter 2. The Stack and Queue

Example 2: ABC*DEF^/G*-H*+
Let A=2,B=3C=9,D=8,E=1,F=4,G=2,H=7

4
1 1 1
9 8 8 8 8 8
3 3 27 27 27 27 27 27
2 2 2 2 2 2 2 2 2

2 2

8 8 16 7

27 27 27 11 11 77

2 2 2 2 2 2 79

Ans= 79

Pravin Sangroula [IOE Purwanchal Campus][[email protected]] Page 10