Учебники

Структура данных и алгоритмы — стек

Декабрь 12, 2018

Стек — это абстрактный тип данных (ADT), обычно используемый в большинстве языков программирования. Он называется стеком, так как он ведет себя как реальный стек, например, колода карт или куча тарелок и т. Д.

Пример стека

Реальный стек допускает операции только с одного конца. Например, мы можем поместить или удалить карту или пластину только из верхней части стопки. Аналогично, Stack ADT разрешает все операции с данными только на одном конце. В любой момент времени мы можем получить доступ только к верхнему элементу стека.

Эта особенность делает его структурой данных LIFO. LIFO означает «Последний пришел первым». Здесь элемент, который помещен (вставлен или добавлен) последним, доступен первым. В терминологии стека операция вставки называется операцией PUSH, а операция удаления — операцией POP .

Представление стека

Следующая диаграмма изображает стек и его операции —

Представление стека

Стек может быть реализован с помощью Array, Structure, Pointer и Linked List. Стек может быть фиксированного размера или иметь динамическое изменение размера. Здесь мы собираемся реализовать стек с использованием массивов, что делает его реализацией стека фиксированного размера.

Основные операции

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

  • push () — Push ( сохранение) элемента в стеке.

  • pop () — Удаление (доступ) элемента из стека.

push () — Push ( сохранение) элемента в стеке.

pop () — Удаление (доступ) элемента из стека.

Когда данные помещаются в стек.

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

  • peek () — получить верхний элемент данных стека, не удаляя его.

  • isFull () — проверить, заполнен ли стек.

  • isEmpty () — проверить, пуст ли стек.

peek () — получить верхний элемент данных стека, не удаляя его.

isFull () — проверить, заполнен ли стек.

isEmpty () — проверить, пуст ли стек.

Мы всегда поддерживаем указатель на последние данные PUSHed в стеке. Поскольку этот указатель всегда представляет вершину стека, отсюда и название top . Верхний указатель предоставляет верхнее значение стека, фактически не удаляя его.

Сначала мы должны узнать о процедурах для поддержки функций стека —

PEEK ()

Алгоритм функции peek () — 

begin procedure peek
   return stack[top]
end procedure

Реализация функции peek () на языке программирования C —

пример 

int peek() {
   return stack[top];
}

полный()

Алгоритм функции isfull () — 

begin procedure isfull

   if top equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

Реализация функции isfull () на языке программирования C —

пример 

bool isfull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

пустой()

Алгоритм функции isempty () — 

begin procedure isempty

   if top less than 1
      return true
   else
      return false
   endif
   
end procedure

Реализация функции isempty () в языке программирования C немного отличается. Мы инициализируем вершину в -1, так как индекс в массиве начинается с 0. Поэтому мы проверяем, находится ли вершина ниже нуля или -1, чтобы определить, является ли стек пустым. Вот код —

пример 

bool isempty() {
   if(top == -1)
      return true;
   else
      return false;
}

Push Operation

Процесс помещения нового элемента данных в стек известен как операция Push. Push-операция включает в себя ряд шагов —

  • Шаг 1 — Проверяет, заполнен ли стек.

  • Шаг 2 — Если стек заполнен, выдает ошибку и завершается.

  • Шаг 3 — Если стек не заполнен, увеличивается сверху вниз, чтобы указать следующий пустой пробел.

  • Шаг 4 — Добавляет элемент данных в расположение стека, куда указывает верх.

  • Шаг 5 — Возвращает успех.

Шаг 1 — Проверяет, заполнен ли стек.

Шаг 2 — Если стек заполнен, выдает ошибку и завершается.

Шаг 3 — Если стек не заполнен, увеличивается сверху вниз, чтобы указать следующий пустой пробел.

Шаг 4 — Добавляет элемент данных в расположение стека, куда указывает верх.

Шаг 5 — Возвращает успех.

Стек операции

Если связанный список используется для реализации стека, то на шаге 3 нам нужно динамически распределять пространство.

Алгоритм работы PUSH

Простой алгоритм операции Push может быть получен следующим образом: 

begin procedure push: stack, data

   if stack is full
      return null
   endif
   
   top ← top + 1
   stack[top] ← data

end procedure

Реализация этого алгоритма на C очень проста. Смотрите следующий код —

пример 

void push(int data) {
   if(!isFull()) {
      top = top + 1;   
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

Поп Операция

Доступ к контенту при удалении его из стека известен как операция Pop. В реализации массива операции pop () элемент данных фактически не удаляется, вместо этого верхняя часть уменьшается в нижнюю позицию в стеке, чтобы указывать на следующее значение. Но в реализации связанного списка pop () фактически удаляет элемент данных и освобождает пространство памяти.

Операция Pop может включать следующие шаги:

  • Шаг 1 — Проверяет, пуст ли стек.

  • Шаг 2 — Если стек пуст, выдает ошибку и завершается.

  • Шаг 3 — Если стек не пуст, обращается к элементу данных, на который указывает вершина .

  • Шаг 4 — Уменьшает значение вершины на 1.

  • Шаг 5 — Возвращает успех.

Шаг 1 — Проверяет, пуст ли стек.

Шаг 2 — Если стек пуст, выдает ошибку и завершается.

Шаг 3 — Если стек не пуст, обращается к элементу данных, на который указывает вершина .

Шаг 4 — Уменьшает значение вершины на 1.

Шаг 5 — Возвращает успех.

Стек Поп Операция

Алгоритм для поп-операции

Простой алгоритм операции Pop может быть получен следующим образом: 

begin procedure pop: stack

   if stack is empty
      return null
   endif
   
   data ← stack[top]
   top ← top - 1
   return data

end procedure

Реализация этого алгоритма в C, заключается в следующем —

пример 

int pop(int data) {

   if(!isempty()) {
      data = stack[top];
      top = top - 1;   
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

Для полной программы стека на языке программирования C, пожалуйста, нажмите здесь .

52
Share: