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