STACK and QUEUE

Dr. P. Ganesh kumar

Dept. of Computer Science and Engineering
College of Engineering Guindy
Anna University
 What is Stack?
• Linear data structure that follows a particular order for
insertion and deletion of items in computer memory.
• The order is “the element that is inserted last should
be the element deleted first”. That is LIFO(Last In First
Out).
• Alternatively, the order can also be thought as “the
element that is inserted first should be the element
deleted last”. That is FILO(First In Last Out).
• Real world example for stack is a deck of cards or a
pile of plates

2
Diagrammatic Representation of Stack

Top=-1 Top= Array size

3
 Operations of Stack
• Push: Adds an item in the stack. Before insertion, check
Overflow condition. That is if the stack is full, then no
insertion possible. [Top == ARRAYSIZE]

• Pop: Removes an item from the stack. Before deletion,

check underflow condition. If the stack is empty, then no
deletion possible. [Top==-1]

• Peek or Top: Returns top element of stack.

• isEmpty: Returns true if stack is empty, else false.

• isFull: Returns true if stack is full, else false

4
 Push Pop Operations of Stack

Top=2

Top=1
Top=1

Top=0
Top=-1

5
Linked List Implementation of Stack

6
 Application of Stack
• Expression Conversion
– An expression can be represented in prefix, postfix or infix notation. Stack can be used to convert one form of
expression to another.

• Syntax Parsing
– Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low
level code.

• Backtracking
– Suppose we are finding a path for solving maze problem. We choose a path and after following it we realize that it
is wrong. Now we need to go back to the beginning of the path to start with new path. This can be done with the
help of stack.

• Parenthesis Checking
– Stack is used to check the proper opening and closing of parenthesis.

• String Reversal
– Stack is used to reverse a string. We push the characters of string one by one into stack and then pop character
from stack.

• Function Call
– Stack is used to keep information about the active functions or subroutines.

• Balancing Symbol

• Number Conversion

• Compiler Design

7
 Queue - Introduction
• Linear data structure to store list of data.
– one data holder and
– two data tracker.
• Front
• Rear
• Data holder
– Stores the data
• Data tracker
– keep track of the operations with data.
• Operations
– Insertion
– Deletion
– Searching

8
 Queue – Diagrammatic Representation
Data Holder

A [0] A [1] A [2] A [3] A [4]

Data Tracker

Front Rear
Helps to insert the element into the Queue

Helps to delete the element from the Queue

9
 Empty Queue
Data Holder
Data Tracker

A [0] A [1] A [2] A [3] A [4]

Front = -1 Rear = -1

Full Queue
Data Holder
5 8 11 -7 6

A [0] A [1] A [2] A [3] A [4]

Front = -1
Rear = 4
10
 One Element Added to Queue
Data Holder

5
A [0] A [1] A [2] A [3] A [4]

Front = -1

Rear = 0

One Element Deleted from Queue

Data Holder
8 11 -7 6

A [0] A [1] A [2] A [3] A [4]

Front = 0 Rear = 4
11
 Empty Queue
Data Holder

A [0] A [1] A [2] A [3] A [4]

Front = 4 Rear = 4

Few inserted and few deleted Queue

Data Holder
-7 6

A [0] A [1] A [2] A [3] A [4]

Front = 2 Rear = 4
12
 Queue - Operations
• Insertion • Deletion
– enQueue – deQueue
– Overflow Condition – Underflow Condition
• Rear=qsize-1 • Front==Rear
• Pseudo code • Pseudo code
– If (Rear==Qsize-1) – If (Front==Rear)
• Print “Full Queue – • Print “Empty Queue –
unable to Insert” Unable to Delete”
– Else – Else
• Rear = Rear + 1 • Front = Front + 1
• Queue[Rear]=item • Item = Queue [Front]
• Delete Item

13
 Special kinds (Types) of Queue
• Queue
– First In First out  (FIFO)
• Last In Last Out  (LILO)
• Types
– Circular Queue
• Last queue location is connected with first queue location to
form a circle.
– Priority Queue
• The data values are provided with priority value to carry out
insertion and deletion based on this value
– Deque
• Double ended queue that allows Insertion and Deletion in
both the ends of queue.

14
 Applications of Queue
• Operating System
– Scheduling
• CPU Scheduling
• Disk Scheduling
• Load Balancing
– File Transfer
• IO Buffers
• Pipes
• Data Communication

15
 Limitations of Simple Queue
• Empty Queue
– REAR== FRONT == -1
– REAR == FRONT == QueueSize
• One Entry Queue
– REAR == 0 && FRONT == -1
• Full Queue
– REAR == Queue Size && FRONT == -1
• Other Forms of Condition for Full Queue
– REAR == QueueSize && FRONT == 0
• One element deleted and One space is there for Insertion but
not possible to carry out insertion
– REAR == QueueSize && FRONT == QueueSize -1
• One element is available and QueueSize-1 space is available but
not possible to carry out insertion
16
Circular Queue
5 4

6 3

7 2

0 1

REAR = -1
FRONT = -1

17
 Circular Queue - Insertion
5 5 4
4

6
6 3
3

7
7
2 2

10
FRONT = -1
0 1 FRONT= -1 0 1
REAR = -1 REAR = 0
5 5 4
4

6 6
3
3 REAR= 3
25

20 7
7
2 2
10 15 10 15
FRONT = -1 0
0 1 1

