STACK & QUEUE

PR E S E N T E D BY :
M R . K I R A N K I S H O R AWA L E ,
 Data Structure

DATA: is simply a value or set of values of

different type (which is called data types like
string, integer, char etc.)
STRUCTURE: Way of organizing information, so
that it is easier to use
Particular way of organizing data
in a computer’s memory so that
DATA it can be used efficiently.
STRUCTURE
A data structure is specialized
format for organizing and
storing data.
 What dose study of data structures
involve???
1. Logical or mathematical description of the
structure.

2. Implementation of structure on a computer

using different computer languages (C)

3. Quantitative analysis of the structure, which

includes determining the amount of memory
needed to store the structure and the time
required to process the structure.
Classification
Classification (Cont…)
 Classification (Cont…)

 LINEAR DATA STRUCTURE: A data structure is

linear if every item is related (or attached) to its
pervious and next item (e.g Array, Linked list)

 NON-LINEAR DATA STRUCTURE: A data structure

is non-linear if every item is attached to many
other items in specific ways to reflect
relationships (e.g Trees)
 Stack Definition

A STACK is a linear list in which additions and

deletions of data are restricted to one end, called
the TOP OF STACK.

If we insert a data series into a stack and then

remove it, the order of data is reversed.

Stacks are known as LIFO (Last In, First Out)

lists.
 Stack Operations

 Insertions and removals are performed individually

 Push: Insertion to stack is called as Push Operation.

 Inserted objects are said to be pushed onto the stack

 The top of the stack is the most recently object pushed onto
the stack

 Pop: Deletion from stack is called as Pop Operation.

 When an object is popped from the stack, the current top is erased
Push and Pop Operations in Stack

Top=Top + 1

Top=Top - 1
Push and Pop Operations in Stack (Cont…)
Consider the following example of pushing
elements A & B into the Stack and then Popping
the element at TOP.
 Some Exceptional Conditions

Overflow:
 In executing the procedure Push, one must test whether there is
room in the stack for new item, if not the we have a condition
called as Overflow.
 In short if we try to insert into a full stack we encounter
Overflow.

Underflow:
 In executing the procedure Pop, one must first test whether
there is an element in the stack, if not then we have a condition
called as Underflow.
 If we try to delete from empty stack we encounter Underflow
condition.
Review

Top Of Stack (TOP/TOS):

Examines the most recently
inserted element
• All the operations (Push /
Pop) take place at TOP

Fundamental operations:
• Push: Equivalent to an
insert
• Associated Exceptional
condition: Overflow
• Pop: Deletes the most
recently inserted element
• Associated Exceptional
condition: Underflow
 Implementation of Stacks

Any list implementation could be used to

implement a stack

 Arrays (static: the size of stack is given initially)

 Linked lists (dynamic: never (conceptually) become full)

Stack Implementation using Array
 Program for Submission

Write a C Program to Implement enlisted

operation on Stack (using Array):
1. Push
2. Pop
3. Display the contents of stack.
 Applications of Stack
1. Recursion
 Function call and return is generally handled by stack

2. Tower of Hanoi

3. Stack is used for Evaluation of Arithmetic Expressions

4. Stack is used for Transforming Polish Notations (Infix to Postfix/Prefix)

5. Stack is used by compilers to check for balancing of parentheses, brackets and braces.

6. Sorting
 Quick Sort is an application of Stack

7. Stack is used for traversal of Non-Linear Data Structures (Trees and Graph)
 1. Recursion as Application of Stack

In general all the function calls and return is

handled using stack
 Applications of Stack

1. Recursion
 Function call and return is generally handled by stack

2. Tower of Hanoi

3. Stack is used for Evaluation of Arithmetic Expressions

4. Stack is used for Transforming Polish Notations (Infix to Postfix/Prefix)

5. Stack is used by compilers to check for balancing of parentheses, brackets and

braces.

6. Sorting
 Quick Sort is an application of Stack

7. Stack is used for traversal of Non-Linear Data Structures (Trees and Graph)
 2. Tower of Hanoi

2. Tower of Hanoi
 2. Tower of Hanoi (Cont…)

 Solution for TOH problem with 3 disks.

 Applications of Stack

1. Recursion
 Function call and return is generally handled by stack

2. Tower of Hanoi

3. Stack is used for Evaluation of Arithmetic Expressions

4. Stack is used for Transforming Polish Notations (Infix to Postfix/Prefix)

5. Stack is used by compilers to check for balancing of parentheses, brackets and

braces.

6. Sorting
 Quick Sort is an application of Stack

7. Stack is used for traversal of Non-Linear Data Structures (Trees and Graph)
 Transforming Polish Notations

Polish Notation:
 Infix
 A+B

 Postfix
 AB+

 Prefix
 +AB
