Реализация стека на языке Си
Реализуем стек вещественных чисел. Ниже мы используем эту реализацию как составную часть проекта Стековый калькулятор (см. раздел 4.4.2).
Реализация включает два файла: "streal.h", в котором описывается интерфейс исполнителя "Стек", и "streal.cpp", реализующий функции работы со стеком. Слово real обозначает вещественное число.
Используется первый вариант реализации стека на базе массива, описанный в предыдущем разделе: стек растет в сторону увеличения индексов массива. Пространство под массив элементов стека захватывается в динамической памяти в момент инициализации стека. Функции инициализации st_init передается размер массива, т.е. максимально возможное число элементов в стеке. Для завершения работы стека нужно вызвать функцию st_terminate, которая освобождает захваченную в st_init память. Ниже приведено содержимое файла "streal.h", описывающего интерфейс стека.
// Файл "streal.h" // Стек вещественных чисел, интерфейс // #ifndef ST_REAL_H #define ST_REAL_H
// Прототипы функций, реализующих предписания стека:
void st_init(int maxSize); // Начать работу (вх: цел // макс. размер стека) void st_terminate(); // Закончить работу void st_push(double x); // Добавить эл-т (вх: вещ x) double st_pop(); // Взять элемент: вещ double st_top(); // Вершина стека: вещ int st_size(); // Текущий размер стека: цел bool st_empty(); // Стек пуст? : лог int st_maxSize(); // Макс. размер стека: цел bool st_freeSpace(); // Есть свободное место? : лог void st_clear(); // Удалить все элементы double st_elementAt(int i); // Элемент стека на // глубине (вх: i): вещ #endif // Конец файла "streal.h"
Отметим, что директивы условной трансляции
#ifndef ST_REAL_H #define ST_REAL_H . . . #endif
используются для предотвращения повторного включения h-файла: при первом включении файла определяется переменная препроцессора ST_REAL_H, а директива "#ifndef ST_REAL_H" подключает текст, только если эта переменная не определена. Такой трюк используется практически во всех h-файлах.
Нужен он потому, что одни h-файлы могут подключать другие, и без этого механизма избежать повторного включения одного и того же файла трудно.
Файл "streal.cpp" описывает общие статические переменные, над которыми работают функции, соответствующие предписаниям стека, и реализует эти функции.
// Файл "streal.cpp" // Стек вещественных чисел, реализация // #include <stdlib.h> #include <assert.h> #include "streal.h" // Подключить описания функций стека
// Общие переменные для функций, реализующих // предписания стека: static double *elements = 0; // Указатель на массив эл-тов // стека в дин. памяти static int max_size = 0; // Размер массива static int sp = (-1); // Индекс вершины стека
// Предписания стека:
void st_init(int maxSize) { // Начать работу (вх: // макс. размер стека) assert(elements == 0); max_size = maxSize; elements = (double *) malloc( max_size * sizeof(double) ); sp = (-1); }
void st_terminate() { // Закончить работу if (elements != 0) { free(elements); } }
void st_push(double x) { // Добавить эл-т (вх: вещ x) assert( // утв: elements != 0 && // стек начал работу и sp < max_size-1 // есть своб. место ); ++sp; elements[sp] = x; }
double st_pop() { // Взять элемент: вещ assert(sp >= 0); // утв: стек не пуст --sp; // элемент удаляется из стека return elements[sp + 1]; }
double st_top() { // Вершина стека: вещ assert(sp >= 0); // утв: стек не пуст return elements[sp]; }
int st_size() { // Текущий размер стека: цел return (sp + 1); }
bool st_empty() { // Стек пуст? : лог return (sp < 0); }
int st_maxSize() { // Макс. размер стека: цел return max_size; }
bool st_freeSpace() { // Есть своб. место? : лог return (sp < max_size - 1); }
void st_clear() { // Удалить все элементы sp = (-1); }
double st_elementAt(int i) { // Элемент стека на // глубине (вх: i): вещ assert( // утв: elements != 0 && // стек начал работу и 0 <= i && i < st_size() // 0 <= i < размер стека ); return elements[sp - i]; } // Конец файла "streal.cpp"
