Шаблон класса Stack реализован в отдельном *.h файле, да, именно реализован, я не ошибся. Все дело в том, что и интерфейс шаблона класса и реализация должны находиться в одном файле, иначе вы увидите список ошибок похожего содержания:

ошибка undefined reference to «метод шаблона класса»

Интерфейс шаблона класса объявлен с 9 по 28 строки. Все методы класса содержат комментарии и, на мой взгляд, описывать их работу отдельно не имеет смысла. Обратите внимание на то, что все методы шаблона класса Стек объявлены как . Это сделано для того, чтобы ускорить работу класса. Так как встроенные функции класса работают быстрее, чем внешние.

Сразу после интерфейса шаблона идет реализация методов класса Стек, строки 32 — 117. В реализации методов класса ничего сложного нет, если знать как устроен стек, шаблоны и . Заметьте, в классе есть два конструктора, первый объявлен в строках 32-33, — это конструктор по умолчанию. А вот конструктор в строках 41-5, — это конструктор копирования. Он нужен для того, чтобы скопировать один объект в другой. Метод Peek , строки 80 — 88 предоставляет возможность просматривать элементы стека. Необходимо просто ввести номер элемента, отсчет идет от вершины стека. Остальные функции являются служебными, то есть предназначены для использования внутри класса, конечно же кроме функции printStack() , она вывод элементы стека на экран.

Теперь посмотрим на драйвер для нашего стека, под драйвером я подразумеваю программу в которой тестируется работа класса. Как всегда это main функция, в которой мы и будем тестировать наш шаблон класса Stack . Смотрим код ниже:

#include using namespace std; #include "stack.h" int main() { Stack stackSymbol(5); int ct = 0; char ch; while (ct++ < 5) { cin >> ch; stackSymbol.push(ch); // помещаем элементы в стек } cout << endl; stackSymbol.printStack(); // печать стека cout << "\n\nУдалим элемент из стека\n"; stackSymbol.pop(); stackSymbol.printStack(); // печать стека Stack newStack(stackSymbol); cout << "\n\nСработал конструктор копирования!\n"; newStack.printStack(); cout << "Второй в очереди элемент: "<< newStack.Peek(2) << endl; return 0; }

Создали объект стека, строка 9, размер стека при этом равен 5, то есть стек может поместить не более 5 элементов. Заполняем стек в , строки 13 — 17. В строке 21 выводим стек на экран, после удаляем один элемент из стека, строка 24 и снова выводим содержимое стека, поверьте оно изменилось, ровно на один элемент. Смотрим результат работы программы:

LOTR! | ! | R | T | O | L Удалим элемент из стека | R | T | O | L Сработал конструктор копирования! | R | T | O | L Второй в очереди элемент: T

В строке 28 мы воспользовались конструктором копирования, о том самом, о котором я писал выше. Не забудем про функцию peek() , давайте посмотри на второй элемент стека, строка 33.

На этом все! Стек у нас получился и исправно работает, попробуйте его протестировать, например на типе данных int . Я уверен, что все останется исправно работать.

Теги: Стек, стек на си, реализация стека, стек на массиве, динамически растущий стек, стек на односвязном сиске

Стек

С тек – наверное, самая простая структура данных, которую мы будем изучать и которой будем постоянно пользоваться. Стек – это структура данных, в которой элементы поддерживают принцип LIFO (“Last in – first out”): последним зашёл – первым вышел. Или первым зашёл – последним вышел.

Стек позволяет хранить элементы и поддерживает, обычно, две базовые операции:

• PUSH – кладёт элемент на вершину стека
• POP – снимает элемент с вершины стека, перемещая вершину к следующему элементу

Также часто встречается операция PEEK, которая получает элемент на вершине стека, но не снимает его оттуда.

Стек является одной из базовых структур данных и используется не только в программировании, но и в схемотехнике, и просто в производстве, для реализации технологических процессов и т.д.; стек используется в качестве вспомогательной структуры данных во многих алгоритмах и в других более сложных структурах.

Пусть, например, у нас есть стек чисел. Выполним несколько команд. Изначально стек пуст. Вершина стека – указатель на первый элемент, никуда не указывает. В случае си она может быть равна NULL.

Теперь стек состоит из одного элемента, числа 3. Вершина стека указывает на число 3.

Стек состоит из двух элементов, 5 и 3, при этом вершина стека указывает на 5.

Стек состоит из трёх элементов, вершина стека указывает на 7.

Вернёт значение 7, в стеке останется 5 и 3. Вершина будет указывать на следующий элемент – 5.

