Стек

Стек (Stack)

Что такое стек?

Стек — это структура данных, работающая по принципу LIFO (Last In, First Out — последний вошёл, первый вышел). Представь стопку тарелок: ты кладёшь тарелку сверху и берёшь тоже сверху.

Push (добавление):        Pop (извлечение):

    | 4 | <- top           | 4 | -> удалён
    | 3 |                  | 3 | <- новый top
    | 2 |                  | 2 |
    | 1 |                  | 1 |
    +---+                  +---+

Операции стека

Операция	Описание	Сложность
push(x)	Положить элемент на вершину	O(1)
pop()	Убрать элемент с вершины	O(1)
peek/top()	Посмотреть вершину	O(1)
isEmpty()	Проверка на пустоту	O(1)
size()	Количество элементов	O(1)

Реализация

class Stack
{
    private array $items = [];

    public function push(int $val): void
    {
        $this->items[] = $val;
    }

    public function pop(): int
    {
        if ($this->isEmpty()) {
            throw new UnderflowException('Stack is empty');
        }
        return array_pop($this->items);
    }

    public function peek(): int
    {
        if ($this->isEmpty()) {
            throw new UnderflowException('Stack is empty');
        }
        return $this->items[count($this->items) - 1];
    }

    public function isEmpty(): bool
    {
        return count($this->items) === 0;
    }

    public function size(): int
    {
        return count($this->items);
    }
}

// In practice, just use array as stack:
$stack = [];
$stack[] = 1;          // push
$stack[] = 2;
array_pop($stack);     // pop -> 2
end($stack);           // peek -> 1

package main

import "errors"

// Stack represents an integer stack.
type Stack struct {
	items []int
}

func (s *Stack) Push(val int) {
	s.items = append(s.items, val)
}

func (s *Stack) Pop() (int, error) {
	if s.IsEmpty() {
		return 0, errors.New("stack is empty")
	}
	top := s.items[len(s.items)-1]
	s.items = s.items[:len(s.items)-1]
	return top, nil
}

func (s *Stack) Peek() (int, error) {
	if s.IsEmpty() {
		return 0, errors.New("stack is empty")
	}
	return s.items[len(s.items)-1], nil
}

func (s *Stack) IsEmpty() bool {
	return len(s.items) == 0
}

func (s *Stack) Size() int {
	return len(s.items)
}

// In practice, just use a slice as stack:
// stack := []int{}
// stack = append(stack, 1)           // push
// stack = append(stack, 2)
// stack = stack[:len(stack)-1]       // pop -> 2
// top := stack[len(stack)-1]         // peek -> 1

using System.Collections.Generic;

public class IntStack
{
    private readonly List<int> _items = [];

    public void Push(int val) => _items.Add(val);

    public int Pop()
    {
        if (IsEmpty)
        {
            throw new InvalidOperationException("Stack is empty");
        }
        var top = _items[^1];
        _items.RemoveAt(_items.Count - 1);
        return top;
    }

    public int Peek()
    {
        if (IsEmpty)
        {
            throw new InvalidOperationException("Stack is empty");
        }
        return _items[^1];
    }

    public bool IsEmpty => _items.Count == 0;

    public int Size => _items.Count;
}

// In practice, just use the built-in Stack<T>:
var stack = new Stack<int>();
stack.Push(1);      // push
stack.Push(2);
stack.Pop();        // pop -> 2
stack.Peek();       // peek -> 1

class Stack:
    def __init__(self) -> None:
        self._items: list[int] = []

    def push(self, val: int) -> None:
        self._items.append(val)

    def pop(self) -> int:
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._items.pop()

    def peek(self) -> int:
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._items[-1]

    def is_empty(self) -> bool:
        return not self._items

    def __len__(self) -> int:
        return len(self._items)

# In practice, just use a list as stack — append/pop are amortized O(1):
stack: list[int] = []
stack.append(1)     # push
stack.append(2)
stack.pop()         # pop -> 2
top = stack[-1]     # peek -> 1

## Задача 1: Валидные скобки

Условие: строка содержит (){}[]. Проверить корректность.

