Stack & Queue

Points to be Discussed
Stacks
Basic Operations of Stack
Memory Representation
Traversal
Stacks
Stacks
A Stack is a list of elements in which an
element may be inserted or deleted only at
one end, called the top of the stack. This
means that the elements are removed from
a stack in the reverse order of that in which
they were inserted into the stack.
Two operations on Stack:
1. Push is the term used to insert an item
on to the stack
2. Pop is the term used to delete an
element from a stack
Array representation of stack
Array Representation of
Stack
Stacks may be represented by means of
one-way list or linear arrays. A pointer
variable TOP 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=0 or TOP=NULL will
indicate that the stack is empty.
XXX YYY ZZZ
1 2 3 4 5 6 7 8

TO 3 MAXST 3
P K
Linked Representation of Stack
 Linked Representation of
Stack
The liked representation of stack is a stack
that is implemented using a singly linked
list. The INFO fields of the nodes hold the
elements of the Stack and the LINK fields
hold pointers to the neighboring element in
the stack. The START pointer of the linked
list behaves as the TOP pointer variable of
the stack and the null pointer of the last
Topnode in the list signals the bottom of stack.
(START)

XXX YYY ZZZ

INFO LIN
Top of K Bottom of
Stack Stack
PUSH(STACK, TOP,
MAXSTK, ITEM)
1. [Stack already filled?]
If TOP=MAXSTK, then: Print:
OVERFLOW, and Return
2. Set TOP:=TOP + 1
3. Set STACK[TOP]:=ITEM
4. Return
POP(STACK, TOP, ITEM)
1. [Stack has an item to be removed?]
If TOP=0, then: Print:
UNDERFLOW, and Return
2. Set ITEM:=STACK[TOP]
3. Set TOP:=TOP-1
4. Return
Polish Notation
1. Infix Notation is the one in which the operator
symbol is placed between its two operands. Ex- A
+B

2. Polish Notation is the one in which the operator

symbol is placed before its two operands. Ex- +AB
Polish Notation is also known as
Prefix Notation.

3. Reverse Polish Notation is the one in which the

operator symbol is placed after its two operands.
Ex- AB+ Reverse Polish Notation is also known as
Postfix/Suffix Notation.
Evaluation of Postfix
Expression
1. Add a right parenthesis “)” at the end of P
2. Scan P from left to right and repeat steps 3 and 4
for each element of P until the sentinel “)” is
encountered
3. If an operand is encountered, put it on STACK
4. If an operator is encountered, then:
(a) Remove the two top elements of STACK, where
A is
the top element and B is the next-to-top
element
(b) Evaluate B (*) A
c) Place the result of (b) back on STACK
[End of If structure]
[End of Step 2 loop]
5. Set VALUE equal to the top element on STACK
6. Exit
Example
P: 5, 6, 2, +, *, 12, 4, /, -
P: 12, 7, 3, -, /, 2, 1, 5, +, *, +
Transforming Infix into Postfix
Expression
POLISH(Q,P)
1. Push “(” onto STACK and add “)” to the end of Q
2. Scan Q from left to right and repeat steps 3 to 6
for each element of Q until the stack is empty:
3. If an operand is encountered, add it to P
4. If a left parenthesis is encountered, push it onto
STACK
5. If an operator is encountered, then:
(a) Repeatedly pop from STACK and add to P
each operator
(on the top of Stack) which has the same
precedence as
or higher precedence than operator.
(b) Add operator to STACK.
Transforming Infix into Postfix
Expression
6. If a right parenthesis is encountered, then:
(a) Repeatedly pop from STACK and add
to P each operator
(on the top of STACK) until a left
parenthesis is
encountered.
(b) Remove the left parenthesis. [Do not
add the left
parenthesis to P.]
7. Exit
Example

A+(B*C-(D/E (exp) F)*G)*H

