39
правок
Изменения
Дек
,Нет описания правки
* <tex>\mathtt{d.tail}</tex> {{---}} индекс хвоста дека.
Дек состоит из элементов <tex>\mathtt {d[d.tail\dots d.head]}</tex>. Если очень много раз добавлять в начало и столько же раз удалять конечные элементы, то скоро мы дойдем до границы, имея немного элементов, при этом добавление в начало вызовет переполнение (в данной реализации во внимание Всего дек способен вместить не берется). Если в деке верно равенство более <tex>\mathtt{d.tail = d.head}n</tex>элементов, то такой дек пуст поэтому при переполнении приходится перевыделять память и изъятие из него может привести к ошибкекопировать все элементы.
'''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]
Все операции выполняются за <tex>O(1)</tex>.
