Дек — различия между версиями
Mutsch (обсуждение | вклад) |
Mutsch (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Определение == | == Определение == | ||
| − | '''Дек''' (от англ. ''deque'' {{---}} double ended queue ()) {{---}} структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. | + | '''Дек''' (от англ. ''deque'' {{---}} double ended queue ()) {{---}} структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Особой разницы между двумя концами нет, поэтому их можно воспринимать как конец 1 и конец 2. Дек можно воспринимать как двустороннюю очередь или двусторонний стек. Он имеет следующие операции: |
* <tex> \mathtt{empty} </tex> {{---}} проверка на наличие элементов, | * <tex> \mathtt{empty} </tex> {{---}} проверка на наличие элементов, | ||
| − | * <tex> \mathtt{pushBack} </tex> {{---}} операция вставки нового элемента в конец, | + | * <tex> \mathtt{pushBack} </tex> (запись в конец) {{---}} операция вставки нового элемента в конец, |
| − | * <tex> \mathtt{popBack} </tex> {{---}} операция удаления конечного элемента, | + | * <tex> \mathtt{popBack} </tex> (снятие с конца) {{---}} операция удаления конечного элемента, |
| − | * <tex> \mathtt{pushFront} </tex> {{---}} операция вставки нового элемента в начало, | + | * <tex> \mathtt{pushFront} </tex> (запись в начало) {{---}} операция вставки нового элемента в начало, |
| − | * <tex> \mathtt{popFront} </tex> {{---}} операция вставки начального элемента. | + | * <tex> \mathtt{popFront} </tex> (снятие с начала) {{---}} операция вставки начального элемента. |
| − | == | + | ==Реализация на двусвязном списке== |
| + | Дек можно реализовать на двусвязном списке. При этом расходуется только <tex>O(n)</tex> памяти, на хранение самих элементов. | ||
| + | === List === | ||
Версия 12:26, 3 декабря 2015
Определение
Дек (от англ. deque — double ended queue ()) — структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Особой разницы между двумя концами нет, поэтому их можно воспринимать как конец 1 и конец 2. Дек можно воспринимать как двустороннюю очередь или двусторонний стек. Он имеет следующие операции:
- — проверка на наличие элементов,
- (запись в конец) — операция вставки нового элемента в конец,
- (снятие с конца) — операция удаления конечного элемента,
- (запись в начало) — операция вставки нового элемента в начало,
- (снятие с начала) — операция вставки начального элемента.
Реализация на двусвязном списке
Дек можно реализовать на двусвязном списке. При этом расходуется только памяти, на хранение самих элементов.