FRONT = -1 REAR = 1
18
 Circular Queue - Deletion
5 5 4
4

6
35 30 35 30
6 3
3
40 25 40 25
REAR = 7
REAR = 7
7 45 20 7
45 20
2 2

10 15 15
FRONT = -1
0 1 0 1

FRONT = 0
5
4 5 4
FRONT = 6

6
35 30
6
3 3
40 25
REAR = 7
REAR = 7
45 45 20
7 7
2
2

0 1 0
1

FRONT = 1
19
 Circular Queue – Pointer Movement -
Insertion
• REAR Pointer
– REAR = (REAR +1) mod QueueSize
• Imagine a Queue of Size = 8
– enqueue(“10"); REAR= (REAR+1)%8; ( FRONT = -1, REAR = 0)
– enqueue(“15"); REAR = (REAR+1)%8; ( FRONT = -1, REAR = 1)
– enqueue(“20"); REAR = (REAR+1)%8; ( FRONT = -1, REAR = 2)
– enqueue(“25"); REAR = (REAR+1)%8; ( FRONT = -1, REAR = 3)
– enqueue(“30"); REAR = (REAR+1)%8; ( FRONT = -1, REAR = 4)
– enqueue(“35"); REAR = (REAR+1)%8; ( FRONT = -1, REAR = 5)
– enqueue(“40"); REAR = (REAR+1)%8; ( FRONT = -1, REAR = 6)
– enqueue(“45"); REAR = (REAR+1)%8; ( FRONT = -1, REAR = 7)

20
 Circular Queue – Pointer Movement -
Deletion
• FRONT Pointer
– FRONT= (FRONT+1) mod QueueSize
• Imagine a Queue of Size = 8
– dequeue(“10"); FRONT = (FRONT+1)%8; (REAR= 7, FRONT = 0)
– dequeue(“15"); FRONT = (FRONT+1)%8; ( REAR = 7, FRONT = 1)
– dequeue(“20"); FRONT = (FRONT+1)%8; ( REAR = 7, FRONT = 2)
– dequeue(“25"); FRONT = (FRONT+1)%8; ( REAR = 7, FRONT = 3)
– dequeue(“30"); FRONT = (FRONT+1)%8; ( REAR = 7, FRONT = 4)
– dequeue(“35"); FRONT = (FRONT+1)%8; ( REAR = 7, FRONT = 5)
– dequeue(“40"); FRONT = (FRONT+1)%8; ( REAR = 7, FRONT = 6)
– dequeue(“45"); FRONT = (FRONT+1)%8; ( REAR = 7, FRONT = 7)

21
Circular Queue – Pointer Movement –
Insertion followed by eletion
• REAR Pointer
– REAR = (REAR + 1) mod QueueSize
• FRONT Pointer
– FRONT = (FRONT+1) mod QueueSize
• Imagine a Queue of Size = 8
– enqueue(“50"); REAR= (REAR+1)%8; ( FRONT = 7, REAR = 0)
– enqueue(“55"); REAR = (REAR+1)%8; ( FRONT = 7, REAR = 1)
– enqueue(“60"); REAR = (REAR+1)%8; ( FRONT = 7, REAR = 2)
– enqueue(“65"); REAR = (REAR+1)%8; ( FRONT = 7, REAR = 3)
– dequeue(“45"); FRONT = (FRONT+1)%8; ( FRONT = 0, REAR = 3)
– dequeue(“50"); FRONT = (FRONT+1)%8; ( FRONT = 1, REAR = 3)
– dequeue(“55"); FRONT = (FRONT+1)%8; ( FRONT = 3, REAR = 3)
– dequeue(“60"); FRONT = (FRONT+1)%8; ( FRONT = 4, REAR = 3)

22
 Circular Queue - Advantages
• Effective Memory Utilization or otherwise Less
Memory Wastage than Simple Queue.

• A new item can be inserted in the location

from where a previous item is deleted.

• Infinite number of elements can be added

continuously but deletion must be used.
23
 Priority Queue
• Special type of Queue in which each data items are associated with
Priority Values.
• An item with higher priority is served first than the item with lower
priority.
• Similar priority value items are served in the order in which it is
inserted.
• Can be implemented using heap

INPUT PRIORITY QUEUE

(P,5) (R,50) REAR = 3
(Q,10) ENQUEUE (S,30)
(R,50) (Q,10)
(S,30) (P,5)
FRONT = -1
REAR = -1
FRONT = -1
24
 Priority Queue - Applications
• Bandwidth management
• Discrete event simulation
• Dijkstra's algorithm
• Huffman coding
• Best-first search algorithms
• ROAM triangulation algorithm
• Prim's algorithm for minimum spanning tree

25
 Deque
• Special type of queue that allows insertion
and deletion at both the ends.
ADD & DELETE ADD & DELETE
IN A B C D E F G H IN
LEFT SIDE RIGHT SIDE

REAR FRONT

ENQUEUE ENQUEUE
•enqRear() •enqFront()

DEQUEUE DEQUEUE
•deqRear() •deqFront()

• Application:
• Steal-job scheduling algorithm byIntel's Threading Building Blocks
26
 References
• Website
– [Link]
– [Link]
– [Link]
– [Link]
– [Link]
• YouTube Channels
– Jenny's lectures CS/IT NET&JRF
– naresh i technologies
– Study with jbrtrisea

27
drganeshclasses@[Link]
9791638370

28