Стек: что это?

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

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

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

class Stack:
    def __init__(self):
        self.stack = []
    
    def is_empty(self):
        return len(self.stack) == 0
    
    def push(self, element):
        self.stack.append(element)
    
    def pop(self):
        if self.is_empty():
            return None
        return self.stack.pop()
    
    def peek(self):
        if self.is_empty():
            return None
        return self.stack[-1]
    
    def size(self):
        return len(self.stack)

# Пример использования стека
my_stack = Stack()
my_stack.push(5)
my_stack.push(3)
my_stack.push(8)
print(my_stack.size())  # Выводит 3
print(my_stack.pop())  # Выводит 8
print(my_stack.peek())  # Выводит 3
print(my_stack.is_empty())  # Выводит False

В приведенном примере класс Stack содержит методы для работы со стеком. Метод push добавляет элемент на вершину стека, метод pop извлекает элемент с вершины, метод peek возвращает элемент, находящийся на вершине, но не удаляет его, а метод is_empty проверяет, пуст ли стек. Также в класс включен метод size, который возвращает текущий размер стека.

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

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

public class Stack {
    private Node top;
    private int size;
    
    public Stack() {
        this.top = null;
        this.size = 0;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public void push(int data) {
        Node newNode = new Node(data);
        newNode.next = top;
        top = newNode;
        size++;
    }
    
    public int pop() {
        if (isEmpty()) {
            return -1;
        }
        int data = top.data;
        top = top.next;
        size--;
        return data;
    }
    
    public int peek() {
        if (isEmpty()) {
            return -1;
        }
        return top.data;
    }
    
    public int size() {
        return size;
    }
    
    // Внутренний класс для представления узла связного списка
    private class Node {
        private int data;
        private Node next;
        
        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
}

// Пример использования стека
Stack myStack = new Stack();
myStack.push(5);
myStack.push(3);
myStack.push(8);
System.out.println(myStack.size());  // Выводит 3
System.out.println(myStack.pop());  // Выводит 8
System.out.println(myStack.peek());  // Выводит 3
System.out.println(myStack.isEmpty());  // Выводит false

В данном примере класс Stack реализован в виде внутреннего класса внутри класса-контейнера. Данные стека хранятся в объектах типа Node, которые содержат информацию и ссылку на следующий узел. Методы push, pop, peek, isEmpty и size служат для работы со стеком.

В обоих примерах демонстрируется работа со стеком с использованием приведенных реализаций на языках Python и Java. Однако стек может быть реализован и на других языках программирования с использованием разных структур данных. Важно понимать принципиальное отличие стека от других структур данных и применять его в соответствии с задачами, где LIFO-подход является оптимальным решением.