Стек

Стек (от англ. stack — стопка) — структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел — первым вышел» (last-in, first-out — LIFO).

 

Переменная

 

Примером стека в реальной жизни может являться стопка тарелок: когда мы хотим вытащить тарелку, мы должны снять все тарелки выше:

 

Переменная

 

Классический стек поддерживает всего лишь три операции:

 

● empty — проверка стека на наличие в нем элементов,

● push (запись в стек) — операция вставки нового элемента,

● pop (снятие со стека) — операция удаления нового элемента.

Реализация на массиве

Перед реализацией стека выделим ключевые поля:

 

● \(array[1 \ldots n] \) — массив, с помощью которого реализуется стек, способный вместить не более \(n\) элементов,

● \(top\) — индекс последнего помещенного в стек элемента.

 

Стек состоит из элементов \(array[1\ldots top]\), где \(array[1]\) — элемент на дне стека, а \(array[top]\) — элемент на его вершине. Если \(top = 0\), то стек не содержит ни одного элемента и является пустым (англ. empty). Протестировать стек на наличие в нем элементов можно с помощью операции — запроса \(empty\). Если элемент снимается с пустого стека, говорят, что он опустошается (англ. underflow), что обычно приводит к ошибке. Если значение \(top\) больше \(n\), то стек переполняется (англ. overflow). (В представленном ниже коде возможное переполнение во внимание не принимается.)

class Stack:
   
  def __init__(self, n):
    self.array = [0] * (n + 1)
    self.top = 0
    
  def empty(self):
    return self.top == 0
   
  def push(self, element):
    self.top += 1
    self.array[self.top] = element
     
  def pop(self):
    if self.empty():
      return 'UnderflowError'
    self.top -= 1
    return self.array[self.top + 1]

Как видно из кода выше, все операции со стеком выполняются за \(O(1)\).

Реализация на списке Python

class Stack:
   
  def __init__(self):
    self.array = []
    
  def empty(self):
    return not self.array
   
  def push(self, element):
    self.array.append(element)
     
  def pop(self):
    if self.empty():
      return 'UnderflowError'
    return self.array.pop()

Обратная польская запись

Обратная польская запись — форма записи математических выражений, в которой операнды расположены перед знаками операций. Её преимущество в том, что выражение записанное таким образом можно вычислить за один проход.

Алгоритм вычисления

  1. Обработка входного символа:

    ● Если на вход подан операнд, он помещается на вершину стека.

    ● Если на вход подан знак операции, то соответствующая операция выполняется над двумя значениями, извлечённых из стека, взятых в порядке добавления. Результат выполненной операции кладётся на вершину стека.

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

Пример вычисления выражений

Инфиксное выражение \((1+2)×4+3\) в обратной польской нотации может быть записано так: \(1 \ \ 2 + 4 × 3 +\)

 

Вычисление производится слева направо, ввод интерпретируется как указано в приведённой ниже таблице (указано состояние стека после выполнения операции, вершина стека выделена красным цветом):

Ввод Операция Стек
1 поместить в стек
1
2 поместить в стек
1, 2
+ сложение
3
4 поместить в стек
3, 4
* умножение
12
3 поместить в стек
12, 3
+ сложение
15

Результат, \(15\), в конце вычислений находится на вершине стека.

Алгоритм преобразования из инфиксной нотации

Эдсгер Дейкстра изобрёл алгоритм для преобразования выражений из инфиксной нотации в обратную польскую запись. Алгоритм получил название «сортировочная станция», за сходство его операций с происходящим на железнодорожных сортировочных станциях. В преобразовании участвуют две текстовых переменных: входная и выходная строки. В процессе преобразования используется стек, хранящий ещё не добавленные к выходной строке операции. Преобразующая программа читает входную строку последовательно символ за символом (символ — это не обязательно буква), выполняет на каждом шаге некоторые действия в зависимости от того, какой символ был прочитан.

 

● Пока есть ещё символы для чтения:

● Читаем очередной символ.
● Если символ является числом или постфиксной функцией (например, ! — факториал), добавляем его к выходной строке.
● Если символ является префиксной функцией (например, sin — синус), помещаем его в стек.
● Если символ является открывающей скобкой, помещаем его в стек.
● Если символ является закрывающей скобкой:

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

● Если символ является бинарной операцией \(o_1\), тогда:

  1. пока на вершине стека префиксная функция или операция на вершине стека приоритетнее или такого же уровня приоритета как \(o_1\) выталкиваем верхний элемент стека в выходную строку;
  2. помещаем операцию \(o_1\) в стек.

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

 