Transforming Polish Notations (Cont…)
 Transforming Polish Notations (Cont…)

Assume the Expression: A + ( B * C – (D / E F)*G)*H

 Applications of Stack

1. Recursion
 Function call and return is generally handled by stack

2. Tower of Hanoi

3. Stack is used for Evaluation of Arithmetic Expressions

4. Stack is used for Transforming Polish Notations (Infix to Postfix/Prefix)

5. Stack is used by compilers to check for balancing of parentheses, brackets and

braces.

6. Sorting
 Quick Sort is an application of Stack

6. Stack is used for traversal of Non-Linear Data Structures (Trees and Graph)
Evaluation of Arithmetic Expressions
Evaluation of Arithmetic Expressions (Cont…)
QUEUE
 Queue Definition

 Queue is a Non-Primitive, Linear, FIFO Data Structure

 It is an ordered group of homogeneous items of

elements.

 Queues have two ends:

 Elements are added/inserted at one end called as Rear end.
 Elements are removed/deleted from the other end called as
Front end.

 The element added first is also removed first (FIFO:

First In, First Out).
 Operations in Queue

Enqueue:
 Insertion operation to the Queue is called as Enqueue.
 Mathematical Operation: Rear = Rear + 1
 Condition to be Checked: Overflow

Dequeue:
 Deletion operation to the Queue is called as Dequeue.
 Mathematical Operation: Front = Front + 1
 Condition to be Checked: Underflow
 Static and Dynamic Queues

Just as stacks are implemented using Arrays

(Static Implementation) or linked list
(Dynamic Implementation), so are queues.
 Implementation of Queue

ENQUEUE ( QUEUE, MAX, FRONT, RARE, NUM)

Step 1: If REAR = MAX – 1 then
Write “Queue Overflow” and Return
[End of IF]
Step 2: IF FRONT = -1 //OR REAR = -1
SET FRONT=0 and REAR=0
ELSE
SET REAR=REAR+1
[END OF IF]
Step 3: SET QUEUE [REAR] = NUM
Step 4: RETURN
 Implementation of Queue (Cont…)

DEQUEUE ( QUEUE, FRONT)

Step 1: If FRONT = -1 then

Write “Queue Underflow” and Return
Step 2: SET VAL=QUEUE [FRONT]
Step 3: If FRONT = REAR
SET FRONT =-1 AND REAR = -1
Else
FRONT = FRONT + 1
Step 2: RETURN
Limitation of Queue (Linear Queue)

2
 Limitation of Queue (Linear Queue) (Cont…)

5. Now Try to insert into the Queue (Enqueue), this will still cause Overflow
though there is space available.
 Types Of Queue

1) Linear Queue (Previously Discussed)

2) Circular Queue
3) Priority Queue
4) Deque Queue
a) Input Restricted Deque
b) Output Restricted Deque
5) Multiple Queue
 Circular Queue

The Arrangement of the elements Q[0], Q[1], ...,Q[n] in a

circular fashion with Q[1] following Q[n] is called
Circular Queue.
The last node is connected to first node to make a circle.
Working with Circular Queue
Working with Circular Queue (Cont…)
Logical Representation/Working

Initial (Empty) Queue After Insertion of 8 elements and

deleting 1 element
Implementation of Circular Queue
Implementation of Circular Queue (Cont…)
 Priority Queue

In priority queue, each element is assigned a

priority.

Priority of an element determines the order in

which the elements will be processed.

Rules:
1. An element with higher priority will processed before an
element with a lower priority.
2. Two elements with the same priority are processed on a
First Come First Serve basis.
 Array Representation of Priority Queue

Insertion Operation:

While inserting elements in priority queue we will
add it at the appropriate position depending on its
priority


It is inserted in such a way that the elements are
always ordered either in Ascending or descending
sequence

Deletion Operation:

While deletion, the element at the front is always
deleted.
Insertion in Priority Queue
Deletion in Priority Queue
 Deque / Double Ended Queue

A list in which elements can be inserted or

deleted either end

Types of Deque:
 Input Restricted Deque:-
 In this dequeue, insertion can be done only at one of the
end, while deletion can be done from both ends.
 Output Restricted Deque:-
 In this dequeue, deletion can be done only at one of the
ends, while insertions can be done on both ends
 Applications of Queue

 Serving requests on a single shared resource, like a printer,

CPU task scheduling etc.
 In real life scenario, Call Centre phone systems uses Queues to
hold people calling them in an order, until a service
representative is free.
 Handling of interrupts in real-time systems. The interrupts are
handled in the same order as they arrive i.e. First come first
served.
 When data is transferred asynchronously (data not necessarily
received at same rate as sent) between two processes.
Examples include IO Buffers, pipes, file IO, etc.
 All types of customer service(like railway reservation) centers
are designed using the concept of queues.
THANK
YOU..