Как работает дек

Структуры данных

(англ. ) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним. Стек должен поддерживать следующие операции:

push Добавить (положить) в конец стека новый элемент
pop Извлечь из стека последний элемент
back Узнать значение последнего элемента (не удаляя его)
size Узнать количество элементов в стеке
clear Очистить стек (удалить из него все элементы)

Хранить элементы стека мы будем в массиве. Для начала будем считать, что максимальное количество элементов в стеке не может превосходить константы MAX_SIZE , тогда для хранения элементов массива необходимо создать массив размера MAX_SIZE .

Объявим структуру данных типа stack .

const int MAX_SIZE=1000;

struct stack int m_size; // Количество элементов в стеке
int m_elems[MAX_SIZE]; // Массив для хранения элементов

stack(); // Конструктор
~stack(); // Деструктор
void push(int d); // Добавить в стек новый элемент
int pop(); // Удалить из стека последний элемент
// и вернуть его значение
int back(); // Вернуть значение последнего элемента
int size(); // Вернуть количество элементов в стеке
void clear(); // Очистить стек
>;

Объявленная здесь структура данных stack реализует стек целых чисел. Поле структуры m_size хранит количество элементов в стеке в настоящее время, сами элементы хранятся в элементах массива m_elems с индексами 0.. m_size-1 . Элементы, добавленные позже, получают большие номера.

Упражнение A — простой стек

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

push n Добавить в стек число n (значение n задается после команды). Программа должна вывести ok .
pop Удалить из стека последний элемент. Программа должна вывести его значение.
back Программа должна вывести значение последнего элемента, не удаляя его из стека.
size Программа должна вывести количество элементов в стеке.
clear Программа должна очистить стек и вывести ok .
exit Программа должна вывести bye и завершить работу.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды pop_back и back корректны, то есть при их исполнении в стеке содержится хотя бы один элемент.

Пример протокола работы программы

Ввод Вывод

push 2 ok
push 3 ok
push 5 ok
back 5
size 3
pop 5
size 2
push 7 ok
pop 7
clear ok
size 0
exit bye

Упражнение B — стек с обработкой ошибок

Аналогично предыдущему заданию, только снимается ограничение на корректность вызовов методов back и pop . Данные операции должны перед исполнением проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop , при этом стек пуст, то программа должна вместо числового значения вывести строку error .

При этом должна быть реализована двойная защита: вызов методов forward и pop для пустого стека не должен приводить к обращению к несуществующим элементам массива m_elems , а функция main должна выводить сообщение error , при считывании некорректной операции.

Пример протокола работы программы

Ввод Вывод

push 2 ok
back 2
pop 2
size 0
pop error
push 1 ok
size 1
exit bye

Упражнение C — стек без ограничения на размер

Реализуйте стек динамического размера, то есть ограниченный только объемом свободной оперативной памяти. Для этого используйте указатели и динамически распределяемую память. Если для полностью заполненного стека вызывается метод push размер динамического массива, отведенного для хранения стека, должен увеличиваться.

Очередь

Очередью (aнгл. )) называется структура данных, в которой элементы кладутся в конец, а извлекаются из начала. Таким образом, первым из очереди будет извлечен тот элемент, который будет добавлен раньше других.

Элементы очереди будем также хранить в массиве. При этом из очереди удаляется первый элемент, и, чтобы не сдвигать все элементы очереди, будем в отдельном поле m_start хранить индекс элемента массива, с которого начинается очередь. При удалении элементов, очередь будет «ползти» дальше от начала массива. Чтобы при этом не происходил выход за границы массива, замкнем массив в кольцо: будем считать, что за последним элементом массива следует первый.

Описание структуры очередь:

const int MAX_SIZE=1000;

struct queue int m_size; // Количество элементов в очереди
int m_start; // Номер элемента, с которого начинается очередь
int m_elems[MAX_SIZE]; // Массив для хранения элементов

queue(); // Конструктор
~queue(); // Деструктор
void push(int d); // Добавить в очередь новый элемент
int pop(); // Удалить из очереди первый элемент
// и вернуть его значение
int front(); // Вернуть значение первого элемента
int size(); // Вернуть количество элементов в очереди
void clear(); // Очистить очередь
>;

Упражнение D — простая очередь

