Двухсторонняя очередь
В этом руководстве вы познакомитесь с двухсторонними очередями (их еще называют двусвязными очередями) и узнаете, как их реализовать в Python, Java, C и C++.
Deque или двухсторонняя очередь — тип очереди, в которой вставка и удаление элементов возможна и с начала, и с конца очереди. Это значит, что этот тип очереди не подчиняется принципу FIFO («первый пришел — первый вышел»).
Типы двухсторонних очередей
1. Двухсторонняя очередь с ограниченной вставкой
В этой двухсторонней очереди вставка элементов осуществляется лишь с одной стороны очереди. Удаление все так же доступно с обеих сторон.
2. Двухсторонняя очередь с ограниченным удалением
В этой двухсторонней очереди удаление элементов осуществляется лишь с одной стороны очереди. Вставка так же доступна с обеих сторон.
Операции с двухсторонними очередями
Ниже представлена реализация двухсторонней очереди с помощью круговой очереди. Одна из особенностей круговой очереди заключается в том, что в случае заполнения массива мы все начинаем сначала.
Но в случае с линейным массивом все не так — когда он заполняется, мы не можем добавлять новые элементы.
Перед выполнением следующих операций выполните следующие действия:
- Объявите массив (двухстороннюю очередь) длины
n. - Объявите два указателя и поместите их в начало очереди. После этого присвойте
front= -1, аrear= 0.
1. Вставка в начало очереди
С помощью этой операции мы можем вставить элемент в начало очереди.
• Проверьте позицию указателя front.
• Если front < 1, то объявите его повторно — front = n-1 (последний индекс).
• Иначе увеличьте значение front на 1.
• Добавьте новое значение 5 в array[front].
2. Вставка в конец очереди
С помощью этой операции мы можем вставить элемент в конец очереди.
• Проверьте, не заполнена ли очередь.
• Если очередь заполнена, повторно объявите указатель rear — rear = 0.
• Иначе увеличьте значение rear на 1.
• Добавьте новое значение 5 в array[5].
3. Удаление элемента из начала очереди
С помощью этой операции мы можем удалить элемент из начала очереди.
• Проверьте, не пуста ли очередь.
• Если двухсторонняя очередь пуста (front = -1), удаление произвести не удастся — возникнет антипереполнение.
• Если в очереди один элемент (front = rear), присвойте front = -1 и rear = -1.
• Если же front находится в конце очереди (front = n - 1), присвойте front = 0.
• Иначе присвойте front = front + 1.
4. Удаление из конца очереди
С помощью этой операции мы можем удалить элемент из конца очереди.
• Проверьте, не пуста ли очередь.
• Если двухсторонняя очередь пуста (front = -1), удаление произвести не удастся — возникнет антипереполнение.
• Если в очереди один элемент (front = rear), присвойте front = -1, а rear = -1. Иначе выполняйте следующие шаги.
• Если же rear находится в конце очереди (rear = 0), присвойте rear = n - 1.
• Иначе присвойте rear = rear - 1.
5. Проверка на пустоту
С помощью этой операции можно проверить, не пуста ли двухсторонняя очередь. Если front = -1, она пуста.
6. Проверка на заполненность
С помощью этой операции можно проверить, не заполнена ли двухсторонняя очередь. Если front = 0 и rear = n - 1 ИЛИ front = rear + 1, она заполнена.
Реализация двухсторонних очередей
Python
# Реализация двухсторонней очереди в Python
class Deque:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addRear(self, item):
self.items.append(item)
def addFront(self, item):
self.items.insert(0, item)
def removeFront(self):
return self.items.pop()
def removeRear(self):
return self.items.pop(0)
def size(self):
return len(self.items)
d = Deque()
print(d.isEmpty())
d.addRear(8)
d.addRear(5)
d.addFront(7)
d.addFront(10)
print(d.size())
print(d.isEmpty())
d.addRear(11)
print(d.removeRear())
print(d.removeFront())
d.addFront(55)
d.addRear(45)
print(d.items)Java
// Реализация круговых двухсторонних очередей в Java
class Deque {
static final int MAX = 100;
int arr[];
int front;
int rear;
int size;
public Deque(int size) {
arr = new int[MAX];
front = -1;
rear = 0;
this.size = size;
}
boolean isFull() {
return ((front == 0 && rear == size - 1) || front == rear + 1);
}
boolean isEmpty() {
return (front == -1);
}
void insertfront(int key) {
if (isFull()) {
System.out.println("Переполнение");
return;
}
if (front == -1) {
front = 0;
rear = 0;
}
else if (front == 0)
front = size - 1;
else
front = front - 1;
arr[front] = key;
}
void insertrear(int key) {
if (isFull()) {
System.out.println(" Переполнение ");
return;
}
if (front == -1) {
front = 0;
rear = 0;
}
else if (rear == size - 1)
rear = 0;
else
rear = rear + 1;
arr[rear] = key;
}
void deletefront() {
if (isEmpty()) {
System.out.println("Антипереполнение\n");
return;
}
// В очереди только один элемент
if (front == rear) {
front = -1;
rear = -1;
} else if (front == size - 1)
front = 0;
else
front = front + 1;
}
void deleterear() {
if (isEmpty()) {
System.out.println(" Антипереполнение");
return;
}
if (front == rear) {
front = -1;
rear = -1;
} else if (rear == 0)
rear = size - 1;
else
rear = rear - 1;
}
int getFront() {
if (isEmpty()) {
System.out.println(" Антипереполнение");
return -1;
}
return arr[front];
}
int getRear() {
if (isEmpty() || rear < 0) {
System.out.println(" Антипереполнение\n");
return -1;
}
return arr[rear];
}
public static void main(String[] args) {
Deque dq = new Deque(4);
System.out.println("Вставить элемент в конец очереди : 12 ");
dq.insertrear(12);
System.out.println("Вставить элемент в конец очереди : 14 ");
dq.insertrear(14);
System.out.println("Получаем элемент из конца : " + dq.getRear());
dq.deleterear();
System.out.println("После удаления последнего элемента новый последний элемент : " + dq.getRear());
System.out.println("Вставляем элемент в начало");
dq.insertfront(13);
System.out.println("Получить первый элемент из начала: " + dq.getFront());
dq.deletefront();
System.out.println("После удаления первого элемента из начала очереди новый первый элемент : " + +dq.getFront());
}
}С
// Реализация круговых двухсторонних очередей в C
#include <stdio.h>
#define MAX 10
void addFront(int *, int, int *, int *);
void addRear(int *, int, int *, int *);
int delFront(int *, int *, int *);
int delRear(int *, int *, int *);
void display(int *);
int count(int *);
int main() {
int arr[MAX];
int front, rear, i, n;
front = rear = -1;
for (i = 0; i < MAX; i++)
arr[i] = 0;
addRear(arr, 5, &front, &rear);
addFront(arr, 12, &front, &rear);
addRear(arr, 11, &front, &rear);
addFront(arr, 5, &front, &rear);
addRear(arr, 6, &front, &rear);
addFront(arr, 8, &front, &rear);
printf("\nЭлементы в двухсторонней очереди: ");
display(arr);
i = delFront(arr, &front, &rear);
printf("\nудален элемент: %d", i);
printf("\nОчередь после удаления элемента: ");
display(arr);
addRear(arr, 16, &front, &rear);
addRear(arr, 7, &front, &rear);
printf("\nОчередь после вставки элемента: ");
display(arr);
i = delRear(arr, &front, &rear);
printf("\nудален элемент: %d", i);
printf("\nОчередь после удаления элемента: ");
display(arr);
n = count(arr);
printf("\nКоличество элементов в очереди: %d", n);
}
void addFront(int *arr, int item, int *pfront, int *prear) {
int i, k, c;
if (*pfront == 0 && *prear == MAX - 1) {
printf("\nОчередь заполнена.\n");
return;
}
if (*pfront == -1) {
*pfront = *prear = 0;
arr[*pfront] = item;
return;
}
if (*prear != MAX - 1) {
c = count(arr);
k = *prear + 1;
for (i = 1; i <= c; i++) {
arr[k] = arr[k - 1];
k--;
}
arr[k] = item;
*pfront = k;
(*prear)++;
} else {
(*pfront)--;
arr[*pfront] = item;
}
}
void addRear(int *arr, int item, int *pfront, int *prear) {
int i, k;
if (*pfront == 0 && *prear == MAX - 1) {
printf("\nОчередь заполнена.\n");
return;
}
if (*pfront == -1) {
*prear = *pfront = 0;
arr[*prear] = item;
return;
}
if (*prear == MAX - 1) {
k = *pfront - 1;
for (i = *pfront - 1; i < *prear; i++) {
k = i;
if (k == MAX - 1)
arr[k] = 0;
else
arr[k] = arr[i + 1];
}
(*prear)--;
(*pfront)--;
}
(*prear)++;
arr[*prear] = item;
}
int delFront(int *arr, int *pfront, int *prear) {
int item;
if (*pfront == -1) {
printf("\nОчередь пуста.\n");
return 0;
}
item = arr[*pfront];
arr[*pfront] = 0;
if (*pfront == *prear)
*pfront = *prear = -1;
else
(*pfront)++;
return item;
}
int delRear(int *arr, int *pfront, int *prear) {
int item;
if (*pfront == -1) {
printf("\nОчередь пуста.\n");
return 0;
}
item = arr[*prear];
arr[*prear] = 0;
(*prear)--;
if (*prear == -1)
*pfront = -1;
return item;
}
void display(int *arr) {
int i;
printf("\n front: ");
for (i = 0; i < MAX; i++)
printf(" %d", arr[i]);
printf(" :конец");
}
int count(int *arr) {
int c = 0, i;
for (i = 0; i < MAX; i++) {
if (arr[i] != 0)
c++;
}
return c;
}C++
// Реализация круговых двухсторонних очередей в C++
#include <iostream>
using namespace std;
#define MAX 10
class Deque {
int arr[MAX];
int front;
int rear;
int size;
public:
Deque(int size) {
front = -1;
rear = 0;
this->size = size;
}
void insertfront(int key);
void insertrear(int key);
void deletefront();
void deleterear();
bool isFull();
bool isEmpty();
int getFront();
int getRear();
};
bool Deque::isFull() {
return ((front == 0 && rear == size - 1) ||
front == rear + 1);
}
bool Deque::isEmpty() {
return (front == -1);
}
void Deque::insertfront(int key) {
if (isFull()) {
cout << "Переполнение\n"
<< endl;
return;
}
if (front == -1) {
front = 0;
rear = 0;
}
else if (front == 0)
front = size - 1;
else
front = front - 1;
arr[front] = key;
}
void Deque ::insertrear(int key) {
if (isFull()) {
cout << " Переполнение\n " << endl;
return;
}
if (front == -1) {
front = 0;
rear = 0;
}
else if (rear == size - 1)
rear = 0;
else
rear = rear + 1;
arr[rear] = key;
}
void Deque ::deletefront() {
if (isEmpty()) {
cout << "Антипереполнение\n"
<< endl;
return;
}
if (front == rear) {
front = -1;
rear = -1;
} else if (front == size - 1)
front = 0;
else
front = front + 1;
}
void Deque::deleterear() {
if (isEmpty()) {
cout << " Антипереполнение\n"
<< endl;
return;
}
if (front == rear) {
front = -1;
rear = -1;
} else if (rear == 0)
rear = size - 1;
else
rear = rear - 1;
}
int Deque::getFront() {
if (isEmpty()) {
cout << " Антипереполнение\n"
<< endl;
return -1;
}
return arr[front];
}
int Deque::getRear() {
if (isEmpty() || rear < 0) {
cout << " Антипереполнение\n"
<< endl;
return -1;
}
return arr[rear];
}
int main() {
Deque dq(4);
cout << "Вставить элемент в конец очереди \n";
dq.insertrear(5);
dq.insertrear(11);
cout << "Последний элемент: "
<< dq.getRear() << endl;
dq.deleterear();
cout << "После удаления последнего элемента новый последний элемент: " << dq.getRear() << endl;
cout << "Вставка в начало очереди \n";
dq.insertfront(8);
cout << "Первый элемент: " << dq.getFront() << endl;
dq.deletefront();
cout << "После удаления первого элемента новый первый элемент: " << dq.getFront() << endl;
}Временная сложность
Временная сложность всех вышеприведенных операций — O(1).
Где применяются двухсторонние списки
- Операции отмены в ПО.
- Хранение истории браузера.
- Реализация очередей и стеков.
