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

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.


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

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

Контрольные вопросы


1. Что представляет собой стек?
2. На основе каких структур данных могут организовываться стеки?
3. Чем отличается стек на основе массива от стека на основе связного списка?
4. Чем отличается стек на основе связного списка от собственно связного списка?
5. К каким структурам данных относятся очереди и стеки?
6. Перечислите основные отличия стека от очереди.
7. Какой метод доступа используется при доступе к элементам стека? В чем его особенности?
8. Перечислите основные операции, применяемые при работе со стеками. К каким позициям в стеке они могут применяться?
9. Какой характер имеет операция считывания для стеков?
10. Перечислите задачи, для решения которых применяются стеки.
11. Изобразите структуру звена динамического стека.
12. Как определить наличие или отсутствие элементов в стеке?
13. Как определить количество элементов в стеке?


Тест для самопроверки

< Назад | Вперед >

Хостинг от uCoz