Вернёт 5, в стеке останется всего один элемент, 3, на который будет указывать вершина стека.

Вернёт 3, стек станет пуст.

Часто сравнивают стек со стопкой тарелок. Чтобы достать следующую тарелку, необходимо снять предыдущие. Вершина стека – это вершина стопки тарелок.

Когда мы будем работать со стеком, возможны две основные и часто встречающиеся ошибки:

• 1. Stack Underflow: Попытка снять элемент с пустого стека
• 2. Stack Overflow: Попытка положить новый элемент на стек, который не может больше расти (например, не хватает оперативной памяти)

Программная реализация

Р ассмотрим три простые реализации стека:

Стек фиксированного размера, построенный на массиве

О тличительная особенность – простота реализации и максимальная скорость выполнения. Такой стек может применяться в том, случае, когда его максимальный размер известен заранее или известно, что он мал.

Сначала определяем максимальный размер массива и тип данных, которые будут в нём храниться:

#define STACK_MAX_SIZE 20 typedef int T;

Теперь сама структура

Typedef struct Stack_tag { T data; size_t size; } Stack_t;

Здесь переменная size – это количество элементов, и вместе с тем указатель на вершину стека. Вершина будет указывать на следующий элемент массива, в который будет занесено значение.

Кладём новый элемент на стек.

Void push(Stack_t *stack, const T value) { stack->data = value; stack->size++; }

Единственная проблема – можно выйти за пределы массива. Поэтому всегда надо проверять, чтобы не было ошибки Stack overflow:

#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 void push(Stack_t *stack, const T value) { if (stack->size >= STACK_MAX_SIZE) { exit(STACK_OVERFLOW); } stack->data = value; stack->size++; }

Аналогично, определим операцию Pop, которая возвращает элемент с вершины и переходит к следующему

T pop(Stack_t *stack) { if (stack->size == 0) { exit(STACK_UNDERFLOW); } stack->size--; return stack->data; }

И функция peek, возвращающая текущий элемент с вершины

T peek(const Stack_t *stack) { if (stack->size <= 0) { exit(STACK_UNDERFLOW); } return stack->data; }

Ещё одно важное замечание – у нас нет функции создания стека, поэтому необходимо вручную обнулять значение size

Вспомогательные функции для печати элементов стека

Void printStackValue(const T value) { printf("%d", value); } void printStack(const Stack_t *stack, void (*printStackValue)(const T)) { int i; int len = stack->size - 1; printf("stack %d > ", stack->size); for (i = 0; i < len; i++) { printStackValue(stack->data[i]); printf(" | "); } if (stack->size != 0) { printStackValue(stack->data[i]); } printf("\n"); }

Заметьте, что в функции печати мы использует int, а не size_t, потому что значение len может стать отрицательным. Функция печатает сначала размер стека, а потом его содержимое, разделяя элементы символом |

Проверка

Stack_t stack; stack.size = 0; push(&stack, 3); printStack(&stack, printStackValue); push(&stack, 5); printStack(&stack, printStackValue); push(&stack, 7); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); _getch();

Рассмотрим также ситуации, когда есть ошибки использования. Underflow

Void main() { Stack_t stack; stack.size = 0; push(&stack, 3); pop(&stack); pop(&stack); _getch(); }

Void main() { Stack_t stack; size_t i; stack.size = 0; for (i = 0; i < 100; i++) { push(&stack, i); } _getch(); }

Динамически растущий стек на массиве

Д инамически растущий стек используется в том случае, когда число элементов может быть значительным и не известно на момент решения задачи. Максимальный размер стека может быть ограничен каким-то числом, либо размером оперативной памяти.

Стек будет состоять из указателя на данные, размера массива (максимального), и числа элементов в массиве. Это число также будет и указывать на вершину.

Typedef struct Stack_tag { T *data; size_t size; size_t top; } Stack_t;

Для начала понадобится некоторый начальный размер массива, пусть он будет равен 10

#define INIT_SIZE 10

Алгоритм работы такой: мы проверяем, не превысило ли значение top значение size. Если значение превышено, то увеличиваем размер массива. Здесь возможно несколько вариантов того, как увеличивать массив. Можно прибавлять число, можно умножать на какое-то значение. Какой из вариантов лучше, зависит от специфики задачи. В нашем случае будем умножать размер на число MULTIPLIER

#define MULTIPLIER 2

