2. Стеки
Стек – разновидность очереди (а значит и разновидность списка), но с другим правилом доступа – L I F O (Last In and First Out – последним пришел и первым ушел). Ещё один термин (редко используемый) для обозначения этой структуры данных – магазин.
В стеке доступна единственная позиция – та, в которой находится последний введённый элемент – вершина. Иногда позицию, от которой стек начал заполняться данными, называют дном стека (хотя особого применения этот термин не имеет, поскольку дно стека, в котором содержится хотя бы один элемент данных, недоступно. Одно из немногих рациональных применений термина "дно" – признак пустого стека, когда дно и вершина совпадают).
Для стека, как и для очереди, характерны две операции – сохранение и извлечение, но применяются они к одной и той же позиции. Операция извлечения удаляет элемент из списка и уничтожает его содержимое. Произвольный доступ к элементам стека не допускается.
Области применения стеков такие же, как и у очередей:
Системные –
Прикладные –
Примеры стеков. Второе название стека – магазин, – приводит к механическому примеру стека – магазин стрелкового оружия. Ещё один простой пример – стакан.
Стеки, также как и очереди, могут реализовываться при помощи одномерных массивов или свЯзных списков.
Ниже приведёны примеры процедур занесения и извлечения данных для стека на основе массива на языках Паскаль и Си++.
Программа работы со стеком на языке Паскальconst
slen, pos: integer; procedure push(i:char); begin
begin
pos := pos + 1 else
function pop():char; begin
begin
pop := 0 else begin
pop := stack[pos] Pos - индекс следующей открытой позиции – вершины стека. Если Pos больше индекса последнего сохранения, значит стек заполнен; если Pos = 0 – стек пуст.
#include <iostream> using namespace std; const int N = 30; char stack[N]; int pos = 0,slen = N; // Занесение элемента в стек. void Push(char i) { if (pos == slen) { cout<<"Стек полон!\n"; return; } stack[pos] = i; pos++; } // Извлечение элемента из стека. char Pop() { if (pos == 0) { cout<<"Стек пуст.\n"; return 0; } pos--; return stack[pos]; } int main() Содержимое { Push('A'); A Push('B'); B A Push('C'); C B A cout>>Pop()>>endl; // Возвр. C B A Push('F'); F B A cout>>Pop()>>'\n'; // Возвр. F B A cout>>Pop()>>endl; // Возвр. B A return 0; } |
Представим стек, как динамическую цепочку звеньев, т.е. свЯзный список. Первое звено – вершина. Так как доступна только вершина, то в таком списке главное звено становится излишним. Стек как единый объект представляет указатель, значение его – адрес вершины стека. Каждое звено цепочки содержит указатель на следующее звено, "дно" стека – элемент, занесенный первым, имеет этот указатель равным nil.
Программа работы с динамическим стеком на языке ПаскальСтек, как структура данных, задается набором типов. type (* Секция описания типов *)
next = ^elem; elem=record (* Запись *)
data: stype stack = next;
var
q^.data := newl; (* новое звено *) q^.dr := st; st := q; (* новое звено - вершина *) Наличие у процедуры аргумента push(var st: stack, ... ) позволяет работать с несколькими стеками. function pop(var st: stack):stype; var
begin
q := st; st := st^.dr; dispose(q) var P: stack; Если стек пуст, то значение указателя P равно nil. К началу использования стека его нужно сделать пустым при помощи оператора p := nil; begin p := nil; push(p,43); writeln(pop(p):3:9); push(p,54); writeln(pop(p):3:9); readln; end. typedef float stype; /* Необязательное переименование типа float (может использоваться любой тип) в имя stype */ struct elem { elem* dr; // указатель на другой такой же элемент stype data; // хранимые в стеке данные }; void Push(elem*& st, stype newel) { elem* q = new elem; q->data = newel; // Новое звено q->dr = st; st = q; // Новое звено становится вершиной стека. } stype Pop(elem*& st) { stype a; elem *q; if (st == NULL) { cout<<"Стек пуст.\n"; return; } a = st->data; q = st; st = st->dr; delete q; return a; } |
Контрольные вопросы
1. Что представляет собой стек?
2. На основе каких структур данных могут организовываться стеки?
3. Чем отличается стек на основе массива от стека на основе связного списка?
4. Чем отличается стек на основе связного списка от собственно связного списка?
5. К каким структурам данных относятся очереди и стеки?
6. Перечислите основные отличия стека от очереди.
7. Какой метод доступа используется при доступе к элементам стека? В чем его особенности?
8. Перечислите основные операции, применяемые при работе со стеками. К каким позициям в стеке они могут применяться?
9. Какой характер имеет операция считывания для стеков?
10. Перечислите задачи, для решения которых применяются стеки.
11. Изобразите структуру звена динамического стека.
12. Как определить наличие или отсутствие элементов в стеке?
13. Как определить количество элементов в стеке?