«

»

Дек

Дек (deque — double ended queue, «двусторонняя очередь») – структура данных типа «список», функционирующая одновременно по двум принцам организации данных: FIFO и LIFO. Определить дек можно как очередь с двумя сторонами, так и стек, имеющий два конца. То есть данный подвид списка характерен двухсторонним  доступом: выполнение поэлементной операции, определенной над деком, предполагает возможность выбора одной из его сторон в качестве активной.

 

Дек (двусторонняя очередь)

Двусторонняя очередь

 

Число основных операций, выполняемых над стеком и очередью, как помнит читатель, равнялось трем: добавление элемента, удаление элемента, чтение элемента. При этом не указывалось место структуры данных, активное в момент их выполнения, поскольку ранее оно однозначно определялось свойствами (определением) самой структуры. Теперь, ввиду дека как обобщенного случая, для приведенных операций следует указать эту область. Разделив каждую из операций на две: одну применительно к «голове» дека, другую – его «хвосту», получим набор из шести операций:

  • добавление элемента в начало;
  • добавление элемента в конец;
  • удаление первого элемента;
  • удаление последнего элемента;
  • чтение первого элемента;
  • чтение последнего элемента.

На практике этот список может быть дополнен проверкой дека на пустоту, получением его размера и некоторыми другими операциями.

В плане реализации двусторонняя очередь очень близка к стеку и обычной очереди: в качестве ее базиса приемлемо использовать как массив, так и список. Далее мы напишем интерфейс обработки дека, представленного обычным индексным массивом.  Программа будет состоять из основной части и девяти функций:

  • Creation – обнуляет указатель на конец, так сказать создает дек;
  • Full – проверяет дек на наличие элементов;
  • AddL – добавляет элемент в начало;
  • AddR – добавляет элемент в конец;
  • DeleteL – удаляет первый элемент;
  • DeleteR – удаляет последний элемент;
  • OutputL – выводит первый элемент;
  • OutputR – выводит последний элемент;
  • Size – выводит количество элементов дека;

Помимо самого массива потребуется указатель на последний элемент, назовем его last. Указатель на первый элемент не потребуется, поскольку дек будет представлять собой смещающуюся структуру, т. е. при добавлении нового элемента в начало, каждый из старых элементов сместиться на одну позицию вправо, уступив тем самым первому элементу ячейку с индексом 0 (в C++), следовательно, адрес первого элемента – константа.

Программная реализация дека на основе массива:

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include "stdafx.h"
#include <iostream>
using namespace std;
const int N=5; //размер дека
struct Deque
{
int data[N]; //массив данных
int last; //указатель на конец
};
void Creation(Deque *D) //создание дека
{ D->last=0; }
bool Full(Deque *D) //проверка дека на пустоту
{
if (D->last==0) return true;
else return false;
}
void AddL(Deque *D) //добавление элемента в начало
{
if (D->last==N)
{ cout<<"\nДек заполнен\n\n"; return; }
int value;
cout<<"\nЗначение > "; cin>>value;
for (int i=D->last; i>0; i--)
D->data[i]=D->data[i-1];
D->data[0]=value;
D->last++;
cout<<endl<<"Элемент добавлен\n\n";
}
void AddR(Deque *D) //добавление элемента в конец
{
if (D->last==N)
{ cout<<"\nДек заполнен\n\n"; return; }
int value;
cout<<"\nЗначение > "; cin>>value;
D->data[D->last++]=value;
cout<<endl<<"Элемент добавлен\n\n";
}
void DeleteL(Deque *D) //удаление первого элемента
{
for (int i=0; i<D->last; i++) //смещение элементов
D->data[i]=D->data[i+1]; D->last--;
}
void DeleteR(Deque *D) //удаление последнего элемента
{ D->last--; }
int OutputL(Deque *D) //вывод первого элемента
{ return D->data[0]; }
int OutputR(Deque *D) //вывод последнего элемента
{ return D->data[D->last-1]; }
int Size(Deque *D) //размер дека
{ return D->last; }
//******************************************
int main() //главная функция
{
setlocale(LC_ALL,"Rus");
Deque D;
Creation(&D);
char number;
do
{
cout<<"1. Добавить элемент в начало"<<endl;
cout<<"2. Добавить элемент в конец"<<endl;
cout<<"3. Удалить первый элемент"<<endl;
cout<<"4. Удалить последний элемент"<<endl;
cout<<"5. Вывести первый элемент"<<endl;
cout<<"6. Вывести последний элемент"<<endl;
cout<<"7. Узнать размер дека"<<endl;
cout<<"0. Выйти\n\n";
cout<<"Номер команды > "; cin>>number;
switch (number)
{
case '1': AddL(&D);
break;
//-----------------------------------------------
case '2': AddR(&D);
break;
//-----------------------------------------------
case '3':
if (Full(&D)) cout<<endl<<"Дек пуст\n\n";
else
{
DeleteL(&D);
cout<<endl<<"Элемент удален из дека\n\n";
} break;
//-----------------------------------------------
case '4':
if (Full(&D)) cout<<endl<<"Дек пуст\n\n";
else
{
DeleteR(&D);
cout<<endl<<"Элемент удален\n\n";
} break;
//-----------------------------------------------
case '5':
if (Full(&D)) cout<<endl<<"Дек пуст\n\n";
else cout<<"\nПервый элемент: "<<OutputL(&D)<<"\n\n";
break;
//-----------------------------------------------
case '6':
if (Full(&D)) cout<<endl<<"Дек пуст\n\n";
else cout<<"\nПоследний элемент: "<<OutputR(&D)<<"\n\n";
break;
//-----------------------------------------------
case '7':
if (Full(&D)) cout<<endl<<"Дек пуст\n\n";
else cout<<"\nРазмер дека: "<<Size(&D)<<"\n\n";
break;
//-----------------------------------------------
case '0': break;
default: cout<<endl<<"Команда не определена\n\n";
break;
}
} while(number!='0');
system("pause");
}

 

