О стеке в C

Языков программирования существует великое множество. И часто новые языки создаются потому, что в старых чего-то нехватало. Однако C – язык исключение, несмотря на появление Go и Rust он всё ещё твёрдо держит свои позиции.

Часто C упрекают ввиду его компактности, и поэтому многие вещи приходится писать самому, руками. Однако с другой стороны, такое положение дел, вынуждает разработчиков глубже вникать в устройство типов данных, функций и т. д.

В этой статье я предлагаю читателю рассмотреть, устройство такого популярного типа данных как стек и его реализацию в C. Начнём с определения: — тип данных, представляющий собой список элементов, организованных по принципу LIFO. У неподготовленного, сразу возникнет вопрос, а что же такое LIFO? LIFO – с англ. «last in — first out», «последним пришёл — первым вышел». Для наглядности, представьте себе тарелку в которую складывают блины. Первый положенный блин, в последствии будет последним. А последний положенный, будет съеден первым.

В любой современной машине есть свой аппаратный стек. Для манипулирования им существуют специальные команды языка ассемблера push и pop. Первая добавляет новый элемент в стек, а вторая выталкивает самый верхний элемент, а его значение сохраняет куда-либо (обычно в регистр). Ввиду этого, можно было бы просто использовать аппаратный стек, однако, во первых, он только один, а во вторых, мы не ищем лёгких путей.

Обычно при реализации стека используют 2 указателя: SP – stack pointer (указатель стека) указывает на вершину стека и BS – bottom stack (дно стека), указывает на дно стека. Ситуация когда SP == BS, есть не что иное, как пустой стек. Если стек может быть пустым, то он соответственно может быть и полным.

Однако нередко можно встретить и реализацию стека через связный список, например здесь или на Википедии.

Однако перейдём от слов к делу. Начнём с функции создания стека:

char *stack_new(size_t size) {     return malloc(size); }

В нашем примере, создаётся стек символов размером size, однако ничто не мешает Вам заменить char на int или что-либо другое.

После того как мы создали стек, не плохо было бы удалить его. И так как при создании мы воспользовались функцией malloc, то при удалении нам надо использовать комплиментарную ей free:

void stack_del(char *stack) {     free(stack); }

Перейдём к помещению символов в стек:

static int offset = 0;  void push(char *stack, char val) {     *(stack+offset) = val;     offset++; }

Внимательный читатель заметит присутствие переменной offset, она в данном случае заменяет SP, являясь смещением относительно дна стека (аргумента stack). Так же обращаю внимание на то, что переменная offset объявлена со спецификатором static вне функций, а это значит, она будет видна только в файле в котором объявлена.

Положив символ в стек, его надо вытолкнуть, и для этого есть ещё одна функция:

char pop(char *stack) {     return *stack+(--offset); }

Здесь так же используется offset. И внимательный читатель, заметит, что если стек пуст, то функция отработает, и даже не заметит ошибки, поэтому исправим:

char pop(char *stack) {     if (offset)          return *stack+(--offset);     else         return -1;   }

Теперь, в случае пустого стека, будет возвращено -1. Однако стек может и переполниться, поэтому перепишем остальные функции так:

char *stack_new(int len) {     stack_len = len;      return (char*)malloc(sizeof(char) * len); }  int push(char *stack, char val) {     if (offset == stack_len)         return -1;      *(stack+offset) = val;     offset++;     return 1; }

Теперь, при создании стека, помимо выделения памяти, происходит инициализация переменной stack_len, а если offset == stack_len, значит стек переполнился, и функция push возвратит -1.

Таким образом мы получаем полный исходный файл:

#include <stdlib.h>  static int offset = 0; static int stack_len = 0;  char *stack_new(int len) {     stack_len = len;      return (char*)malloc(sizeof(char) * len); }  void stack_del(char *stack) {     free(stack); }  int push(char *stack, char val) {     if (offset == stack_len)         return -1;      *(stack+offset) = val;     offset++;     return 1; }  char pop(char *stack) {     if (offset)          return *stack+(--offset);     else         return -1;   }

К нему можно добавить дополнительный заголовочный файл и получить библиотеку. А если требуется несколько стеков, то переменные offset, stack_len и указатель *stack можно оформить в структуру.

У меня, всё. Надеюсь для тебя, Читатель, эта статья была полезна.