Стек - динамічна структура даних, в якій додавання і видалення елементів є тільки з одного кінця (з верхнього (останнього) елемента).
Існують такі скорочення:
Послідовні етапи засилання в стек чисел 1, 2, 3
Над стеком виконуються наступні операції:
- додавання в стек нового елемента;
- визначення порожній чи стек;
- доступ до останнього включеному елементу, вершині стека;
- виключення з стека останнього включеного елемента.
Створення структури вузла:
Додавання елемента в стек:
procedure Push (var Head: PNode; x: char); var NewNode: PNode; begin New (NewNode); <выделение памяти> NewNode ^ .data: = x; <запись символа> NewNode ^ .next: = Head; <сделать первым узлом> Head: = NewNode; end;
Забір елемента з вершини:
Розглянемо детальну роботу зі стеком на прикладі:
Приклад: вводиться символьний рядок, в якій записані теги в кутових дужках (<>). Визначити, чи правильно розставлені дужки (не звертаючи уваги на інші символи).
Алгоритм виконання завдання:
- спочатку стек порожній;
- в циклі переглядаємо кожен символ рядка;
- якщо поточний символ - відкриває кутова дужка, то вставляємо її на вершину стека;
- якщо поточний символ - закриває кутова дужка, то перевіряємо верхній елемент стека: там повинна знаходитися відкриває кутова дужка (інакше - помилка);
- в кінці стек повинен стати порожнім, інакше - помилка.
Створюємо структуру стека:
const MAXSIZE = 50; type Stack = record <стек рассчитан на 50 символов> tags: array [1..MAXSIZE] of char; size: integer; <число элементов> end;
Черга - динамічна структура даних, у якій в кожен момент часу доступні тільки два елементи: перший і останній. Додавання елементів можливо тільки з одного кінця (кінця черги), а видалення елементів - тільки з іншого кінця (початку черги).
Існує скорочення для черги: FIFO = F irst I n - F irst O ut, з англійської - «Хто першим увійшов, той першим вийшов».
Для черзі доступні наступні операції:
- додати елемент в кінець черги (PushTail);
- видалити елемент з початку черги (Pop).
Робота з чергою звичайним масивом:
Це досить простий спосіб, який має на увазі два несприятливих моменти: завчасне виділення масиву, зсув елементів при видаленні з черги.
Робота з чергою за допомогою кільцевого масиву:
Якщо в черзі 1 елемент:
Якщо чергу порожня:
Якщо чергу заповнена:
Визначення розміру масиву (при порожній і заповненої черги):
