Эта серия представляет собой краткое изложение структур данных и алгоритмов, когда я искал работу много лет назад. Здесь есть базовые части и классические вопросы для интервью от крупных компаний. Впервые опубликовано на CSDN. Теперь он организован в серию для справки друзей, которым это нужно.Если есть какая-либо ошибка, пожалуйста, поправьте меня. Полный кодовый адрес этой серии находится по адресуздесь.
0 Обзор
В качестве базовой структуры данных стек используется во многих местах, таких как рекурсия функций, преобразование префиксных и суффиксных выражений и т. д. В этой статье массивы C будут использоваться для реализации структуры стека (об использовании связанных списков см. в разделе, посвященном связанным спискам, и использовании метода вставки заголовков для построения связанных списков), а также проанализированы несколько распространенных вопросов, связанных с интервью, связанных со стеком. в этой статье находится вздесь.
1 Определение
Мы используем структуры для определения стеков и гибких массивов для хранения элементов. Несколько определений макросов используются для вычисления количества элементов в стеке и определения того, является ли стек пустым или полным.
typedef struct Stack {
int capacity;
int top;
int items[];
} Stack;
#define SIZE(stack) (stack->top + 1)
#define IS_EMPTY(stack) (stack->top == -1)
#define IS_FULL(stack) (stack->top == stack->capacity - 1)
2 Основные операции
В стеке есть три основные операции:
- push: Поместить элемент в стек.
- pop: извлечь верхний элемент стека и вернуться.
- peek: Получить верхний элемент стека, но не изменять стек.
как показано на рисунке:
код показывает, как показано ниже:
Stack *stackNew(int capacity)
{
Stack *stack = (Stack *)malloc(sizeof(*stack) + sizeof(int) * capacity);
if (!stack) {
printf("Stack new failed\n");
exit(E_NOMEM);
}
stack->capacity = capacity;
stack->top = -1;
return stack;
}
void push(Stack *stack, int v)
{
if (IS_FULL(stack)) {
printf("Stack Overflow\n");
exit(E_FULL);
}
stack->items[++stack->top] = v;
}
int pop(Stack *stack)
{
if (IS_EMPTY(stack)) {
printf("Stack Empty\n");
exit(E_EMPTY);
}
return stack->items[stack->top--];
}
int peek(Stack *stack)
{
if (IS_EMPTY(stack)) {
printf("Stack Empty\n");
exit(E_EMPTY);
}
return stack->items[stack->top];
}
3 вопроса на собеседовании, связанные со стеком
3.1 Вычисление постфиксного выражения
вопрос:Постфиксное выражение известно6 5 2 3 + 8 * + 3 + *, оценивает постфиксное выражение.
развязать:Постфиксные выражения также называются обратными польскими выражениями, и процесс вычисления может использовать стек для облегчения хранения. Тогда процесс его оценки выглядит следующим образом:
- 1) Обходим выражение, и встречающиеся числа сначала помещаются в стек, в это время стек
[6 5 2 3]. - 2) Тогда читай
+, затем всплывают 3 и 2, вычисляют3 + 2, результат расчета равен5, и воля5Помещенный в стек, стек[6 5 5]. - 3) читать
8, положить его прямо в стек,[6 5 5 8]. - 4) читать
*,выскакивать8а также5,рассчитать8 * 5, и поставить результат40Помещенный в стек, стек[6 5 40]. Далее процесс аналогичен, читайте+,будет40а также5всплывает, будет40 + 5результат45нажать на стек, стек становится[6 45], прочитать 3, положить в стек[6 45 3]... и так далее, окончательный результат288.
Код:
int evaluatePostfix(char *exp)
{
Stack* stack = stackNew(strlen(exp));
int i;
if (!stack) {
printf("New stack failed\n");
exit(E_NOMEM);
}
for (i = 0; exp[i]; ++i) {
// 如果是数字，直接压栈
if (isdigit(exp[i])) {
push(stack, exp[i] - '0');
} else {// 如果遇到符号，则弹出栈顶两个元素计算，并将结果压栈
int val1 = pop(stack);
int val2 = pop(stack);
switch (exp[i])
{
case '+': push(stack, val2 + val1); break;
case '-': push(stack, val2 - val1); break;
case '*': push(stack, val2 * val1); break;
case '/': push(stack, val2/val1); break;
}
}
}
return pop(stack);
}
3.2 Обратный порядок стека
вопрос:Учитывая стек, измените его порядок.
Решение 1:Если вы не учитываете сложность пространства, вы можете получить еще один вспомогательный стек и хранить все исходные данные стека.popвыходи иpushво вспомогательный стек.
Решение 2:Если вы столкнетесь с этим вопросом в интервью, нужно надеяться, что вы справитесь с ним лучше. Вы можете сначала реализовать функцию, которая вставляет элементы в конец стека, а затем рекурсивно реализовать обратный порядок стека без использования вспомогательного стека.
* 在栈底插入一个元素
*/
void insertAtBottom(Stack *stack, int v)
{
if (IS_EMPTY(stack)) {
push(stack, v);
} else {
int x = pop(stack);
insertAtBottom(stack, v);
push(stack, x);
}
}
/**
* 栈逆序
*/
void stackReverse(Stack *stack)
{
if (IS_EMPTY(stack))
return;
int top = pop(stack);
stackReverse(stack);
insertAtBottom(stack, top);
}
3.3 Создайте стек, содержащий функцию min
вопрос:Дизайн стека, так что толкать, поп и мин (получение наименьшего элемента в стеке) можно сделать в постоянном времени.
анализировать:В начале легко придумать метод, заключающийся в дополнительном создании минимальной бинарной кучи для хранения всех элементов, чтобы каждый раз, когда вы получаете минимальный элемент, вам нужно было толькоO(1)время. Но в этом случае для построения минимальной кучиpushа такжеpopтребуется операцияO(lgn)Время истекло (при условии, что количество элементов в стеке равно n), что не соответствует требованиям заголовка.
Решение 1. Метод вспомогательного стека
Для достижения этой функции можно использовать вспомогательный стек для хранения наименьшего элемента.Это простое и элегантное решение. Пусть имя вспомогательного стека будетminStack, верхний элемент стека является наименьшим элементом в текущем стеке. это означает
- 1) Чтобы получить наименьший элемент в текущем стеке, просто верните верхний элемент minStack.
- 2) Каждый раз, когда выполняется операция проталкивания, проверяйте, является ли проталкиваемый элемент меньше или равен верхнему элементу стека minStack. Если это так, поместите этот элемент в minStack.
- 3) При выполнении операции извлечения проверьте, равен ли извлеченный элемент текущему минимальному значению. Если равно, элемент необходимо извлечь из minStack.
Код:
void minStackPush(Stack *orgStack, Stack *minStack, int v)
{
if (IS_FULL(orgStack)) {
printf("Stack Full\n");
exit(E_FULL);
}
push(orgStack, v);
if (IS_EMPTY(minStack) || v < peek(minStack)) {
push(minStack, v);
}
}
int minStackPop(Stack *orgStack, Stack *minStack)
{
if (IS_EMPTY(orgStack)) {
printf("Stack Empty\n");
exit(E_EMPTY);
}
if (peek(orgStack) == peek(minStack)) {
pop(minStack);
}
return pop(orgStack);
}
int minStackMin(Stack *minStack)
{
return peek(minStack);
}
Пример:
предполагается элемент3，4，2，5，1складывать по порядкуorgStack, вспомогательный стекminStackЭлемент3，2，1.
Решение 2: разностный метод
Другое решение — использовать сохраненную разницу без необходимости вспомогательного стека, и этот метод более умный:
- В верхней части стека есть дополнительное пространство для хранения минимального значения стека.
-
pushПри нажатии разница между текущим элементом и наименьшим элементом в стеке (элемент на вершине стека) до того, как элемент будет помещен в стек, а затем сравнение размера текущего элемента и наименьшего элемента в текущем стеке, и используйте меньшее значение в качестве нового минимального значения, помещаемого на вершину стека. -
popКогда функция выполняется, сначалаpopВставьте два значения в верхней части стека, которые являются минимальными значениями в текущем стеке.minи разница между последним выдвинутым элементом и минимальным значением в предыдущем стекеdelta. согласно сdelta < 0илиdelta >= 0чтобы получить значение ранее отправленного элемента и новое минимальное значение после извлечения элемента. -
minФункция состоит в том, чтобы взять верхний элемент стека.
Код:
void minStackPushUseDelta(Stack *stack, int v)
{
if (IS_EMPTY(stack)) { // 空栈，直接压入v两次
push(stack, v);
push(stack, v);
} else {
int oldMin = pop(stack); // 栈顶保存的是压入v之前的栈中最小值
int delta = v - oldMin;
int newMin = delta < 0 ? v : oldMin;
push(stack, delta); // 压入 v 与之前栈中的最小值之差
push(stack, newMin); // 最后压入当前栈中最小值
}
}
int minStackPopUseDelta(Stack *stack)
{
int min = pop(stack);
int delta = pop(stack);
int v, oldMin;
if (delta < 0) { // 最后压入的元素比min小，则min就是最后压入的元素
v = min;
oldMin = v - delta;
} else { // 最后压入的值不是最小值，则min为oldMin。
oldMin = min;
v = oldMin + delta;
}
if (!IS_EMPTY(stack)) { // 如果栈不为空，则压入oldMin
push(stack, oldMin);
}
return v;
}
int minStackMinUseDelta(Stack *stack)
{
return peek(stack);
}
Пример:
push(3): [3 3]
push(4): [3 1 3]
push(2): [3 1 -1 2]
push(5): [3 1 -1 3 2]
push(1): [3 1 -1 3 -1 1]
min(): 1，pop(): 1，[3 1 -1 3 2]
min(): 2，pop(): 5，[3 1 -1 2]
min(): 2，pop(): 2，[3 1 3]
min(): 3，pop(): 4，[3 3]
min(): 3，pop(): 3，[ ]
3.4 Найдите количество стеков и последовательность извлечения
Получить количество стеков
вопрос:Учитывая последовательность нажатия, попробуйте найти количество всех возможных последовательностей нажатия. Например, последовательность нажатия1，2，3, существует 5 возможных последовательностей извлечения:1 2 3，1 3 2 ，2 1 3，2 3 1，3 2 1.
развязать:Относительно легко определить количество извлеченных последовательностей. Было много статей, анализирующих этот вопрос, и окончательный ответ — число Каттелана, то естьnОбщее количество элементов в поп-последовательности равноC(2n, n) - C(2n, n-1) = C(2n, n) / (n+1), например, общее количество всплывающих окон из 3 элементов равноC(6, 3) / 4 = 5.
Если мы не анализируем общую формулу терма, которую нужно решить, можем ли мы написать программу для определения количества последовательностей, извлеченных из стека? Ответ — да, в соответствии с текущим состоянием стека мы можем出栈一个元素а также入栈一个元素Общее количество двух случаев складывается вместе, чтобы получить общее количество всплывающих окон.
/**
* 计算出栈数目
* - in：目前栈中的元素数目
* - out：目前已经出栈的元素数目
* - wait：目前还未进栈的元素数目
*/
int sumOfStackPopSequence(Stack *stack, int in, int out, int wait)
{
if (out == stack->capacity) { // 元素全部出栈了，返回1
return 1;
}
int sum = 0;
if (wait > 0) // 进栈一个元素
sum += sumOfStackPopSequence(stack, in + 1, out, wait - 1);
if (in > 0) // 出栈一个元素
sum += sumOfStackPopSequence(stack, in - 1, out + 1, wait);
return sum;
}
Найти все поп-последовательности
вопрос:учитывая входную последовательностьinput[] = {1, 2, 3}, печатает все возможные поп-последовательности.
развязать:Это немного сложно, не только количество всплывающих окон, но и необходимость печатать все извлеченные последовательности, и необходимо использовать метод возврата.Метод возврата намного сложнее, чем простая рекурсия.Когда есть время, я о методе возврата мы организуем статью отдельно. Последовательность всплывающих окон связана с порядком, в котором стек выталкивается и извлекается.Для каждого ввода есть две ситуации:Следует ли сначала извлекать или помещать элементы из исходного стека, здесь для реализации используются два стека, в которых стек stk используется для имитации проталкивания и извлечения из стека, а вывод стека используется для хранения значения стека.Обратите внимание, что условие выхода состоит в том, что когда все входные элементы пройдены, в стеке могут быть элементы stk и output.Вам нужно сначала распечатать вывод стека из нижней части стека, а затем распечатать стек stk из вершины стека. стек.Другой момент заключается в том, что когда используемый нами стек моделирования stk пуст, эта ветвь заканчивается. код показывает, как показано ниже:
void printStackPopSequence(int input[], int i, int n, Stack *stk, Stack *output)
{
if (i >= n) {
stackTraverseBottom(output); // output 从栈底开始打印
stackTraverseTop(stk); // stk 从栈顶开始打印
printf("\n");
return;
}
push(stk, input[i]);
printStackPopSequence(input, i+1, n, stk, output);
pop(stk);
if (IS_EMPTY(stk))
return;
int v = pop(stk);
push(output, v);
printStackPopSequence(input, i, n, stk, output);
push(stk, v);
pop(output);
}