Solve this expression
A+(B*C-(D/E-F)*G)*H
Recursion
FACTORIAL(FACT,N)
This procedure calculates N! and returns
the value in the variable FACT.
1. If N=0, then: Set FACT=1 and return
2. Call FACTORIAL(FACT, N-1)
3. Set FACT=N*FACT
4. Return
FIBONACCI(FIB,N)
1. If N=0 or N=1, then Set: FIB:=N and
return
2. Call FIBONACCI(FIBA, N-2)
3. Call FIBONACCI(FIBA, N-1)
4. Set FIB=FIBA + FIBB
5. Return
Tower of Hanoi
The Tower of Hanoi puzzle was invented
by the French mathematician Edouard
Lucas in 1883.
You need to move all of the disks from
the first tower to the last tower
Larger disks can not be placed on top of
smaller disks
The third tower can be used to
temporarily hold disks
Tower of Hanoi
Here is a high-level outline of how to move
a tower from the starting pole, to the goal
pole, using an intermediate pole:
Move a tower of height-1 to an intermediate
pole, using the final pole.
Move the remaining disk to the final pole.
Move the tower of height-1 from the
intermediate pole to the final pole using the
original pole.
Recursive Solution
Recursive Solution
Recursive Solution
Recursive Solution
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Recursive Algorithm
void Hanoi(int n, string a, string b, string c)
{
if (n == 1) /* base case */
Move(a,b);
else { /* recursion */
Hanoi(n-1,a,c,b);
Move(a,b);
Hanoi(n-1,c,b,a);
}
}
 Program on tower of hanoi
#include <stdio.h> int main()
#include <stdlib.h> {
void tower(int n, char a,char b,char c) tower(3,'A','B','C');
{ return 0;
if(n==1) }
{

printf("\nDisk %d moves from % c \t to %c \t

",n,a,c);
}
else
{
tower(n-1,a,c,b);
printf("\nDisk %d moves from % c \t to %c \t
",n,a,c);
tower(n-1,b,a,c); }
}
QuickSort
Quick Sort
 Quick sort is an algorithm of the divide and conquer type ie. the problem of
sorting a set is reduced to the problem of sorting two smaller sets using two
Stacks Lower and Upper.
 Example:

44,33,11,55,77,90,40,60,99,22,88,66
1. Use the first element (44) . Beginning with last number 66 scan the list from
right to left comparing each number with 44 and stopping at the first number
less than 44. the number is 22 interchange 44 with 22.
22,33,11,55,77,90,40,60,99,44,88,66
2. Beginning with 22 next scan the list in the opposite direction from left to right
comparing each number with 44 and stopping at the first number greater than
44. the number is 55 interchange 55 with 44.
22,33,11,44,77,90,40,60,99,55,88,66
Algorithm
Quick Sort this algorithm sorts
an array A with N elements.
6. [Push left Sublist on to stacks
1. [Initialize] TOP=NULL when it has 2 or more Elements]
2. [Push boundary values of A on If Beg<LOC-1 then
to stacks where A has 2 or Top=Top+1,
more elements] Lower[Top]=Beg
upper[Top]=LOC-1
if N>1 Then Top=Top+1,
Lower[1]=1, Upper[1]= N.
7. [Push Right Sublist on to stacks
3. Repeat Steps 4 to 7 while Top! when it has 2 or more Elements]
=NULL. if LOC+1<End then
4. [Pop Sublist From Stacks] Top=Top+1,
Set Beg=Lower[Top], End= Lower[Top]=LOC+1
Upper[Top] and Top=Top-1 upper[Top]=End
[End of If]
5. Call [End of step 3 loop]
Quick(A,N,BEG,END,LOC)
8. Exit
 QUICK() 3) [Scan from Left to Right]
