1
Data Structures in C++ Note 3
Queue Data Structure
- Queue:
A queue is a sequential storage structure that permits access only at the two ends of the sequence. We refer to the ends of the sequence as the head and tail. A queue inserts new elements at the tail and removes elements from the head of the sequence. You will note that a queue removes elements in the same order in which they were stored, and hence a queue provides FIFO (first-in / first-out), or FCFS (first-come / first-served), ordering.
- Operation of Queue:
Enqueue: insert operation for the queue is adding item to the tail of queue.
Dequeue: remove operation for the queue is deleting item from the head of queue.
- Implementation of Queues:
(1)Pointer-based queue
(2)Array-based queue
- Pointer-based queue:
Enqueue: Insert a new element ‘D’ to the tail of the queue: O(1)
Dequeue: Delete an element from the head of the queue: O(1)
class PoiQueue
{
private:
struct Node{
int data;
Node * next;
};
Node * head;
Node * tail;
public:
PoiQueue();
~PoiQueue();
void Enqueue(int key);
void Dequeue(int&key, bool &success);
void Gethead(int&key, bool &success);
bool IsEmpty( );
};
PoiQueue::PoiQueue()
: head(0), tail(0)
{}
PoiQueue::~PoiQueue()
{
Node * tmp;
while(head!=0)
{
tmp=head;
head=head->next;
tmp->next=0;
delete tmp;
}
tail=0;
}
bool PoiQueue::IsEmpty( )
{
return (head==0);
}
void PoiQueue::EnQueue(int key)
{
Node * newnode= new Node;
newnode->data=key;
newnode->next=null;
if(head==0)
head=tail=newnode;
else
{
tail->next=newnode;
tail=newnode;
}
}
void PoiQueue::DeQueue(int &key, bool &success)
{
Node *tmp=head;
success=(head!=0);
if(success)
{
if(head->next==0)
head=tail=0;
else
head=head->next;
key=tmp->data;
tmp->next=0;
delete tmp;
}
}
void PoiQueue::Gethead(int&key, bool &success)
{
success=(head!=0);
if(success)
key=head->data;
}
- Array-based queue:
The non-circular queue (MAX=8: at most 8 elements in the array):
Graphical Presentation:
0 / 1 / 2 / 3 / 4 / 5 / 6Enqueue: Insert a new element to the tail of the queue: O(1)
0 / 1 / 2 / 3 / 4 / 5 / 6 / 7Dequeue: Delete the element from the head of the queue: worst case is O(n)
1 / 2 / 3 / 4 / 5 / 6 / 7Problem for non-circular queue:
When the element was removed from the head of the queue, all the elements after it have to be moved forward.
The circular queue with 8 elements:
Graphical Presentation (Initially, the queue is empty):
Enqueue(5):
Enqueue(7); Enqueue(20); Enqueue(10); Enqueue(8); Enqueue(2); Enqueue(14); Enqueue(0);
Dequeue();
Dequeue();Dequeue();Dequeue();Dequeue();Dequeue();Dequeue();
Dequeue();
Enqueue(4);
From the above example, we see that the conditions for empty queue and full queue are same, thus we cannot distinguish these two cases. We have two solutions to solve this problems:
(a)Use one more variable size to represent the actual number of elements in the queue.
(b)When we apply for space for the array, we apply for MAX+1 elements and always leave one space empty, that is, when the queue is full, there is one space unused.
(a) Array-based queue with size defined:
class ArrQueue
{
private:
int size;
int A[max];
int head, tail;
public:
ArrQueue();
~ArrQueue();
void Enqueue(int key);
void Dequeue();
void Dequeue(int&key);
void Gethead(int&key);
bool IsEmpty( );
};
ArrQueue::ArrQueue()
Tail(-1), head(0),size(0)
{
}
ArrQueue::~ArrQueue()
{
}
bool ArrQueue:: IsEmpty ()
{
return(size==0);
}
void ArrQueue::Enqueue(int key)
{
if(size<MAX)
{
Use either (1) or (2):
(1)tail++;
if(tail==MAX)
tail=0;
(2)tail=(tail+1)%MAX;
A[tail]=key;
size++;
}
else
cout<”The queue is full”;
}
void ArrQueue::Dequeue()
{
if(size>0)
{
Use either (3) Or (4):
(3)head++;
if(head>=MAX)
head=0;
(4)head =(head+1)% MAX;
size--;
}
else
cout < “The queue is empty”;
}
void ArrQueue::Dequeue(int&key)
{
if (size>0)
{
key=A[head];
use (3) or (4);
size--;
}
else
cout <”Empty Queue”;
}
void ArrQueue::Gethead (int&key)
{
if (size>0)
key=A[head];
else
cout<”empty queue”;
}