Двусторонняя очередь, реализованная таким способом, имеет два существенных недостатка: ограниченный размер и линейное время. Последнее касается добавления элемента в начало или извлечения его оттуда, а именно операциям AddL и DeleteL необходимо N перестановок, где N – число элементов в деке.

Стандартная библиотека C++ предоставляет специальные средства работы с двусторонней очередью. Для этого в ней предусмотрен контейнер deque. Он позволяет за O(1) осуществлять вставку и удаление элементов. Методы контейнера deque:

  • front – возврат значения первого элемента;
  • back – возврат значения последнего элемента;
  • push_front – добавление элемента в начало;
  • push_back – добавление элемента в конец;
  • pop_front – удаление первого элемента;
  • pop_back – удаление последнего элемента;
  • size – возврат числа элементов дека;
  • clear – очистка дека.

Следующая программа полностью повторяет функционал предыдущей, но для обработки дека она использует не пользовательские подпрограммы, а методы контейнера deque.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include "stdafx.h"
#include <iostream>
#include <deque>
using namespace std;
int main() //главная функция
{
setlocale(LC_ALL,"Rus");
deque<int> D; //создание дека D размером 5
deque<int>::iterator out;
int value;
char number;
do
{
cout<<"1. Добавить элемент в начало"<<endl;
cout<<"2. Добавить элемент в конец"<<endl;
cout<<"3. Удалить первый элемент"<<endl;
cout<<"4. Удалить последний элемент"<<endl;
cout<<"5. Вывести первый элемент"<<endl;
cout<<"6. Вывести последний элемент"<<endl;
cout<<"7. Узнать размер дека"<<endl;
cout<<"0. Выйти\n\n";
cout<<"Номер команды > "; cin>>number;
switch (number)
{
case '1':
cout<<"\nЗначение > "; cin>>value;
D.push_front(value);
cout<<endl<<"Элемент добавлен\n\n";
break;
//-----------------------------------------------
case '2':
cout<<"\nЗначение > "; cin>>value;
D.push_back(value);
cout<<endl<<"Элемент добавлен\n\n";
break;
//-----------------------------------------------
case '3': if (D.empty()) cout<<"\nДек пуст\n\n";
else
{
D.erase(D.begin());
cout<<endl<<"Элемент удален\n\n";
} break;
//-----------------------------------------------
case '4': if (D.empty()) cout<<"\nДек пуст\n\n";
else
{
D.erase(D.end()-1);
cout<<endl<<"Элемент удален\n\n";
} break;
//-----------------------------------------------
case '5':
if (D.empty()) cout<<endl<<"Дек пуст\n\n";
else
{
out=D.begin();
cout<<"\nПервый элемент: "<<*out<<"\n\n";
} break;
//-----------------------------------------------
case '6': if (D.empty()) cout<<"\nДек пуст\n\n";
else
{
out=D.end()-1;
cout<<"\nПоследний элемент: "<<*out<<"\n\n";
} break;
//-----------------------------------------------
case '7':
if (D.empty()) cout<<endl<<"Дек пуст\n\n";
else cout<<"\nРазмер дека: "<<D.size()<<"\n\n";
break;
//-----------------------------------------------
case '0': break;
default: cout<<endl<<"Команда не определена\n\n";
break;
}
} while(number!='0');
system("pause");
}

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Вы можете использовать эти теги HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Проверка на человечность *