Компьютерный центр г. Светлогорска

Стек (от англ. 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 +\)

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

Результат, \(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 ^ / +

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]

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)

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