Максимального размера задавать не будем. Программа будет выпадать при stack overflow или stack underflow. Будем реализовывать тот же интерфейс (pop, push, peek). Кроме того, так как массив динамический, сделаем некоторые вспомогательные функции, чтобы создавать стек, удалять его и чистить.

Во-первых, функции для создания и удаления стека и несколько ошибок

#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 Stack_t* createStack() { Stack_t *out = NULL; out = malloc(sizeof(Stack_t)); if (out == NULL) { exit(OUT_OF_MEMORY); } out->size = INIT_SIZE; out->data = malloc(out->size * sizeof(T)); if (out->data == NULL) { free(out); exit(OUT_OF_MEMORY); } out->top = 0; return out; } void deleteStack(Stack_t **stack) { free((*stack)->data); free(*stack); *stack = NULL; }

Всё крайне просто и понятно, нет никаких подвохов. Создаём стек с начальной длиной и обнуляем значения.

Теперь напишем вспомогательную функцию изменения размера.

Void resize(Stack_t *stack) { stack->size *= MULTIPLIER; stack->data = realloc(stack->data, stack->size * sizeof(T)); if (stack->data == NULL) { exit(STACK_OVERFLOW); } }

Здесь, заметим, в случае, если не удалось выделить достаточно памяти, будет произведён выход с STACK_OVERFLOW.

Функция push проверяет, вышли ли мы за пределы массива. Если да, то увеличиваем его размер

Void push(Stack_t *stack, T value) { if (stack->top >= stack->size) { resize(stack); } stack->data = value; stack->top++; }

Функции pop и peek аналогичны тем, которые использовались для массива фиксированного размера

T pop(Stack_t *stack) { if (stack->top == 0) { exit(STACK_UNDERFLOW); } stack->top--; return stack->data; } T peek(const Stack_t *stack) { if (stack->top <= 0) { exit(STACK_UNDERFLOW); } return stack->data; }

Проверим

Void main() { int i; Stack_t *s = createStack(); for (i = 0; i < 300; i++) { push(s, i); } for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); } deleteStack(&s); _getch(); }

Напишем ещё одну функцию, implode, которая уменьшает массив до размера, равного числу элементов в массиве. Она может быть использована тогда, когда уже известно, что больше элементов вставлено не будет, и память может быть частично освобождена.

Void implode(Stack_t *stack) { stack->size = stack->top; stack->data = realloc(stack->data, stack->size * sizeof(T)); }

Можем использовать в нашем случае

For (i = 0; i < 300; i++) { push(s, i); } implode(s); for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); }

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

У неё есть недостаток, связанный с методом увеличения потребляемой памяти. При умножении в 2 раза (в нашем случае) требуется мало обращений к памяти, но при этом каждое последующее увеличение может привести к ошибке, особенно при маленьком количестве памяти в системе. Если же использовать более щадящий способ выделения памяти (например, каждый раз прибавлять по 10), то число обращений увеличится и скорость упадёт. На сегодня, проблем с размером памяти обычно нет, а менеджеры памяти и сборщики мусора (которых нет в си) работают быстро, так что агрессивное изменение преобладает (на примере, скажем, реализации всей стандартной библиотеки языка Java).

Реализация стека на односвязном списке

Ч то такое односвязный список, . Коротко: односвязный список состоит из узлов, каждый из которых содержит полезную информацию и ссылку на следующий узел. Последний узел ссылается на NULL.

Никакого максимального и минимального размеров у нас не будет (хотя в общем случае может быть). Каждый новый элемент создаётся заново. Для начала определим структуру узел

#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 typedef int T; typedef struct Node_tag { T value; struct Node_tag *next; } Node_t;

Функция вставки первого элемента проста: создаём новый узел. Указатель next кидаем на старый узел. Далее указатель на вершину стека перекидываем на вновь созданный узел. Теперь вершина стека указывает на новый узел.

Void push(Node_t **head, T value) { Node_t *tmp = malloc(sizeof(Node_t)); if (tmp == NULL) { exit(STACK_OVERFLOW); } tmp->next = *head; tmp->value = value; *head = tmp; }

Функция pop берёт первый элемент (тот, на который указывает вершина), перекидывает указатель на следующий элемент и возвращает первый. Здесь есть два варианта – можно вернуть узел или значение. Если вернём значение, то придётся удалять узел внутри функции

Node_t* pop1(Node_t **head) { Node_t *out; if ((*head) == NULL) { exit(STACK_UNDERFLOW); } out = *head; *head = (*head)->next; return out; }

T pop2(Node_t **head) { Node_t *out; T value; if (*head == NULL) { exit(STACK_UNDERFLOW); } out = *head; *head = (*head)->next; value = out->value; free(out); return value; }