Алгоритм предполагает, что исходная строка корректна (проверяются не все ошибки), и все префиксные/постфиксные функции унарные. Для операций вроде \(-x\), являющихся как бинарными, так и унарными, нужна модификация: при обнаружении подобной операции система смотрит на предыдущий символ и определяет, чем будет минус, бинарной операцией или унарной функцией. Соответственно, в стеке и обратной польской записи нужны разные символы для бинарного и унарного минуса.

Пример

Приоритеты:

● самый высокий: выражения, заключённые в скобки ( );
● высокий: ^;
● средний: *, /;
● низкий: +, -.

Вход: 3 + 4 * 2 / (1 - 5)^2

Читаем «3»
 Добавим «3» к выходной строке
  Выход: 3

Читаем «+»
 Кладём «+» в стек
  Выход: 3
  Стек: +

Читаем «4»
 Добавим «4» к выходной строке
  Выход: 3 4
  Стек: +

Читаем «*»
 Кладём «*» в стек
  Выход: 3 4
  Стек: + *

Читаем «2»
 Добавим «2» к выходной строке
  Выход: 3 4 2
  Стек: + *

Читаем «/»
 Выталкиваем «*» из стека в выходную строку, кладём «/» в стек
  Выход: 3 4 2 *
  Стек: + /

Читаем «(»
 Кладём «(» в стек
  Выход: 3 4 2 *
  Стек: + / (

Читаем «1»
 Добавим «1» к выходной строке
  Выход: 3 4 2 * 1
  Стек: + / (

Читаем «−»
 Кладём «−» в стек
  Выход: 3 4 2 * 1
  Стек: + / ( −

Читаем «5»
 Добавим «5» к выходной строке
  Выход: 3 4 2 * 1 5
  Стек: + / ( -

Читаем «)»
 Выталкиваем «−» из стека в выходную строку, выталкиваем «(»
  Выход: 3 4 2 * 1 5 −
  Стек: + /

Читаем «^»
 Кладём «^» в стек
  Выход: 3 4 2 * 1 5 −
  Стек: + / ^

Читаем «2»
 Добавим «2» к выходной строке
  Выход: 3 4 2 * 1 5 − 2
  Стек: + / ^

Конец выражения
 Выталкиваем все элементы из стека в строку
  Выход: 3 4 2 * 1 5 − 2 ^ / +

Модификация стека

Представим себе, что стек должен поддерживать следующий набор операций:

 

● Поддержка минимума (min)
● Поддержка максимума (max)
● Поддержка gcd (англ. greatest common divisor — наибольший общий делитель)
● Поддержка lcm (англ. least common multiple — наименьшее общее кратное)

 

Все перечисленные операции ассоциативны (образуют полугруппу), но ни одна из них не имеет обратного элемента (не образует группу).

 

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

 

\((element, operation\_result)\),

 

где второй элемент пары — результат операции, примененной ко всем элементам стека.

 

Пример реализации стека с поддержкой максимума:

class MaxStack:
   
  def __init__(self):
    self.array = []
    
  def empty(self):
    return not self.array
   
  def push(self, element):
    if self.empty():
      self.array.append((element, element))
    else:
      max_element = max(element, self.array[-1][-1])
      self.array.append((element, max_element))
     
  def pop(self):
    if self.empty():
      return 'UnderflowError'
    return self.array.pop()
  
  def get_max(self):
    if self.empty():
      return float('-inf')
    return self.array[-1][-1]

Монотонный стек

Монотонный стек — это стек, который поддерживает свои элементы в определённом порядке. В отличие от обычного стека, монотонный стек гарантирует, что элементы внутри него будут расположены в порядке возрастания (неубывания) или убывания (невозрастания) в зависимости от времени их прибытия. Чтобы получить монотонный стек, нам нужно применить операцию push и pop в зависимости от того, хотим ли мы получить монотонно возрастающий стек или монотонно убывающий стек.

 

Переменная

 

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

nums = [3, 1, 4, 1, 5, 9, 2, 6]
stack = []
for num in nums:
  while stack and stack[-1] >= num:
    stack.pop()
  stack.append(num)

 

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

Пример

Дан массив \(a\), состоящий из \(n\) целых чисел. Для каждого элемента \(a_i\) выведите номер ближайшего справа большего элемента. Если такого элемента нет, то выведите \(-1.\)

n = int(input())
a = list(map(int, input().split()))

stack = []
ans = [-1] * n
for i in range(n):
    while stack and a[i] > stack[-1][0]:
        idx = stack.pop()[1]
        ans[idx] = i + 1
    stack.append((a[i], i))
print(*ans)
5
4 3 5 1 2

3 3 -1 5 -1

Чтобы находить ближайшие слева элементы, нужно итерироваться в обратном порядке (от \(n-1\) до \(0\)).

Практические задания