Что такое стек? Каковы его основные операции?

Стек — это структура данных, работающая по принципу LIFO. LIFO означает: То есть элемент, добавленный последним, извлекается первым.

Стек — это структура данных, работающая по принципу LIFO.

LIFO означает:

Last In — First Out

То есть элемент, добавленный последним, извлекается первым.

Пример из жизни — стопка тарелок. Последнюю поставленную тарелку удобнее всего взять первой.

Как работает стек?

Представим стек:

верх → 30
       20
       10

Если добавить число 40, оно попадет наверх:

верх → 40
       30
       20
       10

Если извлечь элемент, будет удален верхний элемент 40.

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

1. Push

Push — добавление элемента на вершину стека.

const stack = [];

stack.push(10);
stack.push(20);
stack.push(30);

const stack: number[] = [];

stack.push(10);
stack.push(20);
stack.push(30);

package main
func main() {
  stack := []int{}

  stack = append(stack, 10)
  stack = append(stack, 20)
  stack = append(stack, 30)
}

public class Example {
  public static void main(String[] args) {
    var stack = new java.util.ArrayList<Integer>();

    stack.add(10);
    stack.add(20);
    stack.add(30);
  }
}

stack = []

stack.append(10)
stack.append(20)
stack.append(30)

---

2. Pop

Pop — удаление и возврат верхнего элемента стека.

const last = stack.pop(); // 30

const last = stack.pop(); // 30

package main
func main() {
  last := stack[len(stack)-1] // 30
}

public class Example {
  public static void main(String[] args) {
    var last = stack.remove(stack.size() - 1); // 30
  }
}

last = stack.pop() # 30

---

3. Peek / Top

Peek или Top — просмотр верхнего элемента без удаления.

const top = stack.at(-1);

const top = stack.at(-1);

package main
func main() {
  top := stack[len(stack)-1]
}

public class Example {
  public static void main(String[] args) {
    var top = stack.get(stack.size() - 1);
  }
}

top = stack[-1]

---

4. IsEmpty

Проверка, пуст ли стек.

const isEmpty = stack.length === 0;

const isEmpty = stack.length === 0;

package main
func main() {
  isEmpty := len(stack) == 0
}

public class Example {
  public static void main(String[] args) {
    var isEmpty = stack.length() == 0;
  }
}

isEmpty = len(stack) == 0

---

5. Size

Получение количества элементов.

const size = stack.length;

const size = stack.length;

package main
func main() {
  size := len(stack)
}

public class Example {
  public static void main(String[] args) {
    var size = stack.length();
  }
}

size = len(stack)

Ошибки при работе со стеком

Переполнение стека

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

Извлечение из пустого стека

Возникает, если программа пытается выполнить pop, когда стек пуст.

Где применяется стек?

Стек используется:

• при вызове функций;
• при хранении адресов возврата;
• при обработке рекурсии;
• при отмене действий;
• при проверке скобочных выражений;
• при вычислении выражений;
• в алгоритмах обхода графов;
• в парсерах и компиляторах.

Например, когда одна функция вызывает другую, информация о вызовах хранится в стеке вызовов.

function first() {
  second();
}

function second() {
  console.log('Вторая функция');
}

first();

function first(): void {
  second();
}

function second(): void {
  console.log('Вторая функция');
}

first();

package main
import "fmt"
func first() {
  second()
}

func second() {
  fmt.Println("Вторая функция")
}

func main() {
  first()
}

public class Example {
  static void first() {
    second();
  }

  static void second() {
    System.out.println("Вторая функция");
  }

  public static void main(String[] args) {
    first();
  }
}

def first():
  second()

def second():
  print('Вторая функция')

first()

Сначала в стек вызовов помещается first, затем second. Когда second завершится, управление вернется к first.

Вывод

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