39
правок
Изменения
Дек
,Нет описания правки
'''boolean''' empty():
'''return''' d.head%n+1 == d.tail
'''function''' pushBack(x : '''T'''):
'''if''' (d.head == d.tail)
'''return''' error "overflow"
'''T''' popBack():
'''if''' (d.head == d.tail)
'''return''' error "overflow"
'''T''' popFront():
Все операции выполняются за <tex>O(1)</tex>.
=== На саморасширяющемся массиве ===
Ключевые поля:* <tex>\mathtt{s[1\dots n]}</tex> {{---}} массив, в котором хранится дек,* <tex>\mathtt{newDeque[1\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования,* <tex>\mathtt{d.head}</tex> {{---}} индекс головы дека,* <tex>\mathtt{d.tail}</tex> {{---}} индекс хвоста дека,* <tex>\mathtt{capacity}</tex> {{---}} размер массива. Если реализовывать дек на динамическом массиве, то мы можем избежать ошибки переполнения. При выполнении операций <tex>pushBack</tex> и <tex>pushFront</tex> происходит проверка на переполнение и, если нужно, выделяется большее количество памяти под массив. Также проверяем, не нужно ли нам уменьшить размер массива при выполнении операций <tex>popBack</tex> и <tex>popFront</tex>. Для удобства выделим в отдельную функцию <tex>size</tex> получение размера дека. '''int''' size() '''if''' d.tail > d.head '''return''' n - d.tail + d.head - 1 '''else''' '''return''' d.head - d.tail - 1 '''function''' pushBack(x : '''T'''): '''if''' (d.head == d.tail) '''T''' newDeque[capacity * 2] '''for''' i = 1 '''to''' capacity - 1 newDeque[i] = d[d.tail + 1] d.tail = d.tail % n + 1 d = newDeque d.tail = capacity * 2 d.head = capacity - 1 capacity = capacity * 2 d[d.tail] = x d.tail = (d.tail - 2 + n) % n + 1 '''T''' popBack(): '''if''' (empty()) '''return''' error "underflow" '''if''' (size() < capacity / 4) '''T''' newDeque[capacity / 2] '''for''' i = 1 '''to''' size() newDeque[i] = d[d.tail + 1] d.tail = d.tail % n + 1 d = newDeque d.tail = capacity / 2 d.head = size() + 1 d.tail = d.tail % n + 1 '''return''' d[d.tail] '''function''' pushFront(x : '''T'''): '''if''' (d.head == d.tail) '''T''' newDeque[capacity * 2] '''for''' i = 1 '''to''' capacity - 1 newDeque[i] = d[d.tail + 1] d.tail = d.tail % n + 1 d = newDeque d.tail = capacity * 2 d.head = capacity - 1 d[d.head] = x d.head = d.head % n + 1 '''T''' popFront(): '''if''' (empty()) '''return''' error "underflow" '''if''' (size() < capacity / 4) '''T''' newDeque[capacity / 2] '''for''' i = 1 '''to''' size() newDeque[i] = d[d.tail + 1] d.tail = d.tail % n + 1 d = newDeque d.tail = capacity / 2 d.head = size() + 1 d.head = (d.head - 2 + n) % n + 1 '''return''' d[d.head]
=== На списке ===
Ключевые поля:
