Стеки на примере языка Си

Привет, сегодня поговорим про стеки на е языка си, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое стеки на е языка си , настоятельно рекомендую прочитать все из категории Структуры данных.

Стек (stack) является как бы противоположностью очереди, поскольку он работает по принципу "последним пришел — первым вышел" (last-in, first-out, LIFO)^[1]. Чтобы наглядно представить себе стек, вспомните стопку тарелок. Первая тарелка, стоящая на столе, будет использована последней, а последняя тарелка, положенная наверх — первой. Стеки часто применяются в системном программном обеспечении, включая компиляторы и интерпретаторы.

При работе со стеками операции занесения и извлечения элемента являются основными. Данные операции традиционно называются "затолкать в стек" (push)^[2] и "вытолкнуть из стека" (pop)^[3]. Поэтому для реализации стека необходимо написать две функции: push(), которая "заталкивает" значение в стек, и pop(), которая "выталкивает" значение из стека. Также необходимо выделить область памяти, которая будет использоваться в качестве стека. Для этой цели можно отвести массив или динамически выделить фрагмент памяти с помощью функций языка С, предусмотренных для динамического распределения памяти. Как и в случае очереди, функция извлечения получает из списка элемент и удаляет его, если он не хранится где-либо еше. Ниже приведена общая форма функций push() и pop(), работающих с целочисленным массивом. Стеки данных другого типа можно организовывать, изменив базовый тип данных массива.

int stack[MAX];
int tos=0;   /* вершина стека */

/* Затолкать элемент в стек. */
void push(int i)
{

  if(tos >= MAX) {
    printf("Стак полон\n");
    return;
  }
  stack[tos] = i;
  tos++;
}

/* Получить верхний элемент стека. */
int pop(void)
{
  tos--;
  if(tos < 0) {
    printf("Стек пуст\n");
    return 0;
  }
  return stack[tos];
}

Переменная tos ("top of stack" — "вершина стека"^[4]) содержит индекс вершины стека. При реализации данных функций необходимо учитывать случаи, когда стек заполнен или пуст. В нашем случае признаком пустого стека является равенство tos нулю, а признаком переполнения стека — такое увеличение tos, что его значение указывает куда-нибудь за пределы последней ячейки массива. Пример работы стека показан в табл. 22.2.

Прекрасный пример использования стека — калькулятор с четырьмя действиями. Об этом говорит сайт https://intellect.icu . Большинство современных калькуляторов воспринимают стандартную запись выражений, называемую инфиксной записью^[5], общая форма которой выглядит как операнд-оператор-операнд. Например, чтобы сложить 100 и 200, необходимо ввести 100, нажать кнопку "плюс" ("+"), затем ввести 200 и нажать кнопку "равно" ("="). Напротив, во многих ранних калькуляторах (и некоторых из производимых сегодня) применяется постфиксная запись^[6], в которой сначала вводятся оба операнда, а затем оператор. Например, чтобы сложить 100 и 200 в постфиксной записи, необходимо ввести 100, затем 200, а потом нажать клавишу "плюс". В этом методе операнды при вводе заталкиваются в стек. При вводе оператора операнды извлекаются (выталкиваются) из стека, а результат помещается обратно в стек. Одно из преимуществ постфиксной формы заключается в легкости ввода длинных сложных выражений.

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

int *p;   /* указатель на область свободной памяти */
int *tos; /* указатель на вершину стека */
int *bos; /* указатель на дно стека */

/* Занесение элемента в стек. */
void push(int i)
{
  if(p > bos) {
    printf("Стек полон\n");
    return;
  }
  *p = i;
  p++;
}

/* Получение верхнего элемента из стека. */
int pop(void)
{
  p--;
  if(p < tos) {
    printf("Стек пуст\n");
    return 0;
  }
  return *p;
}

Перед использованием этих функций необходимо выделить память из области свободной памяти с помощью функции malloc() и присвоить переменой tos адрес начала этой области, а переменной bos — адрес ее конца.

Текст программы постфиксного калькулятора целиком приведен ниже.

/* Простой калькулятор с четырмя действиями. */

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int *p;   /* указатель на область свободной памяти */
int *tos; /* указатель на вершину стека */
int *bos; /* указатель на дно стека */

void push(int i);
int pop(void);

int main(void)
{
  int a, b;
  char s[80];

  p = (int *) malloc(MAX*sizeof(int)); /* получить память для стека */
  if(!p) {
    printf("Ошибка при выделении памяти\n");
    exit(1);
  }
  tos = p;
  bos = p + MAX-1;

  printf("Калькулятор с четырьмя действиями\n");
  printf("Нажмите 'q' для выхода\n");

  do {
    printf(": ");
    gets(s);
    switch(*s) {
      case '+':
        a = pop();
        b = pop();
        printf("%d\n", a+b);
        push(a+b);
        break;
      case '-':
        a = pop();
        b = pop();
        printf("%d\n", b-a);
        push(b-a);
        break;
      case '*':
        a = pop();
        b = pop();
        printf("%d\n", b*a);
        push(b*a);
        break;
      case '/':
        a = pop();
        b = pop();
        if(a==0) {
          printf("Деление на 0.\n");
          break;
        }
        printf("%d\n", b/a);
        push(b/a);
        break;
      case '.': /* показать содержимое вершины стека */
        a = pop();
        push(a);
        printf("Текущее значение на вершине стека: %d\n", a);
        break;
      default:
        push(atoi(s));
    }
  } while(*s != 'q');

  return 0;
}

/* Занесение элемента в стек. */
void push(int i)
{
  if(p > bos) {
    printf("Стек полон\n");
    return;
  }
  *p = i;
  p++;
}

/* Получение верхнего элемента из стека. */
int pop(void)
{
  p--;
  if(p < tos) {
    printf("Стек пуст\n");
    return 0;
  }
  return *p;
}

^[1]Иными словами, в магазинном порядке.

^[2]А также: проталкивать (в стек), помещать на стек, класть в стек, поместить в стек, положить в стек, сохранить в стеке.

^[3]А также: выталкивать данные из стека, выталкивание из стека, выталкивание данных из стека, снимать со стека, вынимать из стека, считывать из стека, вытаскивать из стека.

^[4]Называется также верхушкой.

^[5]Другие названия: инфиксное представление, инфиксная нотация.

^[6]Другие названия: постфиксная нотация, польская инверсная запись.

На этом все! Теперь вы знаете все про стеки на е языка си, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое стеки на е языка си и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных