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]; } void 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 } |
Представим стек, как динамическую цепочку звеньев, т.е. свЯзный список. Первое звено - вершина. Так как доступна только вершина, то в таком списке главное звено становится излишним. Стек как единый объект представляет указатель, значение его - адрес вершины стека. Каждое звено цепочки содержит указатель на следующее звено, "дно" стека - элемент, занесенный первым, имеет этот указатель равным 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; } |
![]() |