Дек — различия между версиями
Mutsch (обсуждение | вклад) |
Mutsch (обсуждение | вклад) м |
||
| Строка 19: | Строка 19: | ||
перевыделять память и копировать все элементы. | перевыделять память и копировать все элементы. | ||
| − | '''boolean''' empty(): | + | '''boolean''' empty(): |
'''return''' d.head%n+1 == d.tail | '''return''' d.head%n+1 == d.tail | ||
| − | '''function''' pushBack(x : '''T'''): | + | '''function''' pushBack(x : '''T'''): |
'''if''' (d.head == d.tail) | '''if''' (d.head == d.tail) | ||
'''return''' error "overflow" | '''return''' error "overflow" | ||
| Строка 28: | Строка 28: | ||
d.tail = (d.tail - 2 + n) % n + 1 | d.tail = (d.tail - 2 + n) % n + 1 | ||
| − | '''T''' popBack(): | + | '''T''' popBack(): |
'''if''' (empty()) | '''if''' (empty()) | ||
'''return''' error "underflow" | '''return''' error "underflow" | ||
| Строка 34: | Строка 34: | ||
'''return''' d[d.tail] | '''return''' d[d.tail] | ||
| − | '''function''' pushFront(x : '''T'''): | + | '''function''' pushFront(x : '''T'''): |
'''if''' (d.head == d.tail) | '''if''' (d.head == d.tail) | ||
'''return''' error "overflow" | '''return''' error "overflow" | ||
| Строка 40: | Строка 40: | ||
d.head = d.head % n + 1 | d.head = d.head % n + 1 | ||
| − | '''T''' popFront(): | + | '''T''' popFront(): |
'''if''' (empty()) | '''if''' (empty()) | ||
'''return''' error "underflow" | '''return''' error "underflow" | ||
Версия 15:54, 4 января 2016
Содержание
Определение
Дек (от англ. deque — double ended queue) — структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Дек можно воспринимать как двустороннюю очередь или двусторонний стек. Он имеет следующие операции:
- — проверка на наличие элементов,
- (запись в конец) — операция вставки нового элемента в конец,
- (снятие с конца) — операция удаления конечного элемента,
- (запись в начало) — операция вставки нового элемента в начало,
- (снятие с начала) — операция удаления начального элемента.
Реализации
Дек расходует только памяти, на хранение самих элементов.
На массиве
Ключевые поля:
- — массив, с помощью которого реализуется дек, способный вместить не более элементов,
- — индекс головы дека,
- — индекс хвоста дека.
Дек состоит из элементов . Всего дек способен вместить не более элементов, поэтому при переполнении приходится перевыделять память и копировать все элементы.
boolean empty(): return d.head%n+1 == d.tail
function pushBack(x : T):
if (d.head == d.tail)
return error "overflow"
d[d.tail] = x
d.tail = (d.tail - 2 + n) % n + 1
T popBack():
if (empty())
return error "underflow"
d.tail = d.tail % n + 1
return d[d.tail]
function pushFront(x : T):
if (d.head == d.tail)
return error "overflow"
d[d.head] = x
d.head = d.head % n + 1
T popFront():
if (empty())
return error "underflow"
d.head = (d.head - 2 + n) % n + 1
return d[d.head]
Все операции выполняются за .
На саморасширяющемся массиве
---
На списке
Ключевые поля:
-
ListItem(data : T, next : ListItem, prev : ListItem)— конструктор, - — ссылка на хвост,
- — ссылка на голову.
Дек очень просто реализуется на списке. Элементы всегда добавляются либо в , либо в .
