Стек
В этой статье вы узнаете, что такое стек и как его реализовать в Python, Java и C/C++.
Стек — полезная структура данных. Она похожа на стопку тарелок, сложенных друг на друга.
Что можно сделать со стопкой тарелок?
- Положить сверху еще одну тарелку.
- Убрать верхнюю тарелку.
Если вы хотите взять нижнюю тарелку, то придется убрать все тарелки над ней. Этот принцип называется LIFO — Last In First Out («последним пришёл — первым ушёл»).
LIFO — принцип стека
Для стека доступны две операции — push и pop. push — помещение элемента в начало стека, pop — удаление.
Как видите, хоть элемент 3 и был добавлен последним, но удаляется он самым первым — так работает принцип LIFO.
Реализовать стек можно в любом языке — С, С++, Java, Python или C#. Во всех языках стеки очень похожи.
Базовые операции со стеком
Стек — объект (абстрактный тип данных), он поддерживает следующие операции:
Push— позволяет «протолкнуть» элемент в начало стека.Pop— позволяет удалить элемент из начала стека.IsEmpty— проверяет, пуст ли стек.IsFull— проверяет, заполнен ли стек.Peek— позволяет получить элемент в начале стека без его удаления.
Как работает стек
Стек работает следующим образом:
- Указатель TOP используется для отслеживания «верхнего» элемента стека.
- После инициализации стека его значение равно -1. Так можно легко проверить заполненность стека: если TOP == -1, стек пуст.
- Когда мы «проталкиваем» элемент, значение TOP увеличивается на единицу. Следующий элемент будет находиться на позиции TOP+1.
- Когда мы используем метод
pop, мы удаляем элемент, на который указывает TOP. После этого его значение уменьшается на единицу. - Перед добавлением нового элемента мы проверяем, не заполнен ли стек.
- Перед удалением мы проверяем, не пуст ли стек.
Реализация стека
Наиболее распространенная реализация стека — массив. Но можно использовать и списки.
Python
# Реализация стека в python
# Создаем стек
def create_stack():
stack = []
return stack
# Создаем пустой стек
def check_empty(stack):
return len(stack) == 0
# Добавляем элементы в стек
def push(stack, item):
stack.append(item)
print("Добавлен элемент: " + item)
# Удаляем элементы из стека
def pop(stack):
if (check_empty(stack)):
return "Стек пуст"
return stack.pop()
stack = create_stack()
push(stack, str(1))
push(stack, str(2))
push(stack, str(3))
push(stack, str(4))
print("Удаленный элемент: " + pop(stack))
print("Стек после добавления элемента: " + str(stack))Java
// Реализация стека в Java
class Stack {
private int arr[];
private int top;
private int capacity;
// Создаем стек
Stack(int size) {
arr = new int[size];
capacity = size;
top = -1;
}
// Добавляем элементы в стек
public void push(int x) {
if (isFull()) {
System.out.println("Переполнение\nПрограмма остановлена\n");
System.exit(1);
}
System.out.println("Добавлен элемент " + x);
arr[++top] = x;
}
// Удаляем элементы из стека
public int pop() {
if (isEmpty()) {
System.out.println("Стек пуст");
System.exit(1);
}
return arr[top--];
}
// Функция возвращает размер стека
public int size() {
return top + 1;
}
// Проверяем, пуст ли стек
public Boolean isEmpty() {
return top == -1;
}
// Проверяем, не заполнен ли стек
public Boolean isFull() {
return top == capacity - 1;
}
public void printStack() {
for (int i = 0; i <= top; i++) {
System.out.println(arr[i]);
}
}
public static void main(String[] args) {
Stack stack = new Stack(5);
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.pop();
System.out.println("\nПосле удаления");
stack.printStack();
}
}С
// Реализация стека в C
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
int count = 0;
// Создаем стек
struct stack {
int items[MAX];
int top;
};
typedef struct stack st;
void createEmptyStack(st *s) {
s->top = -1;
}
// Проверяем, не заполнен ли стек
int isfull(st *s) {
if (s->top == MAX - 1)
return 1;
else
return 0;
}
// Проверяем, не пуст ли стек
int isempty(st *s) {
if (s->top == -1)
return 1;
else
return 0;
}
// Добавляем элементы в стек
void push(st *s, int newitem) {
if (isfull(s)) {
printf("Стек заполнен");
} else {
s->top++;
s->items[s->top] = newitem;
}
count++;
}
// Удаляем элементы из стека
void pop(st *s) {
if (isempty(s)) {
printf("\n Стек пуст \n");
} else {
printf("Удален элемент= %d", s->items[s->top]);
s->top--;
}
count--;
printf("\n");
}
// Выводим в консоль элементы стека
void printStack(st *s) {
printf("Стек: ");
for (int i = 0; i < count; i++) {
printf("%d ", s->items[i]);
}
printf("\n");
}
// Функция main
int main() {
int ch;
st *s = (st *)malloc(sizeof(st));
createEmptyStack(s);
push(s, 1);
push(s, 2);
push(s, 3);
push(s, 4);
printStack(s);
pop(s);
printf("\nПосле удаления\n");
printStack(s);
}C++
// Реализация стека в C++
#include <stdlib.h>
#include <iostream>
using namespace std;
#define MAX 10
int size = 0;
// Создаем стек
struct stack {
int items[MAX];
int top;
};
typedef struct stack st;
void createEmptyStack(st *s) {
s->top = -1;
}
// Проверяем, не заполнен ли стек
int isfull(st *s) {
if (s->top == MAX - 1)
return 1;
else
return 0;
}
// Проверяем, не пуст ли стек
int isempty(st *s) {
if (s->top == -1)
return 1;
else
return 0;
}
// Добавляем элемент в стек
void push(st *s, int newitem) {
if (isfull(s)) {
printf("Стек заполнен");
} else {
s->top++;
s->items[s->top] = newitem;
}
size++;
}
// Удаляем элемент из стека
void pop(st *s) {
if (isempty(s)) {
printf("\n Стек пуст \n");
} else {
printf("Удален элемент= %d", s->items[s->top]);
s->top--;
}
size--;
cout << endl;
}
// Выводим в консоль элементы стека
void printStack(st *s) {
printf("Стек: ");
for (int i = 0; i < size; i++) {
cout << s->items[i] << " ";
}
cout << endl;
}
// Функция main
int main() {
int ch;
st *s = (st *)malloc(sizeof(st));
createEmptyStack(s);
push(s, 1);
push(s, 2);
push(s, 3);
push(s, 4);
printStack(s);
pop(s);
cout << "\nПосле удаления\n";
printStack(s);
}Временная сложность стека
У стеков, реализованных с помощью массива, скорость выполнения операций pop и push одинакова и равна O(1).
Где применяются стеки
- Поворот слова задом-наперед. Поместите все буквы в стек и верните их — благодаря LIFO слово «отзеркалится».
- В компиляторах. Компиляторы используют стеки для вычисления выражений вроде 2 + 4 / 5 * (7 - 9). Происходит это благодаря его конвертации в префиксную и постфиксную форму.
- В браузерах. Кнопка «Назад» хранит в стеке все URL-адреса, которые вы посещали. Каждый раз, когда вы посещаете новую страницу, ее URL-адрес оказывается на «вершине» стека. После нажатия на кнопку «Назад» текущий URL-адрес удаляется из стека, и браузер получает доступ к предыдущему.
