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

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

Пример стека

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

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

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

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

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

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

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

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

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

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

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

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

  • 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 - Возвращает успех.

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

Если связанный список используется для реализации стека, то на шаге 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 () элемент данных фактически не удаляется, вместо этого top уменьшается до нижней позиции в стеке, чтобы указывать на следующее значение. Но в реализации связного списка pop () фактически удаляет элемент данных и освобождает пространство памяти.

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

  • Шаг 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, пожалуйста, нажмите здесь .

Назад Вперёд