Четвер, 21.11.2024, 19:57
Гость

Мішатронік

Мобільна версія | Додати у вибране  | Мій профіль | Вихід | RSS |
Меню сайту
Наше опитування
Які схеми ви любите паяти?
[ Результати · Архів опитувань ]
Всього відповідей: 5
Статистика
Онлайн всього: 1
Гостей: 1
Користувачів: 0

Стек. Отличия стека от списка. Основные операции со стеком

Сейчас Вы познакомитесь с одной из разновидностей обычного линейного списка – стеком. Этот вид списка очень часто используется в программировании.

Стек – это линейный список, в котором добавление новых элементов и удаление существующих производится только с одного конца, называемого вершиной стека.

Стек часто называют структурой LIFO (сокращение LIFO означает Last In – First Out, т.е. последним пришел – первым вышел). Это сокращение помогает запомнить механизм работы стека.

Изобразим стек графически:

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

Стек предполагает вставку и удаление элементов, поэтому он является динамической, постоянно меняющейся структурой.

Стеки довольно часто встречаются в практической жизни. Простой пример: детская пирамидка. Процесс ее сборки и разборки подобен процессу функционирования стека.

Итак, стек – это такой список, добавление или извлечение элементов которого происходит с начала и только с начала (или, возможно, с конца и только с конца) списка.

Значением указателя, представляющего стек, является ссылка на вершину стека, и каждый элемент стека содержит поле ссылки на соседний, "нижний" элемент.

Таким образом, описать стек можно следующим образом:

Type
  EXST = ^ST;
  ST = record
       Data : integer;
       Next : EXST;
  end;
Var
  Stack : EXST; {Текущая переменная}

Если стек пуст, то значение указателя равно Nil.

Рассмотрим возможные операции со стеком.

Занесение элемента в стек

Занесение элемента в стек производится аналогично вставке нового элемента в начало списка. Процедура занесения элемента в стек должна содержать два параметра: первый задает вершину стека, в который нужно занести элемент, второй – заносимое значение элемента стека.

Процедура формирования стека будет иметь следующий вид:

Procedure FormStack;
Var
  Stack : EXST; {Текущая переменная}
  Digit : integer;
Procedure writeStack(Var u : EXST; Digit : integer);
Var
  x : EXST;
Begin
  new(x); {выделяем память под хранение нового элемента стека}
  x^.Data := Digit; {заполняем поле данных элемента}
  x^.Next := u; {новый элемент "связываем" со стеком}
  u := x; {созданный элемент определяем как вершину стека}
End;
Begin
  Stack := Nil; {инициализация стека}
  writeln('Введите элементы стека. Окончание ввода – 0');
  read(Digit);
  while Digit <> 0 do
    begin
      writeStack(Stack, Digit);
      read(Digit);
    end;
End;

Извлечение элемента из стека

В результате выполнения этой операции некоторой переменной i должно быть присвоено значение первого элемента стека, и значение указателя на начало списка должно быть перенесено на следующий элемент стека.

Procedure readStack(Var u : EXST; Var i : integer);
Var
  x : EXST;
Begin
  i := u^.Data; {считываем значение поля данных в переменную}
  x := u; {запоминаем адрес вершины стека}
  u := u^.Next; {переносим вершину стека на следующий элемент}
  dispose(x); {освобождаем память, занятую уже ненужным элементом стека}
End.

Недостатком описанной процедуры является предположение о том, что стек не пуст. Для его исправления следует разработать логическую функцию, определяющую, пуст ли обрабатываемый стек.

Function FreeStack(u : EXST) : boolean;

Задание. Описать функцию и закончить программу, для чего описать процедуру вывода значений элементов стека на экран (она аналогична выводу списка). Протестировать программу, дополнить комментарием.

Примеры решения задач

Пример 1. Используя стек, напечатать содержимое текстового файла, выписывая литеры каждой его строки в обратном порядке.

Program MordovskihK;
Type
  EXST = ^ST;
  ST = record
       Data : char;
       Next : EXST;
  End;
Var
  Stack : EXST; {Текущая переменная}
  i : integer;
  f : text;
  Stroka : string;
  c : char;
Procedure writeStack(Var u : EXST; Simvol : char);
Var
  x : EXST;
Begin
  new(x); 
  x^.Data := Simvol; 
  x^.Next := u; 
  u := x; 
End;
Procedure Print(Var u : EXST);
Begin
  while u <> Nil do
    Begin
      write (u^.Data);
      u := u^.Next;
    End;
  End;
Begin
  Stack := Nil; 
  Assign(f, 'c:\autoexec.bat');
  Reset(f);
  while Not Eof(f) do
    Begin
      readln (f, Stroka);
      For i := 1 to Length(Stroka) do
        writeStack(Stack, Stroka[i]);
      Print(Stack);
      writeln;
    End;
  close(f);
End.

Пример 2. Написать программу, проверяющую своевременность закрытия скобок в строке символов.

Для решения задачи определим стек, элементами которого являются символы:

Type
  EXST = ^ST;
  ST = record
       Data : char;
       Next : EXST;
  End;

Будем двигаться по строке а : string до ее конца. Если в процессе просмотра встретится одна из открывающих скобок ({, (, [ ), занесем ее в стек. При обнаружении закрывающей скобки, соответствующей скобке, находящейся в вершине стека, последняя удаляется. При несоответствии скобок выдается сообщение об ошибке.

Пусть факт наличия ошибки хранится в переменной логического типа f, то есть f=True, пока ошибка не найдена и f=False в противном случае. Тогда условие работы цикла будет выглядеть так:

while (i<>Length(a)) and f do ...

Осталось выяснить, как определить, соответствует ли очередная закрывающая скобка скобке, находящейся в вершине стека. Можно заметить, что коды соответствующих друг другу скобок отличаются не более чем на 2, что можно проверить с помощью функции Ord(x)):

{ } 123–125
[ ] 91–93
( ) 40–41,

причем код открывающей скобки меньше. Таким образом, можно записать следующее условие соответствия:

if (Ord(a[i])–Ord(stack^.Data))<=2
  then
    . . .

А теперь просмотрите полный текст программы:

Program Skobki;
Type
  EXST = ^ST;
  ST = record
       Data : char;
       Next : EXST;
  end;
Var
  a : string;
  f : boolean;
  i : integer;
Procedure writeStack(Var x1 : EXST; c : char);
Var
  u : EXST;
Begin
  new(u); {создание нового элемента стека}
  u^.Data := c;
  u^.Next := x1; 
  x1 := u; {созданный элемент определить как вершину стека}
End;
Procedure DelStack(Var x1 : EXST); {процедура удаления верхнего элемента стека}
Var
  u : EXST;
Begin
  u := x1;
  x1 := x1^.Next;
  dispose(u);
End;
Procedure Solve(a : string); {проверка правильности расстановки скобок}
Var
  Stack : EXST;
Begin
  Stack := Nil;
  i := 1;
  while (i<=Length(a)) and f do
    begin
      if (a[i]='(') or (a[i]='{') or (a[i]='[')
        then
          writeStack(Stack , a[i])
        else 
          if (a[i]=')') or (a[i]='}') or (a[i]=']')
            then
              if (Stack <> Nil) And (Ord(a[i]) - Ord(Stack ^.Data) <= 2)
                then
                  DelStack(Stack)
                else
                  f := False;
      Inc(i);
  end;
end;
Begin
  writeln('Введите строку');
  readln(a);
  f := True;
  if a<>''
    then
      begin
        Solve(a);
        if f
          then
            writeln('Все скобки расставлены верно')
          else
            writeln('Скобка ',a[i-1],' закрыта преждевременно');
      end
    else
      writeln('Строка пуста');
  readln;
End.

 
Форма входа
Пошук
Друзі сайту
  • Codeforces, спротивне програмування
  • GitHub - Система контролю версій
  • GitLab - Система контролю версій
  • Bitbucket - Система контролю версій
  • Trello - Система менеджменту
  • Firebase, платформа по розробці додатків
    • Календар
    «  Листопад 2024  »
    ПнВтСрЧтПтСбНд
        123
    45678910
    11121314151617
    18192021222324
    252627282930

    Єдина Країна! Единая Страна!