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

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

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

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

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

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

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

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

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

push() - Размещение (сохранение) элемента в стеке.
pop() - Удаление (доступ) элемента из стека.

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

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

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

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

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

заглянуть ()

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

begin procedure peek
   return stack[top]
end procedure

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

Example

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

полон()

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

begin procedure isfull

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

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

Example

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, чтобы определить, пуст ли стек. Вот код -

Example

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

Нажать операцию

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

Step 1 - Проверяет, заполнен ли стек.
Step 2 - Если стек заполнен, выдает ошибку и выходит.
Step 3 - Если стек не заполнен, увеличивается top чтобы указать следующее пустое пространство.
Step 4 - Добавляет элемент данных в то место стека, куда указывает вершина.
Step 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 очень просто. См. Следующий код -

Example

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

Поп-операция

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

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

Step 1 - Проверяет, пуста ли стопка.
Step 2 - Если стек пуст, выдает ошибку и выходит.
Step 3 - Если стек не пуст, обращается к элементу данных, в котором top указывает.
Step 4 - Уменьшает значение вершины на 1.
Step 5 - Возвращает успех.

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

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

begin procedure pop: stack

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

end procedure

Реализация этого алгоритма на C выглядит следующим образом:

Example

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, щелкните здесь .