Спонсоры сайта:

Места проведения в Тольятти кафе для свадьбы, блокнот амура.

Наличие этой страницы в поиске?

Информеры ТИЦ и PR

  Yandex ТИЦ:  
   Google PR:  

Путешественникам, меломанам, бизнесменам, вебмастерам, новости.

Содержание | <<< | >>>

Стеки





Стек (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.

Таблица 22.2. Действие стека
ДействиеСодержимое стека
push(A)A
push(B)В А
push(C)C B A
рор() извлекает СВ А
push(F)F В А
рор() извлекает FВ А
рор() извлекает ВА
рор() извлекает Апусто

Прекрасный пример использования стека — калькулятор с четырьмя действиями. Большинство современных калькуляторов воспринимают стандартную запись выражений, называемую инфиксной записью[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]Другие названия: постфиксная нотация, польская инверсная запись.


Содержание | <<< | >>>

C++ исходники. Все примеры - рабочие:

часы:

Dev C++ WinAPI Стрелочные часы Analog Clock

Dev C++ WinAPI Цифровые прозрачные часы. Текст на рабочем столе. Digital transparent clock. Text on desktop

Dev C++ OLE WinApi CALENDAR and DIGITAL CLOCK (15kb). Календарь и цифровые часы

Dev C++ OLE WinAPI Календарь и цифровые часы почти Vista SideBar всего 21kb

плееры:

Microsoft Visual C++ 2008 Direct Show DVD Mini Player 10.5kb

Dev C++ WinAPI Микро медиа плеер 3.5kb

Dev C++ WinAPI Мини медиа плеер 4.5kb

Dev C++ WinAPI Hint Всплывающая подсказка

Dev C++ WinAPI RECT - имитатор кнопки

Dev C++ WinAPI Заполнить ListBox

Dev C++ WinAPI Заполнить, редактировать, сохранить, загрузить ListBox (PlayList)

Dev C++ WinAPI Индикатор уровня

Dev C++ WinAPI MP3 Микро плеер Открыть с помощью...

Dev C++ WinAPI Своя кнопка

изображения:

Dev C++ GDI+ WinAPI Mini FotoResizer (16kb), изменяет размеры всех фото (JPG) до указанного размера в выбраной папке и её подпапках

Dev C++ WinAPI Сохранить BITMAP экрана, десктопа, окна, клиентской области.

Dev C++ WinAPI Изменить размер изображения BMP RESIZE. Загрузка изображений из ФАЙЛА, вывод на экран и сохранение в файл.

Dev C++ WinAPI Загрузка изображений из РЕСУРСОВ и вывод на экран.

Dev C++ GDI+ WinAPI. Преобразовать изображения из одного формата в другой (JPG в BMP, GIF, PNG и обратно ), используя дополнительные библиотеки GDI+. Загрузка изображений из файла и сохранение в файл.

Dev C++ GDI+ WinAPI масштабирование JPG RESIZE

Dev C++ OLE WinAPI. Преобразовать изображения из JPG в BMP, используя дополнительные библиотеки OLE. Загрузка изображений из РЕСУРСОВ и сохранение в файл.

Dev C++ OLE WinAPI преобразовать JPG в BMP, используя дополнительные библиотеки OLE. Загрузка изображений из ФАЙЛА и сохранение в файл.

Dev C++ OLE WinAPI масштабирование BMP RESIZE

разное:

Dev C++ WinAPI Dev C++ Преобразовать цвет точки экрана в HTML код

Dev C++ WinAPI NOTIFYICONDATA WS_EX_TOOLWINDOW Иконка в области уведомлений (notification area, tray, трей). Удалить с панели задач (taskbar).

Dev C++ WinAPI ShellExecute Создать ссылку на WEB сайт

Dev C++ WinAPI ShellExecute Создать окно со ссылкой на WEB сайт

Dev C++ WinAPI CreateProcess ShellExecute WinExec Запуск приложения из приложения

Dev C++ OLE WinAPI Создать регион Regions PopUp Меню Menu

Dev C++ FindFiles. Поиск файлов заданного типа (в примере *.JPG) в папке и её подпапках

библиотеки:

Скачать библиотеку GDI+ для Dev C++

Скачать справочнник с примерами языка C.