Курсовая работа: Списки стеки очереди в C

На малюнку нижче видно як додається й видаляється елемент із двонаправленого списку. При додаванні нового елемента (позначений N) між елементами 2 і 3. Зв'язок від 3 іде до N, а від N до 4, а зв'язок між 3 і 4 видаляється.

В односпрямованому списку структура додавання й видалення така ж тільки зв'язок між елементами однобічна.

1.2 Стеки

Стек (stack) — лінійний список, у якому всі видалення й доповнення (і звичайно всякий доступ) робляться з одного кінця списку.

Стек — частина пам'яті ОЗУ комп'ютера, що призначається для тимчасового зберігання байтів, використовуваних мікропроцесором; при цьому використається порядок запам'ятовування байтів “останнім увійшов – першим вийшов”, оскільки таке добавлення й видалення організовувати простіше всього, то операції здійснюються дуже швидко. Дії зі стеком виконуються за допомогою регістра покажчика стека. Будь-яке ушкодження цієї частини пам'яті приводить до фатального збою.

Стек у вигляді списку (pushdown list) – стек, організований таким чином, що останній елемент, що вводить в область пам'яті, розміщується на вершині списку.

З стека ми завжди виключаємо "молодший" елемент із наявних у списку, тобто той, котрий був включений пізніше інших. Для черги справедливо в точності протилежне правило: видаляється завжди "старший" елемент; вузли залишають список у тім порядку, у якому вони в нього ввійшли.

Стеки дуже часто зустрічаються в практиці. Простим прикладом може послуговувати ситуація, коли ми переглядаємо безліч даних і утворюємо список особливих станів або об'єктів, які повинні оброблятися пізніше; коли первісна безліч оброблена, ми повертаємося до даного списку й виконуємо наступну обробку, видаляючи елементи зі списку, поки список не стане порожнім. Для цієї мети придатні як стек, так і черга, але стек, як правило, зручніший. При вирішенні завдань наш мозок поводиться як "стек": одна проблема приводить до іншої, а та у свою чергу до наступної; ми накопичуємо в стеці ці завдання й підзавдання й забуваємо про них у міру того, як вони вирішуються. Аналогічно процес входів у підпрограми й виходів з них при виконанні машинної програми подібний до процесу функціонування стека. Стеки особливо корисні при обробці мов, що мають структуру вкладень. Взагалі, стеки найчастіше виникають у зв'язку з алгоритмами, що мають явно або неявно рекурсивний характер.

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

Для стеку характерні такі властивості:

· елементи додаються у вершину (голову) стеку;

· елементи видаляються з вершини (голови) стеку;

· покажчик в останньому елементі стеку дорівнює NULL;

· неможливо вилучити елементи стеку, не вилучивши всі елементи, що йдуть попереду.

Стек можна уявити собі як коробці, у яку складають які-небудь предмети, щоб дістати самий нижній потрібно попередньо витягти інші. Стек можна вподібнити стопці тарілок, з якої можна взяти верхню й на яку можна покласти нову тарілку. [Інша назва стека в літературі - “магазин” - зрозуміло всякому, хто розбирав автомат Калашникова].

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

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

1.3 Черги

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

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

У деяких розділах математики слово "чергу" використовують у більше широкому змісті, позначаючи будь-який сорт списку, у якому наявні видалення й додавання; зазначені вище спеціальні випадки називаються тоді "чергами з різними дисциплінами". Однак тут термін "черга" використовується у більш вузькому змісті, аналогічному впорядкованим чергам людей, що очікують обслуговування.

Правило тут таке ж, як у живій черзі: першим прийшов - першим тебе і обслужений. Прийшов новий покупець, встав (добавився) у кінець черги, а який уже зробив покупки пішов (вийшов) з початку черги. Тобто першим прийшов, першим пішов.

Інакше кажучи, у черги є голова (head) і хвіст (tail). Елемент, що додається в чергу, виявляється в її хвості.