function isValidParentheses(string $s): bool
{
    $stack = [];
    $matching = [')' => '(', '}' => '{', ']' => '['];

    for ($i = 0; $i < strlen($s); $i++) {
        $char = $s[$i];
        if (in_array($char, ['(', '{', '['])) {
            $stack[] = $char;
        } elseif (isset($matching[$char])) {
            if (empty($stack) || end($stack) !== $matching[$char]) {
                return false;
            }
            array_pop($stack);
        }
    }

    return empty($stack);
}

func isValidParentheses(s string) bool {
	stack := []byte{}
	matching := map[byte]byte{
		')': '(',
		'}': '{',
		']': '[',
	}

	for i := 0; i < len(s); i++ {
		ch := s[i]
		switch ch {
		case '(', '{', '[':
			stack = append(stack, ch)
		case ')', '}', ']':
			if len(stack) == 0 || stack[len(stack)-1] != matching[ch] {
				return false
			}
			stack = stack[:len(stack)-1]
		}
	}

	return len(stack) == 0
}

static bool IsValidParentheses(string s)
{
    var stack = new Stack<char>();
    var matching = new Dictionary<char, char>
    {
        [')'] = '(',
        ['}'] = '{',
        [']'] = '[',
    };

    foreach (var ch in s)
    {
        if (ch is '(' or '{' or '[')
        {
            stack.Push(ch);
        }
        else if (matching.TryGetValue(ch, out var open))
        {
            if (stack.Count == 0 || stack.Pop() != open)
            {
                return false;
            }
        }
    }

    return stack.Count == 0;
}

def is_valid_parentheses(s: str) -> bool:
    stack: list[str] = []
    matching = {")": "(", "}": "{", "]": "["}

    for char in s:
        if char in "({[":
            stack.append(char)
        elif char in matching:
            if not stack or stack.pop() != matching[char]:
                return False

    return not stack

Визуализация для `{[()]}`:

