Списък, стек, опашка, дек.

12.Списък, стек, опашка, дек.

Под списък разбираме крайно множесто от n-еднотипни елемента x1, x2… xN със седните свойства:
1) aкo n == 0, то списъкът е празен
2) ако n > 0, списъкът е непразен, то х1 е първият елемент, х2 – вторият .. xN – последният
3) ако k > 1, то x(k – 1) предшества xk
4) ако k>= 1, k < n - 1, то x(k + 1) следва x(k) (това не е толкова очевидно, колкото изглежда)

В C++ Списъкът е наредена последнователност от краен брой еднотипни елементи. Всеки елемент се състои от полета, като данните в тях може да бъдат от различен тип – числови, текстови.. Със списъците може да се изпълняват следните операции – търсене на елемент по номер и осигуряване достъп до съдържанието му, включване на нов елемент на дадена позиция, изключване на елемент с номер от списъка, обединяване на 2 или повече списъка в един, разбиване на списък на някокло отделни, създаване на копие, определяне броя на елементите на списък, търсене на елемент с определено съдържание(по ключ), сориране. Същестуват различни начини за представяне на списъци в зависимост от вида на операциите над елементите. Основна характеристика на списъка е начинът, по който се осъществява достъпът до елементите му. Ако списъкът използва динамично заделяне на памет, той се нарича динамичен списък(иначе се нарича статичен. Масивите в C са статични списъци). Ако всеки елемент пази указатели към предишния и следващия елемент, нарича се двусвързан списък, иначе - едносвързан. Естествено, има и далеч по-сложни видове списъци.

Стек се нарича списък, при който добавянето на нови елементи, както и изключването, стават само от едната страна на списъка – върха на стека. Мнемоника за запомняне на стек е LIFO (last in, first out). Пример – пълнител на автомат. Пълнителят на автомат е вид стек. Със сигурност най-мъжественият вид стек.

Опашка се нарича списък, при който всички включвания на нови елементи стават само от единия край на списъка( край на опашката ), а изключването на елемент само от другия край на списъка( начало на опашката ). FIFO( first in – first out ). Пример - …опашка …за хляб.

Дек се нарича списък, при който всички включвания и изключвания на елемент може да бъдат извършвани от двата края на списъка. Идва от английското наименование Deque, което пък буквално означава опашка с два края (double-ended queue). Декът е на практика по–рядко използвана структура от данни в сравнение със стека и опашката. В стандартната библиотека на C++ (STL) стековете и опашките са реализирани всъщност чрез използване на дек.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License