Прежде всего, давайте поговорим о том, как мы можем визуализировать стек. Если бы у нас были деревянные поддоны, которые мы хотели бы организовать, мы бы, вероятно, поставили их друг на друга. Основная идея штабелирования заключается в том, что вы собираете деревянные поддоны сверху вниз, что называется LIFO (последним пришел — первым ушел).
Стеки имеют как минимум 2 функции, которые помогают видоизменять стек, обычно они называются «push» и «pop». Push — это добавление нового элемента в начало стека, в то время как pop удаляет элемент из вершины стека, передавая его значение вызываемому.
В нашей реализации у нас будет стек целых чисел, мы будем использовать язык программирования C для выполнения этой задачи, но это выполнимо на большинстве языков, но реализация может отличаться.
Сначала нам нужна структура для отслеживания головы стека, которая представляет собой элемент, содержащий значение и указатель на предыдущий элемент. Мы сохраняем ссылку на предыдущий элемент, чтобы пройти назад и в конечном итоге оказаться на первом элементе. Давайте посмотрим, как мы будем проектировать структуру стека и элементов стека.
typedef struct stack_item { // The value given to the item. int value; // The pointer to the previous item. struct stack_item * prev; } stack_item; typedef struct stack { // The current length of the stack. int length; // The head is a pointer to the value at the top of the stack. stack_item * head; } stack;
Теперь нам нужен способ построения этого стека, в C мы создадим функцию, которая будет возвращать указатель на новый стек.
stack * create_stack() { stack * s = (stack *) malloc(sizeof(stack)); s->length = 0; s->head = NULL; return s; }
Мы не можем вытолкнуть этот стек, пока у нас не будет чего-то в нем, поэтому давайте продолжим и добавим функцию «push».
void stack_push(stack * s, int value) { stack_item * si = (stack_item *) malloc(sizeof(stack_item)); si->value = value; si->prev = s->head; s->head = si; s->length++; }
Итак, здесь мы говорим, что для использования функции stack_push нам нужно передать ей стек и значение для отправки. Затем будет выделено место для нового элемента стека, которому затем присваивается значение и адрес памяти предыдущего значения, затем мы обновляем голову стека и увеличиваем его длину.
Теперь нам нужно предоставить нашу поп-функцию, которая будет получать значение из стека и возвращаться к предыдущему значению.
int stack_pop(stack * s) { // Get the value from the current item before we remove it. int value = s->head->value; stack_item * i = s->head; // Set head on the stack to the previous item. s->head = s->head->prev; // Decrement the size of the stack. s->length--; // Free up the memory allocated for the previous item. free(i); // Return the value we stored from the item we removed. return value; }
Теперь, чтобы использовать его, давайте создадим стек, поместите 1, 2 и затем 3 в стек и посмотрите, в каком порядке они выходят.
int main() { stack * s = create_stack(); stack_push(s, 1); stack_push(s, 2); stack_push(s, 3); printf("First: %d\n", stack_pop(s)); printf("Second: %d\n", stack_pop(s)); printf("Third: %d\n", stack_pop(s)); return 0; }
Результат должен быть таким, как показано ниже, показывая нам, что целые числа возвращаются последними.
[bweston@bweston-dell stack]$ gcc main.c
[bweston@bweston-dell stack]$ ./a.out
Первый: 3
Второй: 2
Третий : 1
Код можно найти здесь: https://gist.github.com/bweston92/88c86a76a5531f1b7a37c0a6891e578f