Свая (абстрактный тип данных)

В информатике стопка — это абстрактный тип данных , предназначенный для хранения данных в свободно упорядоченном виде. Есть два разных значения этого термина; одно относится к упорядоченной двусторонней очереди , другое — к улучшенной куче .

Заказанная двусторонняя очередь

Первая версия сочетает в себе свойства двусторонней очереди (дека) и приоритетной очереди и может быть описана как упорядоченная двухсторонняя очередь.

Элемент может быть добавлен в начало списка, если значение нового элемента меньше или равно текущему началу списка, или в конец списка, если новый элемент больше или равен текущему хвосту. Элементы можно удалять как с головы, так и с хвоста. ^[1]

Стопки такого типа используются в алгоритме сортировки «UnShuffle sort» .

Улучшенная куча

Вторая версия является предметом патентов. ^[2]^[3] и улучшает структуру данных кучи.

Всю систему, основанную на куче данных, можно обобщить следующим образом:

Ссылки

^ Арт С. Кагель, xlinux.nist.gov ; «куча», в Словаре алгоритмов и структур данных [онлайн], изд. Пола Э. Блэка, Национальный институт стандартов и технологий , оценка от 27 сентября 2007 г.
^ «Структура данных и метод сортировки с использованием кучи-суперузлов» , патент США 728147 (2000 г., выдан в 2005 г.)
^ «Структура данных и метод конвейерной пирамидальной сортировки» , патент США 09727534 (2000 г., выдан в 2006 г.)

[1] Арт С. Кагель, xlinux.nist.gov ; «куча», в Словаре алгоритмов и структур данных [онлайн], изд. Пола Э. Блэка, Национальный институт стандартов и технологий , оценка от 27 сентября 2007 г.

[2] «Структура данных и метод сортировки с использованием кучи-суперузлов» , патент США 728147 (2000 г., выдан в 2005 г.)

[3] «Структура данных и метод конвейерной пирамидальной сортировки» , патент США 09727534 (2000 г., выдан в 2006 г.)

[1]

[2]

[3]