2. Стеки


Стек - разновидность очереди (а значит и разновидность списка), но с другим правилом доступа - L I F O (Last In and First Out - последним пришел и первым ушел). Ещё один термин (редко используемый) для обозначения этой структуры данных - магазин.


В стеке доступна единственная позиция - та, в которой находится последний введённый элемент - вершина. Иногда позицию, от которой стек начал заполняться данными, называют дном стека (хотя особого применения этот термин не имеет, поскольку дно стека, в котором содержится хотя бы один элемент данных, недоступно. Одно из немногих рациональных применений термина "дно" - признак пустого стека, когда дно и вершина совпадают).

Для стека, как и для очереди, характерны две операции - сохранение и извлечение, но применяются они к одной и той же позиции. Операция извлечения удаляет элемент из списка и уничтожает его содержимое. Произвольный доступ к элементам стека не допускается.


Области применения стеков такие же, как и у очередей:

Системные -

Прикладные -


Примеры стеков. Второе название стека - магазин, - приводит к механическому примеру стека - магазин стрелкового оружия. Ещё один простой пример - стакан.


Стеки, также как и очереди, могут реализовываться при помощи одномерных массивов или свЯзных списков.


Ниже приведёны примеры процедур занесения и извлечения данных для стека на основе массива на языках Паскаль и Си++.


Программа работы со стеком на языке Паскаль

Programm Stack_Test;
const
    N=30;
var
    stack:array[0..N] of char;
    slen,pos:integer;

procedure push(i:char);
begin
    if pos<slen then
    begin
      stack[pos]:=i;
      pos:=pos+1
    end
    else
      writeln('Стек полон.');
end;

function pop():char;
begin
    if pos=0 then
    begin
      writeln('Стек пуст.');
      pop:=0
    end
    else
    begin
      pos:=pos-1;
      pop:=stack[pos]
    end;
end;

Pos - индекс следующей открытой позиции - вершины стека. Если Pos больше индекса последнего сохранения, значит стек заполнен; если Pos=0 - стек пуст.


begin   Содержимое стека
slen:=N;      
pos:=0;
push('A');A
push('B');B A
push('C');C B A
pop();{Возвращает C}      B A
push('D');D B A
pop();{Возвращает D}B A
pop();{Возвращает B}A
pop();{Возвращает A}Стек пуст
end.

Аналогичная программа на языке Си++

#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.


Программа работы с динамическим стеком на языке Паскаль

Programm Stack_Test;

Стек, как структура данных, задается набором типов.


type      (* Секция описания типов *)
    stype=real;
    next=^elem;
    elem=record      (* Запись *)
      dr:next;
      data:stype
    end;
    stack=next;
var
    p:stack;
procedure push(var st:stack; newl:stype);
var
    q:next;
begin
    new(q);
    q^.data:=newl;      (* новое звено *)
    q^.dr:=st;
    st:=q;      (* новое звено - вершина *)
end;

Наличие у процедуры аргумента push(var st:stack, ... ) позволяет работать с несколькими стеками.


function pop(var st:stack):stype;
var
    q:next;
begin
    if st=nil then
      writeln('Стек пуст.')
    else
    begin
      pop:=st^.data;
      q:=st;
      st:=st^.dr;
      dispose(q)
    end;
end;

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;
}



[ Назад | Вперед ]
Хостинг от uCoz