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

Предыдущая статья: “Структуры данных: кольцевой (циклический, замкнутый) связный список”

Стек  —  это абстрактный тип данных, который обычно используется в большинстве языков программирования. Хорошие примеры для объяснения понятия стека  —  колода карт или стопка тарелок:

Причем положить новую карту в колоду или тарелку в стопку можно только сверху. Взять карту из колоды или тарелку из стопки тоже можно только сверху.

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

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

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

Вот как схематически изображается стек и его операции:

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

Базовые операции

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

• push()  —  вставка (сохранение) элемента в стек;
• pop()  —  удаление (доступ) элемента из стека.

Когда данные вставляются (PUSH) в стек.

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

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

Указатель всегда указывает на данные, которые вставлялись (PUSH) в стек последними. Этот указатель всегда является вершиной стека, поэтому называется top («вершина»). Указатель top («вершина») предоставляет верхнее значение стека, не удаляя его фактически.

Рассмотрим сначала процедуры, являющиеся частью функций стека:

peek()

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

begin procedure peek
   return stack[top]
end procedure

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

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

isfull()

Алгоритм функции 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()

Алгоритм функции 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). Операция вставки проходит в несколько этапов:

• Этап 1: проверяется, заполнен ли стек.
• Этап 2: если стек заполнен, выдается ошибка и операция завершается.
• Этап 3: если стек не заполнен, top увеличивается, указывая на следующее пустое место.
• Этап 4: в то место стека, на которое указывает top (вершина), добавляется элемент данных.
• Этап 5: возвращается сообщение об успешном завершении.

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

Алгоритм для операции вставки (PUSH)

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

begin procedure push: stack, data

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

end procedure

Реализация этого алгоритма на С очень проста. Вот пример кода:

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: если стек не пустой, осуществляется доступ к тому элементу данных, на который указывает top (вершина).
• Этап 4: значение top уменьшается на 1.
• Этап 5: возвращается сообщение об успешном завершении.

Алгоритм для операции удаления (Pop)

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

begin procedure pop: stack

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

end procedure

Вот пример реализации этого алгоритма на С:

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

Читайте также:

• Для чего нужны стеки?
• Чистая архитектура: руководство для начинающих
• Хотите стать счастливым и продуктивным программистом? Используйте эти 5 методов из Психологии!

Читайте нас в Telegram, VK и Яндекс.Дзен