Data Structure and Algorithm
CSC - 220
Lecture 10
Queues
Dr. Muhammad Ayaz
Data Structure Hierarchy
Data Structures
Linear Non Linear
Sequential
Direct Access
Access Graphs Trees
Homogeneous Heterogeneous Last-in, First-in,
General
Components Components Last-out First-out
Arrays Record List Stack Queue
Queue
• Queue: is an abstract data type (ADT) in which
items are added at one end (the rear) and
removed from the other end (the front).
• Queue is a FIFO “First In, First Out” structure.
– The first item in, is the first item served (out).
Basic Idea - Queue
• Queue is an abstract data structure, somewhat
similar to Stacks.
• Unlike stacks, a queue is open at both its ends. One
end is always used to insert data (enqueue) and the
other is used to remove data (dequeue).
En-queue and De-queue
Deque
A deque is a Double-End queue — items can be
inserted and removed from both sides
Stacks, Queues, and Deques
• A stack is a last in, first out (LIFO) data structure
– Items are removed from a stack in the reverse order
from the way they were inserted
• A queue is a first in, first out (FIFO) data structure
– Items are removed from a queue in the same order as
they were inserted
• A deque is a Double-End queue—items can be inserted
and removed at either end
Using of Queue
• “Buffer” for printer uses a queue.
• Operating System (OS) uses “Priority Queues”.
• Simulation applications and commercial offices use
queues to model customers waiting in a line.
• Any problem requiring FIFO property should use a
queue.
Note: Buffer is a region of memory used to temporarily hold data.
Queue Operations
Queue – Possible Operations
enqueue
dequeue
create
QUEUE
isempty
size
Stack Operations 8
Queue Operations (cont.)
Transformers
•Enqueue
•Dequeue Change state
•MakeEmpty
Observers
•IsEmpty Observe state
•IsFull
Basic Operations of Queue
Example 1 – Queues using Arrays
Example 2 – Queues using ArrayLists
void enqueue (queue *q, int element);
/* Insert an element in the queue */
int dequeue (queue *q);
/* Remove an element from the queue */
queue *create();
/* Create a new queue */
int isempty (queue *q);
/* Check if queue is empty */
int size (queue *q);
/* Return the no. of elements in queue */
Assumption: queue contains integer elements!
Implementation of 15
Stacks
Implementation of Queues
• Queues can be implemented using:
• Array (static: the size of queue is given initially).
• ArraysList (static and dynamic: never become full).
• Linked Lists (dynamic: never become full).
• Let us now see how to use Array and ArrayList to implement a
queue.
Implementation of Stacks – using 18
Array
Queue class – using Array
class CQueue {
private int front,rear,counter;
private int [] values;
public CQueue() {
values = new int[10];
front = 0;
rear = -1;
counter = 0;
}
.
.
.
};
Note: In Stacks, there was “top” that serves similar purpose like counter
Implementation of Stacks – using 18
Array
Enqueue class – using Array
Dequeue class – using Array
Priority Queues
• As we know, a queue is a data structure where the first item
placed in the structure is the first item taken out of the
structure.
• The effect of the behavior is the oldest item in the structure
that is removed first.
• For many applications, though, a data structure is needed
where an item with the highest priority is removed first, even
if it is not the “oldest” item in the structure.
Priority Queue Operations
Priority Queues: Example
Priority Queues: Example Solution
Priority Queues: Example Solution
…
Problem in Linear Queues ?
Solution: Circular Queue?
Circular Array …
Circular Array …
Circular Array Time Complexity
Allocation of Memory
Basic idea:
• Create a linked list to which items would be added to one end
and deleted from the other end.
• Two pointers will be maintained:
• One pointing to the beginning of the list (point from where
elements will be deleted).
• Another pointing to the end of the list (point where new
elements will be inserted).
Rear
Front DELETION INSERTION
ENQUEUE
front rear
DEQUEUE
front rear
Implementation of Queue
(Using Linked-List)
Key idea: allocate memory as required
•Keep Linked List with pointers to front and
rear.
•Each queue item stored in a node.
•Each node has two fields: item and next.
Queues using Linked List - Example
Queues using Linked List – Example
…
Implementation of Queue
(Circular Array)