Queue
BLG221E
QUEUES
A queue is a linear list in which data can only be inserted
at one end, called the rear, and deleted from the other
end, called the front.
These restrictions ensure that the data is processed in
the order in which it is received. In other words, a queue
is a first in, first out (FIFO) structure.
Queue Structure
It is possible to access the structure from two points.
A back pointer (back) marks the position where new
arrivals will be added.
A front pointer (front) marks the position where is the
data to be processed.
A1 A2 A3 A4
front back
Operations on queues
Although we can define many operations for a queue, four
are basic: queue, enqueue, dequeue and empty, as defined
below.
The queue operation:
The queue operation creates an empty
queue. The following shows the format.
The enqueue operation
The enqueue operation inserts an item at the rear of the
queue. The following picture shows the format.
The dequeue operation
The dequeue operation deletes the item at the front of
the queue. The following shows the format.
The empty operation
The empty operation checks the status of the queue.
This operation returns true if the queue is empty and
false if the queue is not empty.
Queues applications
Queues have many applications in computer systems:
Any application where a group of items is waiting to use a
shared resource will use a queue. e.g.
jobs in a single processor computer
print spooling
information packets in computer networks.
Recognizing Palindromes
A palindrome
A string of characters that reads
the same from left to right as its
does from right to left
To recognize a palindrome, a queue can be used in conjunction
with a stack
A stack reverses the order of occurrences
A queue preserves the order of occurrences
Recognizing Palindromes Algorithm
Compare the characters at the front
of the queue and the top of the stack.
The results of inserting a string
into both a queue and a stack
Compare the characters at the
front of the queue and the top
of the stack
Categorizing Data
Categorizing Data is the rearrangement of data without destroying
their basic sequence.
As an example: suppose, we need to categorize following list into four
different groups without destroying their basic sequence.
Initial list of numbers:
3 22 12 6 10 34 65 29 9 30 81 4 5 19 20 57 44 99
We need to categorize them into four different groups:
Group 1: less than 10 The solution: we build a queue for each of the
four categories. We than store the numbers in
Group 2: between 10 and 19 the appropriate queue as we read them.
Group 3: between 20 and 29 After all the data have been processed, we
print each queue to demonstrate that we
Group4: 30 and greater categorized data correctly.
| 3 6 9 4 5 | 12 10 19 | 22 29 20 | 34 65 30 81 57 44 99
Implementations of the Queue
Array-based implementations of queue
1. An array-based implementation of queue
2. A circular array-based implementation of queue
Linked List implementations of queue
1. A linear linked list with two external references
• A reference to the front
• A reference to the back
2. A circular linked list with one external reference
• A reference to the back
An error condition occurs
Queue implementation details when an item is being tried
to insert into a full queue,
called as overflow.
With an array implementation:
you can have both overflow and underflow
An error condition occurs
when an item is called
from the queue, but
the queue is empty, called
as underflow.
With a linked-list implementation:
you can have underflow
overflow is a global out-of-memory condition
Array implementation of queues
0 1 2 3 4 5 6 7
myQueue: 17 23 97 44
front = 0 rear = 3
Front and rear variables hold the index values of the locations.
To insert: put new element in location 4, and set rear to 4
To delete: take element from location 0, and set front to 1
Array implementation of queues
front = 0 rear = 3
Initial queue: 17 23 97 44
After 17 23 97 44 333
insertion:
After deletion: 23 97 44 333
front = 1 rear = 4
Problem: Notice how the array contents “crawl” to
the right as elements are inserted and deleted.
This will be a problem after a while!
Circular arrays
We can treat the array (holding the queue elements) as circular
(joined at the ends)
0 1 2 3 4 5 6 7
myQueue: 44 55 11 22 33
rear = 1 front = 5
Elements were added to this queue in the order 11, 22, 33,
44, 55, and will be removed in the same order
Delete: front = (front + 1)
Add: rear = (rear + 1)
Circular arrays
0 1 2 3 4 5 6 7
myQueue: 44 55 11 22 33
rear = 1 front = 5
0 1 2 3 4 5 6 7
enqueue(66) 44 55 66 11 22 33
rear = 2 front = 5
0 1 2 3 4 5 6 7
enqueue(77) 44 55 66 77 11 22 33
rear = 3 front = 5
Circular arrays
0 1 2 3 4 5 6 7
enqueue(77) 44 55 66 77 11 22 33
rear = 3 front = 5
0 1 2 3 4 5 6 7
enqueue(88) 44 55 66 77 88 11 22 33
rear = 4 front = 5
Queues with one element
0 1 2 3 4 5 6 7
myQueue: 88
rear = 4 front = 4
If the queue is completely empty, it would look like this:
0 1 2 3 4 5 6 7
myQueue:
rear = 4 front = 5
Full and empty queues
If the queue iscompletely full, it would look like this:
0 1 2 3 4 5 6 7
myQueue: 44 55 66 77 88 11 22 33
rear = 4 front = 5
If the queue is completely empty, it would look like this:
0 1 2 3 4 5 6 7
myQueue:
rear = 4 front = 5
So, we need extra mechanism to distinguish
This is a problem! between queue-full and queue-empty
conditions.
Solutions for Queue-Empty/Queue-Full Problem
1. Using a counter to keep the number items in the queue.
• Initialize count to 0 during creation; Increment count by 1 during
insertion; Decrement count by 1 during deletion.
• count=0 empty; count=MAX_QUEUE full
2. Using isFull flag to distinguish between the full and empty
conditions.
• When the queue becomes full, set isFullFlag to true; When the
queue is not full set isFull flag to false;
3. Using an extra array location (leaving at least one empty
location in the queue). ( MORE EFFICIENT )
• Declare MAX_QUEUE+1 locations for the array items, but only use
MAX_QUEUE of them. We do not use one of the array locations.
• Full: front equals to (back+1)
• Empty: front equals to back
Using a counter queue-empty
To initialize the queue, set
front to 0
back to MAX_QUEUE–1
count to 0 Count=0
0 1 2 3 4 5 6 7
Inserting into a queue
back Count=1
back = (back+1); front
items[back] = newItem; 0 1 2 3 4 5 6 7
++count;
front back Count=2
Deleting from a queue queue-full
front = (front+1);
0 1 2 3 4 5 6 7
--count;
Full: count == MAX_QUEUE
Empty: count == 0
front Count=8 back
Using isFull flag
To initialize the queue, set
front = 0; back = MAX_QUEUE–1; isFull = false;
Inserting into a queue
back = (back+1);
items[back] = newItem; queue-empty
if ((back+1 == front)) isFull = true;
Deleting from a queue
front = (front+1);
isFull = false;
Full: isFull == true
Empty: isFull == false ; back+1 == front; queue-full
Using an extra array location
To initialize the queue, allocate
(MAX_QUEUE+1) locations
front=0; back=0;
Front holds the index of the location.
Inserting into a queue (if queue is not full)
back = (back+1);
empty queue items[back] = newItem;
Deleting from a queue (if queue is not empty)
front = (front+1);
Full: (back+1)== front
Empty: front == back
full queue
Linked-list implementation of queues
In a queue, insertions occur at one end, deletions at the other end
Operations at the front of a singly-linked list are O(1), but at the other
end they are O(n)
Because you have to find the last element each time
BUT: there is a simple way to use a singly-linked list to implement
both insertions and deletions in O(1) time
You always need a pointer for the first element in the list
You can keep an additional pointer for the last element in the
list
Linked-list (pointer-based) implementations of queue
a linear linked list with
two external pointers
a circular linear linked
list with one external
pointer
Empty queue
• front : Used for dequeue operation.
• back: Used for enqueue operation.
front back
enqueue(60) enqueue(40)
front back front back
60 60 40
enqueue(50)
front back
60 40 50
front back
60 40 50
dequeue() dequeue()
front back
front back
40 50 50
60dequeued 40 dequeued
dequeue()
front back
50dequeued
Enqueueing a node
Node to
last be
first enqueued
44 97 23 17
To enqueue (add) a node:
Find the current last node
Change it to point to the new last node
Change the last pointer in the list header
Dequeueing a node
last
first
44 97 23 17
To dequeue (remove) a node:
Copy the address from the first node into the first pointer
A Pointer-Based Implementation -- enqueue
Inserting an item into a nonempty queue
Inserting an item into an empty queue
a) before insertion b) after insertion
A Pointer-Based Implementation -- dequeue
Deleting an item from a queue of more than one item
Deleting an item from a queue with one item
tempPtr = frontPtr;
frontPtr = NULL;
backPtr = NULL;
tempPtr delete tempPtr;
before deletion after deletion
Array implementation of Queue
#include <stdio.h>
#include <stdlib.h> 0 1 2 3 4 5 6 7
#define MAX 50
int queue_array[MAX];
int rear = - 1; rear
int front = - 1; front
Enqueue
void insert() { 0 1 2 3 4 5 6 7
int add_item;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else front rear
{
if (front == - 1) front = 0;
printf("Insert the element in queue : ");
scanf("%d", &add_item);
rear = rear + 1;
Queue-full
queue_array[rear] = add_item ;
} 0 1 2 3 4 5 6 7
} /*End of insert()*/
front rear
Array implementation of Queue
void delete1() {
if (front == - 1 || front > rear) { 0 1 2 3 4 5 6 7
printf("Queue Underflow \n");
return ;
} rear
front
else
{
printf("Element deleted from queue is Dequeue (delete)
: %d\n", queue_array[front]);
0 1 2 3 4 5 6 7
front = front + 1;
}
} /*End of delete() */ rear
front
void display() {
int i;
if (front == - 1 || front > rear)
printf("Queue is empty \n");
else
0 1 2 3 4 5 6 7
{
printf("Queue is : \n");
for (i = front; i <= rear; i++)
printf("%d ", queue_array[i]); front rear
printf("\n");
} } /*End of display() */
Array implementation of Queue
main() {
int choice;
while (1)
{
printf("[Link] element to queue \n");
printf("[Link] element from queue \n");
printf("[Link] all elements of queue \n");
printf("[Link] \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
insert(); break;
case 2:
delete1(); break;
case 3:
display(); break;
case 4:
exit(1);
default:
printf("Wrong choice \n");
}}}
Linked List implemantation of Queues
#include <stdio.h>
#include <stdlib.h>
struct node
{
int info;
node *ptr;
} *front,*rear,*temp,*front1;
int frontelement();
void enq(int data);
void deq();
void empty();
void display();
void create();
void queuesize();
int count = 0;
Linked List implemantation of Queues
int main() case 2:
{ deq();
int no, ch, e; break;
case 3:
printf("\n 1 - Enquee"); e = frontelement();
printf("\n 2 - Dequee"); if (e != 0)
printf("\n 3 - Front element"); printf("Front element : %d", e);
printf("\n 4 - Empty"); else
printf("\n 5 - Exit"); printf("\n No front element in Queue as queue is
printf("\n 6 - Display"); empty");
printf("\n 7 - Queue size"); break;
create(); case 4:
empty();
while (1) { break;
printf("\n Enter choice : "); case 5:
scanf("%d", &ch); exit(0);
switch (ch) case 6:
{ display(); break;
case 1: case 7:
printf("Enter data : "); queuesize(); break;
scanf("%d", &no); default:
enq(no); printf("Wrong choice, Please enter correct choice");
break; break;
} } }
Linked List implemantation of Queues
/* Create an empty queue */
void create()
{
front = rear = NULL;
}
/* Returns queue size */
void queuesize()
{
printf("\n Queue size : %d", count);
}
front rear
Empty queue
Linked List implemantation of Queues
front rear
/* Enqueing the queue */
Empty queue
void enq(int data)
{
front rear
if (rear == NULL)
{
rear = new node;
rear->ptr = NULL;
rear->info = data; Inserting first node
front = rear;
} data
else
{
temp=new node;
else
rear->ptr = temp; front rear
temp->info = data;
temp->ptr = NULL; Inserting a
rear = temp;
new node
}
count++;
} data1 data2
New node
Linked List implemantation of Queues
/* Displaying the queue elements */
void display() { front rear
front1 = front;
Empty queue
if ((front1 == NULL) && (rear == NULL)) {
printf("Queue is empty");
return;
}
while (front1 != rear) {
printf("%d ", front1->info);
front1 = front1->ptr;
}
if (front1 == rear) printf("%d", front1->info); }
front front1 rear
Queue
data data data
Linked List implemantation of Queues
/* Dequeing the queue */ front rear
void deq()
{
front1 = front;
if (front1 == NULL)
{ Empty queue
printf("\n Error: Trying to display elements
from empty queue");
return; front rear
}
else
if (front1->ptr != NULL)
{
front1 = front1->ptr;
printf("\n Dequed value : %d", front->info);
delete front; front = front1;
}
data
else
{ Deleting first node
printf("\n Dequed value : %d", front->info);
delete front;
front = NULL; rear = NULL;
}
count--; }
Linked List implemantation of Queues
/* Returns the front element of queue */ front rear
int frontelement() Empty queue
{
if ((front != NULL) && (rear != NULL))
return(front->info);
else
return 0;
}
/* Display if queue is empty or not */
void empty()
{
if ((front == NULL) && (rear == NULL))
printf("\n Queue empty");
else
printf("Queue not empty");
}