С тек – наверное, самая простая структура данных, которую мы будем изучать и которой будем постоянно пользоваться. Стек – это структура данных, в которой элементы поддерживают принцип 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: Попытка положить новый элемент на стек, который не может больше расти (например, не хватает оперативной памяти)
Программная реализация
- 1) Стек фиксированного размера на массиве
- 2) Динамически растущий стек на массиве
- 3) Динамически растущий стек на односвязном списке
Стек фиксированного размера, построенный на массиве
О тличительная особенность – простота реализации и максимальная скорость выполнения. Такой стек может применяться в том, случае, когда его максимальный размер известен заранее или известно, что он мал.
Сначала определяем максимальный размер массива и тип данных, которые будут в нём храниться:
#define STACK_MAX_SIZE 20 typedef int T;
Теперь сама структура
typedef struct Stack_tag < T data[STACK_MAX_SIZE]; size_t size; >Stack_t;
Здесь переменная size – это количество элементов, и вместе с тем указатель на вершину стека. Вершина будет указывать на следующий элемент массива, в который будет занесено значение.
Стек как структура данных. Полное понимание! Динамические структуры данных #4
Кладём новый элемент на стек.
void push(Stack_t *stack, const T value) < stack->data[stack->size] = 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[stack->size] = value; stack->size++; >
Аналогично, определим операцию Pop, которая возвращает элемент с вершины и переходит к следующему
T pop(Stack_t *stack) < if (stack->size == 0) < exit(STACK_UNDERFLOW); >stack->size—; return stack->data[stack->size]; >
И функция peek, возвращающая текущий элемент с вершины
T peek(const Stack_t *stack) < if (stack->size return stack->data[stack->size — 1]; >
Ещё одно важное замечание – у нас нет функции создания стека, поэтому необходимо вручную обнулять значение 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( printStack( push( printStack( push( printStack( printf(«%dn», pop( printStack( printf(«%dn», pop( printStack( printf(«%dn», pop( printStack( _getch();
Рассмотрим также ситуации, когда есть ошибки использования. Underflow
void main()
void main() < Stack_t stack; size_t i; stack.size = 0; for (i = 0; i < 100; i++) < push( >_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[stack->top] = value; stack->top++; >
Функции pop и peek аналогичны тем, которые использовались для массива фиксированного размера
T pop(Stack_t *stack) < if (stack->top == 0) < exit(STACK_UNDERFLOW); >stack->top—; return stack->data[stack->top]; > T peek(const Stack_t *stack) < if (stack->top return stack->data[stack->top — 1]; >
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( _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
Эта однопоточная реализация стека использует мало обращений к памяти, достаточно проста и универсальна, работает быстро и может быть реализована, при необходимости, за несколько минут. Она используется всегда в дальнейшем, если не указано иное.
У неё есть недостаток, связанный с методом увеличения потребляемой памяти. При умножении в 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; >
Конечно, можно хранить размер отдельно, можно обернуть стек со всеми данными ещё в одну структуру и т.д. Рассмотрим всё это при более подробном изучении списков.
void main() < int i; Node_t *head = NULL; for (i = 0; i < 300; i++) < push( >printf(«size = %dn», getSize(head)); while (head) < printf(«%d «, peek(head)); printf(«%d «, pop2( >_getch(); >
void main() < int i; Node_t *head = NULL; Node_t *tmp; for (i = 0; i < 300; i++) < push( >printf(«size = %dn», getSize(head)); while (head) < printf(«%d «, peek(head)); tmp = pop1( printf(«%d «, tmp->value); free(tmp); > _getch(); >
Всё ещё не понятно? – пиши вопросы на ящик
Источник: learnc.info
Структура данных: стеки
Стек является общей структурой данных для представления данных, которые должны обрабатываться в определенном порядке. Например, когда функция вызывает другую функцию, которая, в свою очередь, вызывает третью функцию, важно, чтобы третья функция вернулась на вторую функцию, а не первую.
Один из способов реализации такого порядка обработки данных — это организовать своего рода очередь вызовов функций. Последняя добавленная в стек функция, будет завершена первой и наоборот, первая добавленная в стек функция будет завершена последней. Таким образом, сама структура данных обеспечивает надлежащий порядок вызовов.
Концептуально, структура данных — стек очень проста: она позволяет добавлять или удалять элементы в определенном порядке. Каждый раз, когда добавляется элемент, он попадает на вершину стека, единственный элемент, который может быть удален из стека — элемент, который находится на вершине стека. Таким образом, стек, как принято говорить, «первым пришел, последним ушел — FILO» или «последним пришел, первым ушел — LIFO». Первый элемент, добавленный в стек будет удален из него в последнюю очередь.
Так в чем же дело? Зачем нам нужны стеки? Как мы уже говорили, стеки — удобный способ организации вызовов функций. В самом деле, «стек вызовов» это термин, который часто используют для обозначения списка функций, которые сейчас либо выполняются, либо находятся в режиме ожидания возвращаемого значения других функций.
В некотором смысле, стеки являются частью фундаментального языка информатики. Когда вы хотите реализовать очередь типа — «первый пришел, последним ушел», то имеет смысл говорить о стеках с использованием общей терминологии. Кроме того, такие очереди участвуют во многих процессах, начиная от теоретических компьютерных наук, например функции push-down и многое другое.
Стеки имеют некоторые ассоциируемые методы:
- Push — добавить элемент в стек;
- Pop — удалить элемент из стека;
- Peek — просмотреть элементы стека;
- LIFO — поведение стека,
- FILO Equivalent to LIFO
Давайте теперь разработаем программу, которая будет реализовывать работу структуры данных Стек. Создадим универсальный стек, который будет соответствовать методике обобщенного программирования, то есть создадим шаблон класса Stack . Если вы плохо знакомы с шаблонами, то прочитайте статью: Шаблоны функций, там подробно описан механизм работы с шаблонами. Если же вы знакомы с шаблонами, но забыли как работать с шаблонами классов, прочитайте статью о шаблонах классов.
Этот стек был реализован с шаблонами, чтобы его можно было использовать практически для любых типов данных. Причем размер стека определяется динамически, во время выполнения программы. В стек добавлена также дополнительная функция: peek() , которая показывает n-й элемент от вершины стека.
#ifndef STACK_H #define STACK_H #include // для assert #include #include // для setw template class Stack < private: T *stackPtr; // указатель на стек const int size; // максимальное количество элементов в стеке int top; // номер текущего элемента стека public: Stack(int = 10); // по умолчанию размер стека равен 10 элементам Stack(const Stack // конструктор копирования ~Stack(); // деструктор inline void push(const T // поместить элемент в вершину стека inline T pop(); // удалить элемент из вершины стека и вернуть его inline void printStack(); // вывод стека на экран inline const T // n-й элемент от вершины стека inline int getStackSize() const; // получить размер стека inline T *getPtr() const; // получить указатель на стек inline int getTop() const; // получить номер текущего элемента в стеке >; // реализация методов шаблона класса STack // конструктор Стека template Stack::Stack(int maxSize) : size(maxSize) // инициализация константы < stackPtr = new T[size]; // выделить память под стек top = 0; // инициализируем текущий элемент нулем; >// конструктор копирования template Stack::Stack(const Stack stackPtr = new T[size]; // выделить память под новый стек top = otherStack.getTop(); for(int ix = 0; ix < top; ix++) stackPtr[ix] = otherStack.getPtr()[ix]; >// функция деструктора Стека template Stack::~Stack() < delete [] stackPtr; // удаляем стек >// функция добавления элемента в стек template inline void Stack::push(const T // проверяем размер стека assert(top < size); // номер текущего элемента должен быть меньше размера стека stackPtr[top++] = value; // помещаем элемент в стек >// функция удаления элемента из стека template inline T Stack::pop() < // проверяем размер стека assert(top >0); // номер текущего элемента должен быть больше 0 stackPtr[—top]; // удаляем элемент из стека > // функция возвращает n-й элемент от вершины стека template inline const T // assert(nom // вывод стека на экран template inline void Stack::printStack() < for (int ix = top — 1; ix >= 0; ix—) cout // вернуть размер стека template inline int Stack::getStackSize() const < return size; >// вернуть указатель на стек (для конструктора копирования) template inline T *Stack::getPtr() const < return stackPtr; >// вернуть размер стека template inline int Stack::getTop() const < return top; >#endif // STACK_H
Шаблон класса Stack реализован в отдельном *.h файле, да, именно реализован, я не ошибся. Все дело в том, что и интерфейс шаблона класса и реализация должны находиться в одном файле, иначе вы увидите список ошибок похожего содержания:
ошибка undefined reference to «метод шаблона класса»
Интерфейс шаблона класса объявлен с 9 по 28 строки. Все методы класса содержат комментарии и, на мой взгляд, описывать их работу отдельно не имеет смысла. Обратите внимание на то, что все методы шаблона класса Стек объявлены как inline функции. Это сделано для того, чтобы ускорить работу класса. Так как встроенные функции класса работают быстрее, чем внешние.
Сразу после интерфейса шаблона идет реализация методов класса Стек, строки 32 — 117. В реализации методов класса ничего сложного нет, если знать как устроен стек, шаблоны и классы. Заметьте, в классе есть два конструктора, первый объявлен в строках 32-33, — это конструктор по умолчанию. А вот конструктор в строках 41-5, — это конструктор копирования.
Он нужен для того, чтобы скопировать один объект в другой. Метод Peek , строки 80 — 88 предоставляет возможность просматривать элементы стека. Необходимо просто ввести номер элемента, отсчет идет от вершины стека. Остальные функции являются служебными, то есть предназначены для использования внутри класса, конечно же кроме функции printStack() , она вывод элементы стека на экран.
Теперь посмотрим на драйвер для нашего стека, под драйвером я подразумеваю программу в которой тестируется работа класса. Как всегда это main функция, в которой мы и будем тестировать наш шаблон класса Stack . Смотрим код ниже:
#include using namespace std; #include «stack.h» int main() < StackstackSymbol(5); int ct = 0; char ch; while (ct++ < 5) < cin >> ch; stackSymbol.push(ch); // помещаем элементы в стек > cout << endl; stackSymbol.printStack(); // печать стека cout << «nnУдалим элемент из стекаn»; stackSymbol.pop(); stackSymbol.printStack(); // печать стека StacknewStack(stackSymbol); cout
Создали объект стека, строка 9, размер стека при этом равен 5, то есть стек может поместить не более 5 элементов. Заполняем стек в цикле while, строки 13 — 17. В строке 21 выводим стек на экран, после удаляем один элемент из стека, строка 24 и снова выводим содержимое стека, поверьте оно изменилось, ровно на один элемент. Смотрим результат работы программы:
CppStudio.com
LOTR! | ! | R | T | O | L Удалим элемент из стека | R | T | O | L Сработал конструктор копирования! | R | T | O | L Второй в очереди элемент: T
В строке 28 мы воспользовались конструктором копирования, о том самом, о котором я писал выше. Не забудем про функцию peek() , давайте посмотри на второй элемент стека, строка 33.
На этом все! Стек у нас получился и исправно работает, попробуйте его протестировать, например на типе данных int . Я уверен, что все останется исправно работать.
Источник: cppstudio.com
Реализация stack в C
Stack — это линейная структура данных который служит набором элементов с тремя основными операциями.
- Push операция, которая добавляет элемент в stack.
- Pop операция, которая удаляет последний добавленный элемент, который еще не был удален, и
- Peek операция, которая возвращает верхний элемент без изменения stack.
The push а также pop операции происходят только на одном конце структуры, называемом top stack. Порядок, в котором элементы выходят из stack, приводит к его альтернативному названию LIFO (от Last-In, First-Out).
Ниже приведено простое представление stack с push а также pop операции:
Stack может быть реализован с ограниченной емкостью. Если stack заполнен и не содержит достаточно места для push операции, то считается, что stack находится в состоянии переполнения.
Реализация stack с использованием массива:
(Ограниченный) стек можно легко реализовать с помощью массива. Первый элемент stack (то есть самый нижний элемент) сохраняется в 0’th index в массиве (при условии индексации с нуля). Второй элемент будет храниться по индексу 1 и т. д. Мы также поддерживаем переменную top чтобы отслеживать размер stack, записывая общее количество элементов, перемещенных до сих пор. Он указывает на место в массиве, куда должен быть вставлен следующий элемент. Таким образом, сам стек может быть эффективно реализован в виде трехэлементной структуры:
structure stack:
maxsize : integer
top : integer
items : array of item
Stack может быть реализован на C следующим образом:
Источник: www.techiedelight.com