Списки стеки очереди в C (стр. 2 из 5)
Однонаправлений і двонаправлений список – це лінійний список, у якому всі видалення й вставки відбуваються в будь-якому місці списку.
Однонаправлений список відрізняється від двонаправленного списку тільки зв'язком. Тобто в односпрямованому списку можна переміщатися тільки в одному напрямку (з початку в кінець), а двонаправленому - у кожному. З малюнка це видно: зверху однонаправлений список, а знизу двонаправлений.
На малюнку нижче видно як додається й видаляється елемент із двонаправленого списку. При додаванні нового елемента (позначений N) між елементами 2 і 3. Зв'язок від 3 іде до N, а від N до 4, а зв'язок між 3 і 4 видаляється.
В односпрямованому списку структура додавання й видалення така ж тільки зв'язок між елементами однобічна.
1.2 Стеки
Стек (stack) — лінійний список, у якому всі видалення й доповнення (і звичайно всякий доступ) робляться з одного кінця списку.
Стек — частина пам'яті ОЗУ комп'ютера, що призначається для тимчасового зберігання байтів, використовуваних мікропроцесором; при цьому використається порядок запам'ятовування байтів “останнім увійшов – першим вийшов”, оскільки таке добавлення й видалення організовувати простіше всього, то операції здійснюються дуже швидко. Дії зі стеком виконуються за допомогою регістра покажчика стека. Будь-яке ушкодження цієї частини пам'яті приводить до фатального збою.
Стек у вигляді списку (pushdown list) – стек, організований таким чином, що останній елемент, що вводить в область пам'яті, розміщується на вершині списку.
З стека ми завжди виключаємо "молодший" елемент із наявних у списку, тобто той, котрий був включений пізніше інших. Для черги справедливо в точності протилежне правило: видаляється завжди "старший" елемент; вузли залишають список у тім порядку, у якому вони в нього ввійшли.
Стеки дуже часто зустрічаються в практиці. Простим прикладом може послуговувати ситуація, коли ми переглядаємо безліч даних і утворюємо список особливих станів або об'єктів, які повинні оброблятися пізніше; коли первісна безліч оброблена, ми повертаємося до даного списку й виконуємо наступну обробку, видаляючи елементи зі списку, поки список не стане порожнім. Для цієї мети придатні як стек, так і черга, але стек, як правило, зручніший. При вирішенні завдань наш мозок поводиться як "стек": одна проблема приводить до іншої, а та у свою чергу до наступної; ми накопичуємо в стеці ці завдання й підзавдання й забуваємо про них у міру того, як вони вирішуються. Аналогічно процес входів у підпрограми й виходів з них при виконанні машинної програми подібний до процесу функціонування стека. Стеки особливо корисні при обробці мов, що мають структуру вкладень. Взагалі, стеки найчастіше виникають у зв'язку з алгоритмами, що мають явно або неявно рекурсивний характер.
У стеці елемент додаються й віддаляються тільки з одного кінця. На малюнку це елемент N. Тобто якщо він додався, то видалятися може спочатку тільки він, а вже потім всі інші.
Для стеку характерні такі властивості:
· елементи додаються у вершину (голову) стеку;
· елементи видаляються з вершини (голови) стеку;
· покажчик в останньому елементі стеку дорівнює NULL;
· неможливо вилучити елементи стеку, не вилучивши всі елементи, що йдуть попереду.
Стек можна уявити собі як коробці, у яку складають які-небудь предмети, щоб дістати самий нижній потрібно попередньо витягти інші. Стек можна вподібнити стопці тарілок, з якої можна взяти верхню й на яку можна покласти нову тарілку. [Інша назва стека в літературі - “магазин” - зрозуміло всякому, хто розбирав автомат Калашникова].
У програмуванні стеки мають широке застосування. Наприклад під час виклику підпрограми адрес повернення до неї зберігається у стеку. У випадку, коли відбувається цілий ряд послідовних викликів, адреси повернення розміщаються в стеці в порядку останнім прийшов - першим вийшов, так що після завершення виконання кожної функції відбувається перехід до функції, її що викликала. Стек підтримує як звичайні нерекурсивні виклики, так і рекурсивний виклик функцій.
Стек використовується компілятором під час обчислення виразів, до нього записуються значення локальних змінних тощо.
1.3 Черги
Черга (queue) — лінійний список, у якому всі видалення відбуваються на одному кінці списку, а всі включення (і звичайно всякий доступ) робляться на іншому його кінці.
Черга — тип даних, при якому нові дані розташовуються слідом за існуючими в порядку надходження; першими дані, що надійшли, при цьому обробляються першими.
У деяких розділах математики слово "чергу" використовують у більше широкому змісті, позначаючи будь-який сорт списку, у якому наявні видалення й додавання; зазначені вище спеціальні випадки називаються тоді "чергами з різними дисциплінами". Однак тут термін "черга" використовується у більш вузькому змісті, аналогічному впорядкованим чергам людей, що очікують обслуговування.
Правило тут таке ж, як у живій черзі: першим прийшов - першим тебе і обслужений. Прийшов новий покупець, встав (добавився) у кінець черги, а який уже зробив покупки пішов (вийшов) з початку черги. Тобто першим прийшов, першим пішов.
Інакше кажучи, у черги є голова (head) і хвіст (tail). Елемент, що додається в чергу, виявляється в її хвості.
У черзі новий елемент додається тільки з одного кінця. Видалення елемента відбувається на іншому кінці. Черга, це по суті однонаправлений список, тільки додавання й видалення елементів відбувається на кінцях списку.
Черга характеризується такими властивостями:
· елементи додаються в кінець черги;
· елементи зчитуються та видаляються з початку (вершини) черги;
· покажчик в останньому елементі черги дорівнює NULL;
· неможливо отримати елемент із середини черги, не вилучивши все елементи що ідуть попереду.
Наведемо приклади застосування черг в обчислювальній техніці. У мережній операційній системі процесор сервера обслуговує в певний момент часу тільки одного користувача. Запити інших користувачів записуються до черги. Під час обслуговування користувачів кожен запит просувається до початку черги. Перший в черзі запит підлягає «першочерговому» обслуговуванню. У комп’ютерній мережі за чергою обслуговуються інформаційні пакети. Черги застосовуються також для буферизації потоків даних, що виводяться на друк, якщо в комп’ютерній мережі використовується один принтер.
Крім цих структур існують і інші, наприклад деки, двонаправленні списки, кільцеві списки і т.і.
На малюнку вище графічно зображено дек (deck) (стек із двома кінцями) — лінійний список, у якому всі додавання й видалення (і звичайно всякий доступ) робляться на обох кінцях списку.
Дек по суті двонаправлений список.
У зв'язаному списку (linked list) елементи лінійно впорядковані, але порядок визначається не номерами, як у масиві, а покажчиками, що входять до складу елементів списку. Списки є зручним способом зберігання динамічних даних, що дозволяють реалізувати всі операції, (хоча й не завжди ефективно).
Інакше кажучи, елемент двостороннє зв'язаного списку (doubly linked list) — це запис, що містить три поля: key (ключ) і два покажчики — next (наступний) і prev (від previous-попередній). Крім цього, елементи списку можуть містити додаткові дані. Якщо х — елемент списку, то next вказує на наступний елемент списку, а prev — на попередній. Якщо prev{х}=nil, то в елемента х немає попереднього: це голова (head) списку. Якщо next{х}= nil, то х — останній елемент списку або, як говорять, його хвіст (tail). Ці дані є неявно загальноприйнятими в програмуванні.
Звичайно, динамічні структури даних не обмежуються наведеними вище. Існують і інші, зокрема графи, дерева що займають свою окрему нішу у програмуванні і почасти вирішення певних питань не можливе без їх застосування.
Розділ ІІ. Практична реалізація динамічних структур на мові програмування С++
2.1 Робота з динамічною пам’яттю
2.1.1 Вказівники
Робота із динамічними структурами у С++ передбачає безпосередню роботу із посиланнями і вказівниками. Розглянемо детально як же їх створювати і які операції можна над ними проводити.
Змінні-вказівники містять в якості своїх значень адреси пам’яті. Зазвичай змінна містить деяке значення. З іншої сторони, вказівники містять адрес змінної, яка містить деяке значення. В цьому смислі ім’я змінної відсилається до значення прямо, а вказівник – побічно. Перехід на значення через вказівник називається побічною адресацією.