A queue is a useful data structure in programming. Imagine a queue of tickets outside of a movie theater where the first person to enter the queue is the first person to receive a ticket.
The queue follows the First In First Out (FIFO) rule - the element that comes first is the element that comes out first.
Consider the drawing. Since 1 is queued before 2, it will also be the first to leave the queue. It follows the FIFO rule.
From a programming point of view, placing an element in the queue (empty queue - an empty queue) is called "enqueue", and removing an element from the queue is called "dequeue".
We can implement a queue in any programming language like C, C++, Java, Python or C# with almost the same specification.
Technical characteristics of the queue
A queue is an object, or more specifically an abstract data structure (ADT), that allows you to perform the following operations:
- Enqueue: add an element to the end of the queue;
- Dequeue: remove an element from the front of the queue;
- IsEmpty: check if the queue is empty;
- IsFull: check if the queue is full;
- Peek: get the value of the start of the queue without deleting it.
How the queue works
Queue operations work like this:
- Two pointers called FRONT and REAR are used to keep track of the first and last elements in the queue.
- When initializing the queue, we set the value of FRONT and REAR to -1.
- When adding an element, we increment the value of the REAR index and place the new element at the position pointed to by REAR.
- When removing an element from the queue, we return the value pointed to by FRONT and increment the FRONT index.
- Before queuing, we check if the queue is full.
- Before removing the queue, we check if the queue is empty.
- When initializing the first element, we set the value of FRONT to 0.
- When removing the last element, we reset the FRONT and REAR values to -1.
Implementation of a queue in a programming language
The most common implementation of a queue uses arrays, but a queue can also be implemented using lists.
Implementation using C programming
#include<stdio.h>
#define SIZE 5
void enQueue(int);
void deQueue();
void display();
int items[SIZE], front = -1, rear = -1;
int main()
{
//deQueue невозможно в пустой очереди
deQueue();
//enQueue 5 elements
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
//6-й элемент не может быть добавлен в очередь, потому что очередь заполнена
enQueue(6);
display();
//deQueue удаляет элемент, введенный первым, т.е. 1
deQueue();
//Теперь у нас всего 4 элемента
display();
return 0;
}
void enQueue(int value){
if(rear == SIZE-1)
printf("\nQueue is Full!!");
else {
if(front == -1)
front = 0;
rear++;
items[rear] = value;
printf("\nInserted -> %d", value);
}
}
void deQueue(){
if(front == -1)
printf("\nQueue is Empty!!");
else{
printf("\nDeleted : %d", items[front]);
front++;
if(front > rear)
front = rear = -1;
}
}
void display(){
if(rear == -1)
printf("\nQueue is Empty!!!");
else{
int i;
printf("\nQueue elements are:\n");
for(i=front; i<=rear; i++)
printf("%d\t",items[i]);
}
}
When you run this program, you get the following:
Queue is Empty!! Inserted -> 1 Inserted -> 2 Inserted -> 3 Inserted -> 4 Inserted -> 5 Queue is Full!! Queue elements are: 1 2 3 4 5 Deleted : 1 Queue elements are: 2 3 4 5
Implementation using C programming ++
#include <iostream>
#define SIZE 5
using namespace std;
class Queue {
private:
int items[SIZE], front, rear;
public:
Queue(){
front = -1;
rear = -1;
}
bool isFull(){
if(front == 0 && rear == SIZE - 1){
return true;
}
return false;
}
bool isEmpty(){
if(front == -1) return true;
else return false;
}
void enQueue(int element){
if(isFull()){
cout << "Queue is full";
} else {
if(front == -1) front = 0;
rear++;
items[rear] = element;
cout << endl << "Inserted " << element << endl;
}
}
int deQueue(){
int element;
if(isEmpty()){
cout << "Queue is empty" << endl;
return(-1);
} else {
element = items[front];
if(front >= rear){
front = -1;
rear = -1;
} /* В Q есть только один элемент, поэтому мы удаляем очередь после удаления. */
else {
front++;
}
cout << endl << "Deleted -> " << element << endl;
return(element);
}
}
void display()
{
/* Функция для отображения элементов очереди */
int i;
if(isEmpty()) {
cout << endl << "Empty Queue" << endl;
}
else
{
cout << endl << "Front -> " << front;
cout << endl << "Items -> ";
for(i=front; i<=rear; i++)
cout << items[i] << ""\t";
cout << endl << "Rear -> " << rear << endl;
}
}
};
int main()
{
Queue q;
//deQueue невозможно в пустой очереди
q.deQueue();
//enQueue 5 элементов
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
//6-й элемент не может быть добавлен в очередь, потому что очередь заполнена
q.enQueue(6);
q.display();
//deQueue удаляет элемент, введенный первым, т.е. 1
q.deQueue();
//Теперь у нас всего 4 элемента
q.display();
return 0;
}
After running we will get:
Queue is empty Inserted 1 Inserted 2 Inserted 3 Inserted 4 Inserted 5 Queue is full Front -> 0 Items -> 1 2 3 4 5 Rear -> 4 Deleted -> 1 Front -> 1 Items -> 2 3 4 5 Rear -> 4
Limitation of this implementation
As you can see in the image below, some time after being added to the queue and removed from the queue, the size of the queue was reduced.
Indexes 0 and 1 can only be used after the queue has been flushed when all elements have been removed.
By changing the code for the queue, we can use the space by implementing a modified queue called a circular queue.