Реализуйте простейшую очередь, размер которой не превосходит 100 элементов. Очередь поддерживает те же операции, что и стек, за исключением операции back , которая заменена операцией front . Операции front и pop всегда корректны.

Упражнение E — очередь с обработкой ошибок

Аналогично заданию B, но для очереди. Операции front и pop могут быть некорректными, в этом случае необходимо вывести error .

Программа должна содержать «двойную защиту» от некорректных операций: как в функции main , так и в самих методах pop и front .

Упражнение F — очередь без ограничений на размер

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

Дек

Деком (англ. – аббревиатура от double-ended queue , двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека:

push_front Добавить (положить) в начало дека новый элемент
push_back Добавить (положить) в конец дека новый элемент
pop_front Извлечь из дека первый элемент
pop_back Извлечь из дека последний элемент
front Узнать значение первого элемента (не удаляя его)
back Узнать значение последнего элемента (не удаляя его)
size Узнать количество элементов в деке
clear Очистить дек (удалить из него все элементы)

Упражнение G — простой дек

Аналогично заданиям A и D, но для дека. Количество элементов в деке в любой момент не превосходит 100. Все операции pop_front , pop_back , front , back всегда корректны.

Упражнение H — дек с обработкой ошибок

Аналогично заданиям B и E, но для дека. Количество элементов в деке в любой момент не превосходит 100. При выполнении некорректных операций необходимо вывести error .

Упражнение I — дек неограниченного размера

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

Как работает дек

Дек (deque) представляет двустороннюю очередь, в которой элементы можно добавлять как в начало, так и в конец. Удаление также может идти как с начала, так и с конца.

Поскольку реализовать добавление и удаление нужно с двух сторон, то за основу реализации можно взять организацию двусвязного список. Так, каждый элемент в деке будет представлен следующим классом:

public class DoublyNode  < public DoublyNode(T data) < Data = data; >public T Data < get; set; >public DoublyNode Previous < get; set; >public DoublyNode Next < get; set; >>

Класс дека будет следующим:

using System; using System.Collections; using System.Collections.Generic; namespace SimpleAlgorithmsApp < public class Deque: IEnumerable // двусвязный список < DoublyNodehead; // головной/первый элемент DoublyNode tail; // последний/хвостовой элемент int count; // количество элементов в списке // добавление элемента public void AddLast(T data) < DoublyNodenode = new DoublyNode(data); if (head == null) head = node; else < tail.Next = node; node.Previous = tail; >tail = node; count++; > public void AddFirst(T data) < DoublyNodenode = new DoublyNode(data); DoublyNode temp = head; node.Next = temp; head = node; if (count == 0) tail = head; else temp.Previous = node; count++; > public T RemoveFirst() < if (count == 0) throw new InvalidOperationException(); T output = head.Data; if(count==1) < head = tail = null; >else < head = head.Next; head.Previous = null; >count--; return output; > public T RemoveLast() < if (count == 0) throw new InvalidOperationException(); T output = tail.Data; if (count == 1) < head = tail = null; >else < tail = tail.Previous; tail.Next = null; >count--; return output; > public T First < get < if (IsEmpty) throw new InvalidOperationException(); return head.Data; >> public T Last < get < if (IsEmpty) throw new InvalidOperationException(); return tail.Data; >> public int Count < get < return count; >> public bool IsEmpty < get < return count == 0; >> public void Clear() < head = null; tail = null; count = 0; >public bool Contains(T data) < DoublyNodecurrent = head; while (current != null) < if (current.Data.Equals(data)) return true; current = current.Next; >return false; > IEnumerator IEnumerable.GetEnumerator() < return ((IEnumerable)this).GetEnumerator(); >IEnumerator IEnumerable.GetEnumerator() < DoublyNodecurrent = head; while (current != null) < yield return current.Data; current = current.Next; >> > >

В отличие от класса очереди здесь определены два метода для добавления и два для удаления.

Для добавления в начало очереди переустанавливаем ссылку на переменную head:

public void AddFirst(T data) < DoublyNodenode = new DoublyNode(data); DoublyNode temp = head; node.Next = temp; head = node; if (count == 0) tail = head; else temp.Previous = node; count++; >

Добавление элемента в конец дека вызывает аналогичную переустановку переменной tail:

public void AddLast(T data) < DoublyNodenode = new DoublyNode(data); if (head == null) head = node; else < tail.Next = node; node.Previous = tail; >tail = node; count++; >

При удалении из начала дека надо переустановить ссылку на первый элемент:

public T RemoveFirst() < if (count == 0) throw new InvalidOperationException(); T output = head.Data; if(count==1) < head = tail = null; >else < head = head.Next; head.Previous = null; >count--; return output; >

При удалении последнего элемента переустанавливается переменная tail на предпоследний элемент:

public T RemoveLast() < if (count == 0) throw new InvalidOperationException(); T output = tail.Data; if (count == 1) < head = tail = null; >else < tail = tail.Previous; tail.Next = null; >count--; return output; >

Сложность алгоритмов всех методов добавления и удаления из дека составляет O(1) .

Deque usersDeck = new Deque(); usersDeck.AddFirst("Alice"); usersDeck.AddLast("Kate"); usersDeck.AddLast("Tom"); foreach(string s in usersDeck) Console.WriteLine(s); string removedItem = usersDeck.RemoveFirst(); Console.WriteLine("\n Удален: \n", removedItem); foreach (string s in usersDeck) Console.WriteLine(s);

Alice Kate Tom Удален: Alice Kate Tom

Как работает дек

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

• [math] \mathtt [/math] — проверка на наличие элементов,
• [math] \mathtt [/math] (запись в конец) — операция вставки нового элемента в конец,
• [math] \mathtt [/math] (снятие с конца) — операция удаления конечного элемента,
• [math] \mathtt [/math] (запись в начало) — операция вставки нового элемента в начало,
• [math] \mathtt [/math] (снятие с начала) — операция удаления начального элемента.

Реализации

Дек расходует только [math]O(n)[/math] памяти, на хранение самих элементов.

Простая реализация

В данной реализации изначально [math] \mathtt [/math] и [math] \mathtt [/math] . Ключевые поля:

• [math]\mathtt[/math] — массив, с помощью которого реализуется дек, способный вместить не более [math]n[/math] элементов,
• [math]\mathtt[/math] — индекс головы дека,
• [math]\mathtt[/math] — индекс хвоста.

Дек состоит из элементов [math]\mathtt [/math] . Если происходит максимум [math]\mathtt [/math] добавлений, то массив длины [math]\mathtt [/math] может вместить в себя все добавленные элементы.

boolean empty(): return head == tail

function pushBack(x : T): d[tail++] = x

T popBack(): if (empty()) return error "underflow" return d[--tail]

function pushFront(x : T): d[--head] = x

T popFront(): if (empty()) return error "underflow" return d[head++]

Циклический дек на массиве константной длины

Во всех циклических реализациях изначально присвоены следующие значения [math] \mathtt [/math] и [math] \mathtt [/math] . Ключевые поля:

• [math]\mathtt[/math] — массив, с помощью которого реализуется дек, способный вместить не более [math]n[/math] элементов,
• [math]\mathtt[/math] — индекс головы дека,
• [math]\mathtt[/math] — индекс хвоста.

Дек состоит из элементов [math]\mathtt [/math] или [math]\mathtt [/math] и [math]\mathtt [/math] . Всего он способен вместить не более [math]n[/math] элементов. В данной реализации учитывается переполнение и правильно обрабатывается изъятие из пустого дека. Недостатком является константная длина массива, хранящего элементы. Все операции выполняются за [math]O(1)[/math] .

function pushBack(x : T): if (head == (tail + 1) % n) return error "overflow" d[tail] = x tail = (tail + 1) % n

T popBack(): if (empty()) return error "underflow" tail = (tail - 1 + n) % n return d[tail]

function pushFront(x : T): if (head == (tail + 1) % n) return error "overflow" head = (head - 1 + n) % n d[head] = x

T popFront(): if (empty()) return error "underflow" T ret = d[head] head = (head + 1) % n return ret

Циклический дек на динамическом массиве

• [math]\mathtt[/math] — размер массива,
• [math]\mathtt[/math] — массив, в котором хранится дек,
• [math]\mathtt[/math] — временный массив, где хранятся элементы после перекопирования,
• [math]\mathtt[/math] — индекс головы дека,
• [math]\mathtt[/math] — индекс хвоста.

Дек состоит из элементов [math]\mathtt [/math] или [math]\mathtt [/math] и [math]\mathtt [/math] . Если реализовывать дек на динамическом массиве, то мы можем избежать ошибки переполнения. При выполнении операций [math]\mathtt[/math] и [math]\mathtt[/math] происходит проверка на переполнение и, если нужно, выделяется большее количество памяти под массив. Также происходит проверка на избыточность памяти, выделенной под дек при выполнении операций [math]\mathtt[/math] и [math]\mathtt[/math] . Если памяти под дек выделено в четыре раза больше размера дека, то массив сокращается в два раза. Для удобства выделим в отдельную функцию [math]\mathtt[/math] получение текущего размера дека.

int size() if tail > head return n - head + tail else return tail - head

function pushBack(x : T): if (head == (tail + 1) % n) T newDeque[n * 2] for i = 0 to n - 2 newDeque[i] = d[head] head = (head + 1) % n d = newDeque head = 0 tail = n - 1 n *= 2 d[tail] = x tail = (tail + 1) % n

T popBack(): if (empty()) return error "underflow" if (size() < n / 4) T newDeque[n / 2] int dequeSize = size() for i = 0 to dequeSize - 1 newDeque[i] = d[head] head = (head + 1) % n d = newDeque head = 0 tail = dequeSize n /= 2 tail = (tail - 1 + n) % n return d[tail]

function pushFront(x : T): if (head == (tail + 1) % n) T newDeque[n * 2] for i = 0 to n - 2 newDeque[i] = d[head] head = (head + 1) % n d = newDeque head = 0 tail = n - 1 n *= 2 head = (head - 1 + n) % n d[head] = x

T popFront(): if (empty()) return error "underflow" if (size() < n / 4) T newDeque[n / 2] int dequeSize = size() for i = 0 to dequeSize - 1 newDeque[i] = d[head] head = (head + 1) % n d = newDeque head = 0 tail = dequeSize n /= 2 T ret = d[head] head = (head + 1) % n return ret

На списке

• ListItem(data : T, next : ListItem, prev : ListItem) — конструктор,
• [math]\mathtt[/math] — ссылка на хвост,
• [math]\mathtt[/math] — ссылка на голову.

Дек очень просто реализуется на двусвязном списке. Он состоит из элементов [math]\mathtt [/math] . Элементы всегда добавляются либо в [math]\mathtt[/math] , либо в [math]\mathtt[/math] . В данной реализации не учитывается изъятие из пустого дека.

function initialize(): head = ListItem(null, null, null) tail = ListItem(null, null, head) head.next = tail

function pushBack(x : T): head = ListItem(x, head, null) head.next.prev = head

T popBack(): data = head.data head = head.next return data

function pushFront(x : T): tail = ListItem(x, null, tail) tail.prev.next = tail

T popFront(): data = tail.data tail = tail.prev return data

На двух стеках

• [math]\mathtt[/math] — ссылка на хвост,
• [math]\mathtt[/math] — ссылка на голову.

Храним два стека — [math]\mathtt[/math] и [math]\mathtt[/math] . Левый стек используем для операций [math]\mathtt[/math] и [math]\mathtt[/math] , правый — для [math]\mathtt[/math] и [math]\mathtt[/math] . Если мы хотим работать с левым стеком и при этом он оказывается пустым, то достаем нижнюю половину элементов из правого и кладем в левый, воспользовавшись при этом локальным стеком. Аналогично с правым стеком. Худшее время работы — [math]O(n)[/math] .

function pushBack(x : T): leftStack.push(x)

T popBack(): if not leftStack.empty() return leftStack.pop() else int size = rightStack.size() Stack local for i = 0 to size / 2 local.push(rightStack.pop()) while not rightStack.empty() leftStack.push(rightStack.pop()) while not local.empty() rightStack.push(local.pop()) return leftStack.pop()

function pushFront(x : T): rightStack.push(x)

T popFront(): if not rightStack.empty() return rightStack.pop() else int size = leftStack.size() Stack local for i = 0 to size / 2 local.push(leftStack.pop()) while not leftStack.empty() rightStack.push(leftStack.pop()) while not local.empty() leftStack.push(local.pop()) return rightStack.pop()