В информатике стек — это абстрактный тип данных, который соответствует принципу «последним пришел — первым обслужен» (LIFO). Это позволяет эффективно хранить и извлекать элементы данных. Стеки находят применение в различных реальных сценариях: от управления вызовами функций до анализа выражений. В этой статье мы рассмотрим различные методы использования стеков, приведя примеры кода для каждого варианта использования.
- Стек вызовов функций.
Одним из наиболее распространенных применений стека является управление вызовами функций. Каждый раз, когда вызывается функция, ее адрес возврата и локальные переменные помещаются в стек. Когда функция завершается, стек извлекает адрес возврата, позволяя программе возобновить выполнение с точки вызова. Вот пример на Python:
def function_a():
print("Function A")
function_b()
def function_b():
print("Function B")
function_a()- Сбалансированные круглые скобки.
Стеки можно использовать для проверки сбалансированности строки круглых скобок. Это классическая задача информатики. Идея состоит в том, чтобы поместить открывающую скобку в стек и вытолкнуть ее при обнаружении закрывающей скобки. Если стек в конце пуст и все круглые скобки совпадают, строка считается сбалансированной. Вот пример на Java:
import java.util.Stack;
public class BalancedParentheses {
public static boolean isBalanced(String str) {
Stack<Character> stack = new Stack<>();
for (char c : str.toCharArray()) {
if (c == '(')
stack.push(c);
else if (c == ')') {
if (stack.isEmpty())
return false;
stack.pop();
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
String str = "((())())";
System.out.println(isBalanced(str)); // Output: true
}
}- История веб-браузера.
Стек можно использовать для реализации функции кнопки «Назад» в веб-браузерах. Каждый раз, когда пользователь посещает новую страницу, ее URL-адрес помещается в стек. При нажатии кнопки «Назад» стек отображает верхний URL-адрес, позволяя пользователю перейти на предыдущую страницу. Вот пример использования JavaScript:
class BrowserHistory {
constructor() {
this.stack = [];
}
visit(url) {
this.stack.push(url);
}
back() {
if (this.stack.length > 1) {
this.stack.pop();
}
}
getCurrentPage() {
return this.stack[this.stack.length - 1];
}
}
const browser = new BrowserHistory();
browser.visit("https://example.com");
browser.visit("https://google.com");
console.log(browser.getCurrentPage()); // Output: https://google.com
browser.back();
console.log(browser.getCurrentPage()); // Output: https://example.com- Функциональность отмены/повтора.
Стеки можно использовать для реализации функций отмены и повтора в текстовых редакторах или программах графического дизайна. Каждое изменение, внесенное пользователем, помещается в стек. Когда срабатывает команда отмены, стек извлекает последнее изменение, возвращая состояние. Redo работает путем помещения отмененных изменений обратно в стек. Вот упрощенный пример на C++:
#include <iostream>
#include <stack>
class TextEditor {
public:
void insertText(const std::string& text) {
textStack.push(text);
std::cout << "Inserted: " << text << std::endl;
}
void undo() {
if (!textStack.empty()) {
std::string undoneText = textStack.top();
textStack.pop();
std::cout << "Undone: " << undoneText << std::endl;
}
}
private:
std::stack<std::string> textStack;
};
int main() {
TextEditor editor;
editor.insertText("Hello");
editor.insertText("World");
editor.undo(); // Output: Undone: World
editor.undo(); // Output: Undone: Hello
return 0;
}Стеки предоставляют мощный инструмент для управления данными в различных реальных сценариях. Стеки универсальны и эффективны: от управления вызовами функций до анализа выражений, проверки сбалансированных круглых скобок и истории веб-браузера, а также функций отмены и повтора. Понимая и используя стеки, разработчики могут повысить функциональность и производительность своих приложений.