Выбор структуры
Размер
0
Ёмкость
10
Верх / голова
—
Хвост
—
Визуализация
Структура пуста.
Журнал операций
Журнал пуст.
Ключевой код: стек и очередь на массиве
Стек на массиве
const int MAXSIZE = 100;
struct Stack {
int data[MAXSIZE];
int size; // количество элементов
};
void Push(Stack &S, int x) {
if (S.size == MAXSIZE) {
cout << "Стек переполнен" << endl;
return;
}
S.data[S.size] = x; // кладём наверх
S.size++;
}
int Pop(Stack &S) {
if (S.size == 0) {
cout << "Стек пуст" << endl;
return -1; // признак ошибки
}
S.size--;
return S.data[S.size]; // снимаем с верхушки
}
Очередь-кольцо на массиве
struct Queue {
int data[MAXSIZE];
int size, head, tail; // head — начало, tail — конец
};
void PushTail(Queue &Q, int x) {
if (Q.size == MAXSIZE) {
cout << "Очередь переполнена" << endl;
return;
}
Q.tail++;
if (Q.tail >= MAXSIZE) Q.tail = 0; // замыкание в кольцо
Q.data[Q.tail] = x;
Q.size++;
}
int Pop(Queue &Q) {
if (Q.size == 0) {
cout << "Очередь пуста" << endl;
return -1;
}
int temp = Q.data[Q.head];
Q.head++;
if (Q.head >= MAXSIZE) Q.head = 0;
Q.size--;
return temp;
}
Различие на пальцах. Стек похож на стопку тарелок: положили сверху,
сняли сверху же. Очередь — как очередь в магазине: кто первый встал, тот первый
и уходит. Обе структуры отличаются только тем, с какого конца мы удаляем элементы.
Задание
- Запустите обе структуры, добавив по 4 элемента. Сравните, какой элемент выходит первым при Pop/Dequeue.
- Нажмите Pop, когда структура пуста. Как ведёт себя программа?
- Доведите стек до переполнения (10 элементов). Что произойдёт при 11-м Push?
- Реализуйте стек на двусвязном списке — что меняется, если нет ограничения MAXSIZE?
- Какой структурой смоделировать историю браузера (кнопка «назад»)? А какой — печать документов в очереди?