В этом уроке ты
- Узнаешь, почему не всегда удобно использовать стек.
- Научишься заменять стек на более удобные структуры данных.
Недостатки использования стека
Стек — удобная структура данных, но бывают случаи, когда его применение становится неудобным или избыточным.
Из стека в массив
Иногда задача требует вернуть ответ в виде массива, но все необходимые элементы уже находятся в стеке. В этом случае приходится перекладывать элементы из стека в массив:
// В языке JavaScript нет встроенного стека, но полезно знать,
// что такая проблема встречается в других языках
export function arrayFromStack(stack) {
// Создаём массив нужного размера
const result = new Array(stack.length);
const tempStack = [...stack];
// Заполняем массив с конца, так как
// доступ в стеке только к последнему элементу
for (let i = stack.length - 1; i >= 0; i--) {
result[i] = tempStack.pop();
}
return result;
}#include <iostream>
#include <stack>
#include <vector>
using namespace std;
vector<int> arrayFromStack(stack<int> st) {
// Создаём массив нужного размера
vector<int> result(st.size());
// Заполняем массив с конца, так как
// доступ в стеке только к последнему элементу
for (int i = st.size() - 1; i >= 0; i--) {
result[i] = st.top();
st.pop();
}
return result;
}package main
import "fmt"
// В языке Go напрямую стек не используется, но полезно знать,
// что такая проблема встречается в других языках
func arrayFromStack(stack []int) []int {
// Создаём массив нужного размера
result := make([]int, len(stack))
tempStack := make([]int, len(stack))
copy(tempStack, stack)
// Заполняем массив с конца, так как
// доступ в стеке только к последнему элементу
for i := len(tempStack) - 1; i >= 0; i-- {
result[i] = tempStack[len(tempStack)-1]
tempStack = tempStack[:len(tempStack)-1]
}
return result
}import java.util.Stack;
public class Solution {
public static int[] arrayFromStack(Stack<Integer> stack) {
// Создаём массив нужного размера
int[] result = new int[stack.size()];
Stack<Integer> tempStack = (Stack<Integer>) stack.clone();
// Заполняем массив с конца, так как
// доступ в стеке только к последнему элементу
for (int i = stack.size() - 1; i >= 0; i--) {
result[i] = tempStack.pop();
}
return result;
}
}# В Python напрямую стек не используется, но полезно знать,
# что такая проблема встречается в других языках
from typing import List
def array_from_stack(stack) -> List[int]:
# Создаём массив нужного размера
result = [0] * len(stack)
# Заполняем массив с конца, так как
# доступ в стеке только к последнему элементу
for i in reversed(range(len(stack))):
result[i] = stack.pop()
return result// В языке JavaScript нет встроенного стека, но полезно знать,
// что такая проблема встречается в других языках
export function arrayFromStack(stack) {
// Создаём массив нужного размера
const result = new Array(stack.length);
const tempStack = [...stack];
// Заполняем массив с конца, так как
// доступ в стеке только к последнему элементу
for (let i = stack.length - 1; i >= 0; i--) {
result[i] = tempStack.pop();
}
return result;
}Проблема не критичная, но неприятная. Возможно, интервьюер предложит тебе упростить такой код и сделать его более компактным.
Нужны последние N значений
Иногда для принятия решения нужно проверить не один последний элемент, а несколько последних элементов стека. В таком случае приходится извлекать несколько элементов подряд и возвращать их обратно, если условие не выполняется:
// Нужно проверить три последних элемента, и только затем удалять их из стека
int third = stack.Pop();
int second = stack.Pop();
int first = stack.Pop();
if (!(curr == first && curr == second && curr == third))
{
// Возвращаем элементы обратно, если условие не выполнилось
stack.Push(first);
stack.Push(second);
stack.Push(third);
}using namespace std;
// Нужно проверить три последних элемента, и только затем удалять их из стека
int third = stack.top();
stack.pop();
int second = stack.top();
stack.pop();
int first = stack.top();
stack.pop();
if (!(curr == first && curr == second && curr == third)) {
// Возвращаем элементы обратно, если условие не выполнилось
stack.push(first);
stack.push(second);
stack.push(third);
}// Нужно проверить три последних элемента, и только затем удалять их из стека
third := stack[len(stack)-1]
stack = stack[:len(stack)-1]
second := stack[len(stack)-1]
stack = stack[:len(stack)-1]
first := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if !(curr == first && curr == second && curr == third) {
// Возвращаем элементы обратно, если условие не выполнилось
stack = append(stack, first)
stack = append(stack, second)
stack = append(stack, third)
}// Нужно проверить три последних элемента, и только затем удалять их из стека
int third = stack.pop();
int second = stack.pop();
int first = stack.pop();
if (!(curr == first && curr == second && curr == third)) {
// Возвращаем элементы обратно, если условие не выполнилось
stack.push(first);
stack.push(second);
stack.push(third);
}# Нужно проверить три последних элемента, и только затем удалять их из стека
third = stack.pop()
second = stack.pop()
first = stack.pop()
if not (curr == first and curr == second and curr == third):
# Возвращаем элементы обратно, если условие не выполнилось
stack.push(first)
stack.push(second)
stack.push(third)// Нужно проверить три последних элемента, и только затем удалять их из стека
const third = stack.pop();
const second = stack.pop();
const first = stack.pop();
if (!(curr === first && curr === second && curr === third)) {
// Возвращаем элементы обратно, если условие не выполнилось
stack.push(first);
stack.push(second);
stack.push(third);
}Такой подход увеличивает количество кода и создаёт риск запутаться.
Чем можно заменить стек
Стек можно заменить на следующие структуры данных:
- Дек (deque)
- Динамический массив
Дек является хорошей альтернативой, особенно когда нужно проверять несколько последних значений без их удаления. Однако если ответ нужно возвращать в виде массива, всё равно потребуется дополнительное преобразование.
Наиболее универсальным решением является использование динамического массива, так как он:
- Позволяет удобно возвращать результат сразу в виде массива.
- Позволяет легко проверить последние N значений без их удаления:
// Проверяем элементы до удаления, избегая лишних операций
if (stack.Count >= 3 &&
curr == stack.Peek() &&
curr == stack.ElementAt(stack.Count - 2) &&
curr == stack.ElementAt(stack.Count - 3)) {
stack.Pop();
stack.Pop();
stack.Pop();
}using namespace std;
// Проверяем элементы до удаления, избегая лишних операций
if (stack.size() >= 3 &&
curr == stack.top() &&
curr == *(stack.end() - 2) &&
curr == *(stack.end() - 3)) {
stack.pop();
stack.pop();
stack.pop();
}// Проверяем элементы до удаления, избегая лишних операций
if len(stack) >= 3 && curr == stack[len(stack)-1] && curr == stack[len(stack)-2] && curr == stack[len(stack)-3] {
stack = stack[:len(stack)-3]
}// Проверяем элементы до удаления, избегая лишних операций
if (stack.size() >= 3 &&
curr == stack.peek() &&
curr == stack.get(stack.size() - 2) &&
curr == stack.get(stack.size() - 3)) {
stack.pop();
stack.pop();
stack.pop();
}# Проверяем элементы до удаления, избегая лишних операций
if curr == stack[-1] and curr == stack[-2] and curr == stack[-3]:
stack.pop()
stack.pop()
stack.pop()// Проверяем элементы до удаления, избегая лишних операций
if (stack.length >= 3 &&
curr === stack[stack.length - 1] &&
curr === stack[stack.length - 2] &&
curr === stack[stack.length - 3]) {
stack.pop();
stack.pop();
stack.pop();
}Кратко о главном
Вместо стека удобно использовать динамический массив, так как он решает большинство проблем, связанных с извлечением элементов.
Что дальше
Теперь скорее переходи к задачам, чтобы закрепить полученные знания на практике!