Прежде всего, давайте поговорим о том, как мы можем визуализировать стек. Если бы у нас были деревянные поддоны, которые мы хотели бы организовать, мы бы, вероятно, поставили их друг на друга. Основная идея штабелирования заключается в том, что вы собираете деревянные поддоны сверху вниз, что называется 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