a) Repeat while
1)[Initialize] Set Left=Beg ,Right
A[LEFT]<=A[LOC] and
=End and Loc= Beg
LEFT!=LOC:
2) [Scan from Right to Left]
LEFT=LEFT+1
a) Repeat while [End of Loop]
A[LOC]<=A[Right] and
LOC !=Right: b) If LOC=LEFT then Return:
Right=Right-1 c) If A[LEFT] > A [LOC] then
[End of Loop] i) Interchange A[left] and
b) If LOC=Right then Return: A[loc]
Temp=A[LOC],
c) If A[LOC]>A[Right] then
A[LOC]=A[Left],
i) Interchange A[loc] and A[Left]=Temp.
A[Right] ii) Set LOC=Left
Temp=A[LOC], iii) GOTO Step 2.
A[LOC]=A[Right],
A[Right]=Temp.
ii) Set LOC=Right
iii) GOTO Step 3.
Queues
Queues
A Queue is a linear list of elements in which
deletions can take place only at one end,
called the front, and insertions can take
place only at the other end, called the rear.
Queues are also called FIFO lists, since the
first element in a queue will be the first
element out of the queue.
Array Representation of
Queues
Array Representation of
Queues
FRONT contains the location of the front
element of the queue, and REAR contains the
location of the rear element of the queue.
The condition FRONT=NULL will indicate that
the queue is empty.
Whenever an element is deleted from the
queue, the value of FRONT is increased by 1
FRONT=FRONT + 1
Whenever an element is added to the queue,
the value of REAR is increased by 1
REAR=REAR + 1
If REAR=N, then to insert a new ITEM in queue
we reset REAR=1 instead of N+1.
Array Representation of
Queue
If FRONT=N and an element of QUEUE is
deleted, we reset FRONT=1 instead of
increasing FRONT to N+1.
Suppose that the queue contains only one
element, i.e. suppose that
FRONT=REAR != NULL
and suppose that the element is deleted.
Then we assign
FRONT:=NULL and
REAR:=NULL
to indicate that the queue is empty
Array Representation of
Queue
FRONT: AAA BBB CCC DD …
1 D
1 2 3 4 5 6 7 … N
REAR: 4

FRONT: BBB CCC DD …

2 D
1 2 3 4 5 6 7 … N
REAR: 4

FRONT: AAA BBB CCC DD …

1 D
REAR: 4 1 2 3 4 5 6 7 … N

FRONT: BBB CCC DD …

2 D
REAR: 4 1 2 3 4 5 6 7 … N
QINSERT(QUEUE,N,FRONT,REA
R,ITEM)
1. [Queue already filled?]
If FRONT=1 and
REAR=N, or if FRONT=REAR+1, then:
Write: OVEFLOW, and Return
2. [Find new value of REAR]
If FRONT:=NULL, then Set
FRONT:=1 and REAR:=1
Else if REAR:=N then Set REAR:=1
Else Set REAR:=REAR+1
[End of If structure]
3. Set QUEUE[REAR]:=ITEM
4. Return
QDELETE(QUEUE,N,FRONT,REA
R,ITEM)
1. [Queue already empty?]
If FRONT:=NULL, then
write: UNDERFLOW, and Return
2. Set ITEM:=QUEUE[FRONT]
3. [Find new value of FRONT]
If FRONT=REAR, then: Set
FRONT:=NULL and REAR:=NULL
Else if FRONT:=N then Set
FRONT:=1
Else Set FRONT:=FRONT+1
[End of If structure]
4. Return
Linked representation of
Queues
 Linked Representation of
Queues
A linked queue is a queue implemented as
a linked list with two pointer variables
FRONT and REAR pointing to the nodes
which is in the FRONT and REAR of the
queue. The INFO fields of the list hold the
elements of the queue and the LINK fields
hold pointers to the neighboring elements
in the queue.
Queue
Q:

AAA BBB CCC DDD X

Fron Rea
t r
LINKQ_INSERT(INFO, LINK,
FRONT, REAR, ITEM)
1. Set INFO[NEW]=ITEM and
LINK[NEW]=NULL
2. If (FRONT==NULL)
then FRONT=REAR=NEW
else
LINK[REAR]=NEW and REAR=NEW
3. Exit
LINKQ_DELETE(INFO, LINK,
FRONT, REAR, ITEM)
1. If FRONT=NULL then write: UNDERFLOW
and Exit
2. Set TEMP=FRONT
3. ITEM=INFO(TEMP)
4. FRONT=LINK(TEMP)
Deques
A deque is a linear list in which elements
can be added or removed at either end but
not in the middle. The term deque is a
contraction of the name double-ended
queue.
There are two types of deques:
1. input-restricted deque: It is a deque
which allows insertions at only one end of
the list but allows deletions at both ends of
the list.
2. output-restricted deque: It is a deque
which allows deletions at only one end of
the list but allows insertions at both ends of
Priority Queues
A Priority Queue is a collection of elements
such that each element has been assigned
a priority and such that the order in which
elements are deleted and processed comes
from the following rules:
1. An element of higher priority is processed
before any element of lower priority
2. Two elements with same priority are
processed according to the order in which
they were added to the queue