Стеки — это важная структура данных, которая следует принципу «последним пришел — первым вышел» (LIFO). Они предлагают простой, но мощный способ управления данными, что делает их бесценными во многих сценариях программирования. В этой статье мы рассмотрим реализацию стеков в коде с использованием разных языков программирования и обсудим задействованные ключевые операции.
Реализация стека на основе массивов
Одним из наиболее распространенных способов реализации стека является использование массива. Давайте посмотрим, как мы можем реализовать стек на основе массива в коде.
питон
class ArrayStack: def __init__(self): self.stack = [] 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 is_empty(self): return len(self.stack) == 0 def size(self): return len(self.stack)
В этой реализации Python мы определяем класс ArrayStack, который использует список Python для хранения элементов. Метод push добавляет элемент в конец списка, представляющий вершину стека. Метод pop удаляет и возвращает верхний элемент, а метод peek извлекает верхний элемент, не удаляя его. Метод is_empty проверяет, пуст ли стек, а метод size возвращает количество элементов в стеке.
C++
#include <iostream> #define MAX_SIZE 100 class Stack { private: int top; int stack[MAX_SIZE]; public: Stack() { top = -1; } bool isEmpty() { return (top == -1); } bool isFull() { return (top == MAX_SIZE - 1); } void push(int element) { if (isFull()) { std::cout << "Stack Overflow: Cannot push element, stack is full." << std::endl; return; } stack[++top] = element; } int pop() { if (isEmpty()) { std::cout << "Stack Underflow: Cannot pop element, stack is empty." << std::endl; return -1; } return stack[top--]; } int peek() { if (isEmpty()) { std::cout << "Stack is empty." << std::endl; return -1; } return stack[top]; } int size() { return top + 1; } }; int main() { Stack stack; stack.push(10); stack.push(20); stack.push(30); std::cout << "Stack size: " << stack.size() << std::endl; std::cout << "Top element: " << stack.peek() << std::endl; while (!stack.isEmpty()) { std::cout << "Popped element: " << stack.pop() << std::endl; } std::cout << "Stack size: " << stack.size() << std::endl; return 0; }
В этой реализации C++ мы определяем класс Stack
с частными переменными-членами top
(для отслеживания индекса верхнего элемента) и stack
(массив для хранения элементов). Методы isEmpty()
и isFull()
проверяют, пуст или полон стек соответственно. Функция push()
вставляет элемент на вершину стека, а pop()
удаляет и возвращает верхний элемент. Метод peek()
извлекает верхний элемент, не удаляя его. Функция size()
возвращает количество элементов в стеке.
В функции main()
мы демонстрируем использование стека, помещая в стек три элемента, печатая размер стека и верхний элемент, а затем извлекая все элементы из стека.
Реализация стека на основе связанного списка
Другой популярный подход к реализации стека — использование связанного списка. Давайте посмотрим, как мы можем реализовать стек на основе связанных списков в коде.
питон
class Node: def __init__(self, value): self.value = value self.next = None class LinkedListStack: def __init__(self): self.top = None def push(self, element): new_node = Node(element) new_node.next = self.top self.top = new_node def pop(self): if self.is_empty(): return None popped_value = self.top.value self.top = self.top.next return popped_value def peek(self): if self.is_empty(): return None return self.top.value def is_empty(self): return self.top is None def size(self): count = 0 current = self.top while current: count += 1 current = current.next return countIn this Python implementation, we create a `Node` class to represent each element in the stack. The `LinkedListStack` class maintains a reference to the top node of the stack. The `push` method creates a new node with the given element and updates the references accordingly. The `pop` method removes and returns the value of the top node, while the `peek` method retrieves the value without removing it. The `is_empty` method checks if the stack is empty, and the `size` method iterates through the linked list to count the number of elements.
В этой реализации Python мы создаем класс Node
для представления каждого элемента в стеке. Класс LinkedListStack
поддерживает ссылку на верхний узел стека. Метод push
создает новый узел с заданным элементом и соответствующим образом обновляет ссылки. Метод pop
удаляет и возвращает значение верхнего узла, а метод peek
извлекает значение, не удаляя его. Метод is_empty
проверяет, пуст ли стек, а метод size
выполняет итерацию по связанному списку, чтобы подсчитать количество элементов.
C++
#include <iostream> class Node { public: int data; Node* next; Node(int value) { data = value; next = nullptr; } }; class Stack { private: Node* top; public: Stack() { top = nullptr; } bool isEmpty() { return (top == nullptr); } void push(int element) { Node* newNode = new Node(element); newNode->next = top; top = newNode; } int pop() { if (isEmpty()) { std::cout << "Stack Underflow: Cannot pop element, stack is empty." << std::endl; return -1; } Node* temp = top; int poppedValue = temp->data; top = top->next; delete temp; return poppedValue; } int peek() { if (isEmpty()) { std::cout << "Stack is empty." << std::endl; return -1; } return top->data; } int size() { int count = 0; Node* current = top; while (current != nullptr) { count++; current = current->next; } return count; } }; int main() { Stack stack; stack.push(10); stack.push(20); stack.push(30); std::cout << "Stack size: " << stack.size() << std::endl; std::cout << "Top element: " << stack.peek() << std::endl; while (!stack.isEmpty()) { std::cout << "Popped element: " << stack.pop() << std::endl; } std::cout << "Stack size: " << stack.size() << std::endl; return 0; }
В этой реализации C++ мы определяем класс Node
для представления каждого элемента в стеке. Каждый узел содержит поле data
для хранения значения и указатель next
для указания на следующий узел в стеке.
Класс Stack
имеет закрытую переменную-член top
, указывающую на верхний узел стека. Метод isEmpty()
проверяет, пуст ли стек. Функция push()
создает новый узел с заданным элементом, связывает его с текущим верхним узлом и обновляет указатель top
. Метод pop()
удаляет и возвращает значение верхнего узла, соответствующим образом обновляя указатель top
и освобождая память. Метод peek()
извлекает значение верхнего узла, не удаляя его. Функция size()
перебирает связанный список, чтобы подсчитать количество элементов.
В функции main()
мы демонстрируем использование стека, помещая в стек три элемента, печатая размер стека и верхний элемент, а затем извлекая все элементы из стека.
Выбор реализации
Выбор между реализацией на основе массива или на основе связанного списка зависит от различных факторов. Стеки на основе массивов обеспечивают постоянную временную сложность для доступа к элементам, что делает их предпочтительными, когда необходим прямой доступ к элементам. С другой стороны, стеки на основе связанных списков обеспечивают гибкость при обработке динамического количества элементов.
Заключение
Реализация стеков в коде имеет решающее значение для управления данными по принципу «последним пришел – первым обслужен». Используя реализацию на основе массива или связанного списка, программисты могут воспользоваться преимуществами простоты и эффективности стека. Решите ли вы реализовать стек с использованием связанного списка или массива, зависит от целей, которых вы хотите достичь. Если вы хотите ускорить время доступа, используйте массив, если вы хотите, чтобы стек не имел ограничений по размеру, используйте связанный список.