Загальна характеристика списків магазинного типу.

Списки магазинного типу

У практиці інформаційного моделювання часто використовуються лінійні списки, в яких включення, виключення або доступ до ланок майже завжди проводиться в першій або останній ланках.

Назвемо списком магазинного типу лінійний список, всі ланки якого вставляються і видаляються тільки з одного або обох кінців списку. Списки магазинного типу підрозділяються на черги, стеки і деки.

Черга - список магазинного типу, в якому всі включення проводяться на одному кінці списку, а всі виключення - на іншому.

Чергу іноді називають циклічною пам'яттю або списком типу FIFO ("First In - First Out" - "першим включається - першим виключається").

У черзі інформація поміщається в кінець черги і віддаляється в мить, коли, нарешті, досягає її початку. Зобразимо це схематично: звідси сюди

Рис.1. Черга

Черги використовуються при моделюванні систем масового обслуговування, диспетчеризація завдань операційною системою, буферизація введення-виведення і ін.

Стек - список магазинного типу, в якому всі включення і виключення ланок робляться в одному кінці списку.

Із стеку завжди виключається "молодший" елемент з наявних в списку (той елемент, який був включений пізніше за інших).

Існують і інші назви стеку: магазин, список типу LIFO ("Last In - First Out" - "останнім включається - першим виключається"); список ("push-down"), реверсивна пам'ять, гніздова пам'ять.

Рис.2. Стек

Стеки широко застосовуються в програмуванні, компіляторах, рекурсивних алгоритмах і т. п.

Дек ("Double-Ended Queue" - "двостороння черга") - список магазинного типу, в якому всі включення і виключення ланок робляться на обох кінцях списку.

Дек обобщает стек и очередь и имеет некоторые общие свойства с колодой игральных карт.

Зауваження. Поняття стек було введено А.М.Тьюрінгом в 1947 р. і названо ним реверсивною пам'яттю (воно використовувалося для зв'язку підпрограм). Термін " дек" був введений Швеппе.

Приклад 12. Структурна программа. Побудова черги.

struct node { int value; node *next; };void POSTROENIE (node **no, node **ko);void VYVOD (node **no, node **ko);-------------------------------------------------------------------------- int main() { SetConsoleCP(1251); SetConsoleOutputCP(1251); node *no, *ko; POSTROENIE (&no, &ko); VYVOD (&no, &ko); return 0;} -------------------------------------------------------------------------- void POSTROENIE(node **no, node **ko) { node *r; int el; cin>>el; if (el!=0) { r = new (node); r->value = el; r->next = NULL; *no = r; *ko = r; cin>> el; while (el!=0) { r = new (node); r->value = el; r->next = NULL; (*ko)->next = r; *ko = r; cin>>el; } } else { r = NULL; *no = r; *ko = r; }} void VYVOD(node **no, node **ko) { node *r; cout<< "Очередь: "; r = *no; while (r!=NULL) { cout<<r->value<<" "; r = r->next; } cout<<endl;}

Приклад 13. Структурна программа. Додавання ланки до черги.

… … … -------------------------------------------------------------------------- void DOBAVLENIE (node **no, node **ko,int el) { node *r; r = new (node); r->value = el; r->next = NULL; if (*no!= NULL) { (*ko)->next = r; *ko = r; } else { *no = r; *ko = r; }}

Приклад 14. Структурна программа. Видалення ланки з черги.

… … … -------------------------------------------------------------------------- void UDALENIE (node **no, node **ko) { node *q; if (*no == NULL) cout<< "Видалити не можна, оскільки черга порожня!\n"; else { q = *no; *no = (*no)->next; delete q; }}

Приклад 15. Об'єктно-орієнтована програма. Побудова і проглядання черги, додавання і видалення ланок з черги.

Дата добавления: 2015-07-21