Очередь - это полезная структура данных в программировании. Представьте очередь билетов за пределами кинозала, где первый человек, входящий в очередь, является первым человеком, который получает билет.
Очередь следует правилу «первым пришел - первым обслужен» (First In First Out - FIFO) - элемент, который идет первым, - это элемент, который выходит первым.
Рассмотрим рисунок. Поскольку 1 помещена в очередь до 2, она так же уйдет первой из очереди. Это следует правилу FIFO.
С точки зрения программирования, помещение элемента в очередь (empty queue - пустая очередь) называется "enqueue" (постановка в очередь), а удаление элемента из очереди - "dequeue" (снятие очереди).
Мы можем реализовать очередь на любом языке программирования, таком как C, C ++, Java, Python или C #, почти с одинаковой спецификацией.
Технические характеристики очереди
Очередь - это объект или, более конкретно, абстрактная структура данных (ADT), которая позволяет выполнять следующие операции:
- Enqueue: добавить элемент в конец очереди;
- Dequeue: удалить элемент из начала очереди;
- IsEmpty: проверить, пуста ли очередь;
- IsFull: проверьте, заполнена ли очередь;
- Peek: получить значение начала очереди, не удаляя его.
Как работает очередь
Операции с очередями работают следующим образом:
- Два указателя, называемые FRONT и REAR, используются для отслеживания первого и последнего элементов в очереди.
- При инициализации очереди мы устанавливаем значение FRONT и REAR равным -1.
- При добавлении элемента мы увеличиваем значение индекса REAR и помещаем новый элемент в положение, на которое указывает REAR.
- При удалении элемента из очереди мы возвращаем значение, на которое указывает FRONT, и увеличиваем индекс FRONT.
- Перед постановкой в очередь мы проверяем, заполнена ли очередь.
- Перед снятием очереди мы проверяем, пуста ли очередь.
- При инициализации первого элемента мы устанавливаем значение FRONT в 0.
- При удалении последнего элемента мы сбрасываем значения FRONT и REAR в -1.
Реализация очереди на языке программирования
Наиболее распространенная реализация очереди использует массивы, но также очередь может быть реализована с использованием списков.
Реализация с использованием C-программирования
#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]);
}
}
Когда вы запускаете эту программу, вы получаете следующее:
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
Реализация с использованием программирования на C ++
#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;
}
После запуска мы получим:
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
Ограничение этой реализации
Как вы можете видеть на изображении ниже, через некоторое время после добавления в очередь и удаления из очереди, размер очереди был уменьшен.
Индексы 0 и 1 могут использоваться только после сброса очереди, когда все элементы удалены.
Изменяя код для очереди, мы можем использовать пространство путем реализации модифицированной очереди, называемой циклической очередью.