Символ  Стек        Действие
  {     [{]         push
  [     [{, []      push
  (     [{, [, (]   push
  )     [{, []      pop (match)
  ]     [{]         pop (match)
  }     []          pop (match)
                    Стек пуст -> true

Задача 2: Min Stack

Условие: стек, который поддерживает push, pop, top и getMin — всё за O(1).

class MinStack
{
    private array $stack = [];
    private array $minStack = [];

    public function push(int $val): void
    {
        $this->stack[] = $val;
        if (empty($this->minStack) || $val <= end($this->minStack)) {
            $this->minStack[] = $val;
        }
    }

    public function pop(): void
    {
        $val = array_pop($this->stack);
        if ($val === end($this->minStack)) {
            array_pop($this->minStack);
        }
    }

    public function top(): int
    {
        return end($this->stack);
    }

    public function getMin(): int
    {
        return end($this->minStack);
    }
}

// MinStack supports push, pop, top, and getMin in O(1).
type MinStack struct {
	stack    []int
	minStack []int
}

func (s *MinStack) Push(val int) {
	s.stack = append(s.stack, val)
	if len(s.minStack) == 0 || val <= s.minStack[len(s.minStack)-1] {
		s.minStack = append(s.minStack, val)
	}
}

func (s *MinStack) Pop() {
	val := s.stack[len(s.stack)-1]
	s.stack = s.stack[:len(s.stack)-1]
	if val == s.minStack[len(s.minStack)-1] {
		s.minStack = s.minStack[:len(s.minStack)-1]
	}
}

func (s *MinStack) Top() int {
	return s.stack[len(s.stack)-1]
}

func (s *MinStack) GetMin() int {
	return s.minStack[len(s.minStack)-1]
}

// MinStack supports Push, Pop, Top, and GetMin in O(1).
public class MinStack
{
    private readonly Stack<int> _stack = new();
    private readonly Stack<int> _minStack = new();

    public void Push(int val)
    {
        _stack.Push(val);
        if (_minStack.Count == 0 || val <= _minStack.Peek())
        {
            _minStack.Push(val);
        }
    }

    public void Pop()
    {
        var val = _stack.Pop();
        if (val == _minStack.Peek())
        {
            _minStack.Pop();
        }
    }

    public int Top() => _stack.Peek();

    public int GetMin() => _minStack.Peek();
}

# MinStack supports push, pop, top and get_min in O(1).
class MinStack:
    def __init__(self) -> None:
        self._stack: list[int] = []
        self._min_stack: list[int] = []

    def push(self, val: int) -> None:
        self._stack.append(val)
        if not self._min_stack or val <= self._min_stack[-1]:
            self._min_stack.append(val)

    def pop(self) -> None:
        val = self._stack.pop()
        if val == self._min_stack[-1]:
            self._min_stack.pop()

    def top(self) -> int:
        return self._stack[-1]

    def get_min(self) -> int:
        return self._min_stack[-1]

## Задача 3: Обратная польская нотация (RPN)

function evalRPN(array $tokens): int
{
    $stack = [];

    foreach ($tokens as $token) {
        if (in_array($token, ['+', '-', '*', '/'])) {
            $b = array_pop($stack);
            $a = array_pop($stack);
            $stack[] = match ($token) {
                '+' => $a + $b,
                '-' => $a - $b,
                '*' => $a * $b,
                '/' => intdiv($a, $b),
            };
        } else {
            $stack[] = (int) $token;
        }
    }

    return $stack[0];
}

import "strconv"

func evalRPN(tokens []string) int {
	stack := []int{}

	for _, token := range tokens {
		switch token {
		case "+", "-", "*", "/":
			b := stack[len(stack)-1]
			a := stack[len(stack)-2]
			stack = stack[:len(stack)-2]

			switch token {
			case "+":
				stack = append(stack, a+b)
			case "-":
				stack = append(stack, a-b)
			case "*":
				stack = append(stack, a*b)
			case "/":
				stack = append(stack, a/b) // integer division in Go
			}
		default:
			num, _ := strconv.Atoi(token)
			stack = append(stack, num)
		}
	}

	return stack[0]
}

static int EvalRPN(string[] tokens)
{
    var stack = new Stack<int>();

    foreach (var token in tokens)
    {
        if (token is "+" or "-" or "*" or "/")
        {
            var b = stack.Pop();
            var a = stack.Pop();
            stack.Push(token switch
            {
                "+" => a + b,
                "-" => a - b,
                "*" => a * b,
                "/" => a / b, // integer division in C#
                _ => throw new ArgumentException($"Unknown operator: {token}"),
            });
        }
        else
        {
            stack.Push(int.Parse(token));
        }
    }

    return stack.Pop();
}

import operator
from collections.abc import Callable

# Note: // floors toward negative infinity, so truncate like PHP intdiv / Go
OPS: dict[str, Callable[[int, int], int]] = {
    "+": operator.add,
    "-": operator.sub,
    "*": operator.mul,
    "/": lambda a, b: int(a / b),
}

def eval_rpn(tokens: list[str]) -> int:
    stack: list[int] = []

    for token in tokens:
        if token in OPS:
            b = stack.pop()
            a = stack.pop()
            stack.append(OPS[token](a, b))
        else:
            stack.append(int(token))

    return stack[0]

## Задача 4: Упрощение пути (Simplify Path)

function simplifyPath(string $path): string
{
    $stack = [];
    $parts = explode('/', $path);

    foreach ($parts as $part) {
        if ($part === '..') {
            if (!empty($stack)) {
                array_pop($stack);
            }
        } elseif ($part !== '' && $part !== '.') {
            $stack[] = $part;
        }
    }

    return '/' . implode('/', $stack);
}

import "strings"

func simplifyPath(path string) string {
	stack := []string{}
	parts := strings.Split(path, "/")

	for _, part := range parts {
		switch part {
		case "..", "":
			if part == ".." && len(stack) > 0 {
				stack = stack[:len(stack)-1]
			}
		case ".":
			// skip current directory
		default:
			stack = append(stack, part)
		}
	}

	return "/" + strings.Join(stack, "/")
}

static string SimplifyPath(string path)
{
    var stack = new List<string>();

    foreach (var part in path.Split('/'))
    {
        if (part == "..")
        {
            if (stack.Count > 0)
            {
                stack.RemoveAt(stack.Count - 1);
            }
        }
        else if (part.Length > 0 && part != ".")
        {
            stack.Add(part);
        }
    }

    return "/" + string.Join('/', stack);
}

def simplify_path(path: str) -> str:
    stack: list[str] = []

    for part in path.split("/"):
        if part == "..":
            if stack:
                stack.pop()
        elif part not in ("", "."):
            stack.append(part)

    return "/" + "/".join(stack)

## Задача 5: Декодирование строки

function decodeString(string $s): string
{
    $stack = [];
    $currentString = '';
    $currentNum = 0;

    for ($i = 0; $i < strlen($s); $i++) {
        $char = $s[$i];

        if (ctype_digit($char)) {
            $currentNum = $currentNum * 10 + (int) $char;
        } elseif ($char === '[') {
            $stack[] = [$currentString, $currentNum];
            $currentString = '';
            $currentNum = 0;
        } elseif ($char === ']') {
            [$prevString, $num] = array_pop($stack);
            $currentString = $prevString . str_repeat($currentString, $num);
        } else {
            $currentString .= $char;
        }
    }

    return $currentString;
}

import "strings"

type stackFrame struct {
	str string
	num int
}

func decodeString(s string) string {
	stack := []stackFrame{}
	currentStr := ""
	currentNum := 0

	for _, ch := range s {
		switch {
		case ch >= '0' && ch <= '9':
			currentNum = currentNum*10 + int(ch-'0')
		case ch == '[':
			stack = append(stack, stackFrame{currentStr, currentNum})
			currentStr = ""
			currentNum = 0
		case ch == ']':
			frame := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			currentStr = frame.str + strings.Repeat(currentStr, frame.num)
		default:
			currentStr += string(ch)
		}
	}

	return currentStr
}

using System.Text;

static string DecodeString(string s)
{
    var stack = new Stack<(string Str, int Num)>();
    var currentString = new StringBuilder();
    var currentNum = 0;

    foreach (var ch in s)
    {
        switch (ch)
        {
            case >= '0' and <= '9':
                currentNum = currentNum * 10 + (ch - '0');
                break;
            case '[':
                stack.Push((currentString.ToString(), currentNum));
                currentString.Clear();
                currentNum = 0;
                break;
            case ']':
            {
                var (prevString, num) = stack.Pop();
                var inner = currentString.ToString();
                currentString.Clear().Append(prevString);
                for (var i = 0; i < num; i++)
                {
                    currentString.Append(inner);
                }
                break;
            }
            default:
                currentString.Append(ch);
                break;
        }
    }

    return currentString.ToString();
}

def decode_string(s: str) -> str:
    stack: list[tuple[str, int]] = []
    current_string = ""
    current_num = 0

    for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)
        elif char == "[":
            stack.append((current_string, current_num))
            current_string = ""
            current_num = 0
        elif char == "]":
            prev_string, num = stack.pop()
            current_string = prev_string + current_string * num
        else:
            current_string += char

    return current_string

## Где используется стек

Вызов функций — стек вызовов (call stack)
Undo/Redo — в текстовых редакторах
Навигация — кнопки Назад/Вперёд в браузере
Парсинг выражений — компиляторы, калькуляторы
DFS — обход графов (итеративная реализация)
Backtracking — перебор с откатом

Запомни: Стек — это просто, но мощно. Если задача связана с вложенностью (скобки, HTML-теги, рекурсивные структуры) или с последовательной обработкой с возможностью отката — думай о стеке.

Итоги

LIFO: последний пришёл — первый ушёл
Все операции O(1)
Валидные скобки — каноническая задача на стек
Min Stack: параллельный стек минимумов
RPN, декодирование строк, упрощение путей — всё через стек

Стек (Stack)

Что такое стек?

Операции стека

Реализация

Задача 2: Min Stack

Итоги

Проверь себя

Code Challenges

Проверка скобок

Связанные темы