Теперь вместо проверки на длину массива везде используется проверка на равенство NULL вершины стека.

Простая функция peek

T peek(const Node_t* head) { if (head == NULL) { exit(STACK_UNDERFLOW); } return head->value; }

Итерирование достаточно интересное. Просто переходим от одного узла к другому, пока не дойдём до конца

Void printStack(const Node_t* head) { printf("stack >"); while (head) { printf("%d ", head->value); head = head->next; } }

И ещё одна проблема – теперь нельзя просто посмотреть размер стека. Нужно пройти от начала до конца и посчитать все элементы. Например, так

Size_t getSize(const Node_t *head) { size_t size = 0; while (head) { size++; head = head->next; } return size; }

Конечно, можно хранить размер отдельно, можно обернуть стек со всеми данными ещё в одну структуру и т.д. Рассмотрим всё это при более подробном изучении списков.

Мы используем всё более продвинутые языки программирования, которые позволяют нам писать меньше кода и получать отличные результаты. За это приходится платить. Поскольку мы всё реже занимаемся низкоуровневыми вещами, нормальным становится то, что многие из нас не вполне понимают, что такое стек и куча, как на самом деле происходит компиляция, в чём разница между статической и динамической типизацией, и т.д. Я не говорю, что все программисты не знают об этих понятиях - я лишь считаю, что порой стоит возвращаться к таким олдскульным вещам.

Сегодня мы поговорим лишь об одной теме: стек и куча. И стек, и куча относятся к различным местоположениям, где происходит управление памятью, но стратегия этого управления кардинально отличается.

Стек

Стек - это область оперативной памяти, которая создаётся для каждого потока. Он работает в порядке LIFO (Last In, First Out), то есть последний добавленный в стек кусок памяти будет первым в очереди на вывод из стека. Каждый раз, когда функция объявляет новую переменную, она добавляется в стек, а когда эта переменная пропадает из области видимости (например, когда функция заканчивается), она автоматически удаляется из стека. Когда стековая переменная освобождается, эта область памяти становится доступной для других стековых переменных.

Из-за такой природы стека управление памятью оказывается весьма логичным и простым для выполнения на ЦП; это приводит к высокой скорости, в особенности потому, что время цикла обновления байта стека очень мало, т.е. этот байт скорее всего привязан к кэшу процессора. Тем не менее, у такой строгой формы управления есть и недостатки. Размер стека - это фиксированная величина, и превышение лимита выделенной на стеке памяти приведёт к переполнению стека. Размер задаётся при создании потока, и у каждой переменной есть максимальный размер, зависящий от типа данных. Это позволяет ограничивать размер некоторых переменных (например, целочисленных), и вынуждает заранее объявлять размер более сложных типов данных (например, массивов), поскольку стек не позволит им изменить его. Кроме того, переменные, расположенные на стеке, всегда являются локальными.

В итоге стек позволяет управлять памятью наиболее эффективным образом - но если вам нужно использовать динамические структуры данных или глобальные переменные, то стоит обратить внимание на кучу.

Куча

Куча - это хранилище памяти, также расположенное в ОЗУ, которое допускает динамическое выделение памяти и не работает по принципу стека: это просто склад для ваших переменных. Когда вы выделяете в куче участок памяти для хранения переменной, к ней можно обратиться не только в потоке, но и во всем приложении. Именно так определяются глобальные переменные. По завершении приложения все выделенные участки памяти освобождаются. Размер кучи задаётся при запуске приложения, но, в отличие от стека, он ограничен лишь физически, и это позволяет создавать динамические переменные.

Вы взаимодействуете с кучей посредством ссылок, обычно называемых указателями - это переменные, чьи значения являются адресами других переменных. Создавая указатель, вы указываете на местоположение памяти в куче, что задаёт начальное значение переменной и говорит программе, где получить доступ к этому значению. Из-за динамической природы кучи ЦП не принимает участия в контроле над ней; в языках без сборщика мусора (C, C++) разработчику нужно вручную освобождать участки памяти, которые больше не нужны. Если этого не делать, могут возникнуть утечки и фрагментация памяти, что существенно замедлит работу кучи.

В сравнении со стеком, куча работает медленнее, поскольку переменные разбросаны по памяти, а не сидят на верхушке стека. Некорректное управление памятью в куче приводит к замедлению её работы; тем не менее, это не уменьшает её важности - если вам нужно работать с динамическими или глобальными переменными, пользуйтесь кучей.