Стек
С тек – наверное, самая простая структура данных, которую мы будем изучать и которой будем постоянно пользоваться. Стек – это структура данных, в которой элементы поддерживают принцип 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 – это количество элементов, и вместе с тем указатель на вершину стека. Вершина будет указывать на следующий элемент массива, в который будет занесено значение.
Кладём новый элемент на стек.
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(&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()
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[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(&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
Эта однопоточная реализация стека использует мало обращений к памяти, достаточно проста и универсальна, работает быстро и может быть реализована, при необходимости, за несколько минут. Она используется всегда в дальнейшем, если не указано иное.
У неё есть недостаток, связанный с методом увеличения потребляемой памяти. При умножении в 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(&head, i); >printf("size = %d\n", getSize(head)); while (head) < printf("%d ", peek(head)); printf("%d ", pop2(&head)); >_getch(); >
void main() < int i; Node_t *head = NULL; Node_t *tmp; for (i = 0; i < 300; i++) < push(&head, i); >printf("size = %d\n", getSize(head)); while (head) < printf("%d ", peek(head)); tmp = pop1(&head); printf("%d ", tmp->value); free(tmp); > _getch(); >
ru-Cyrl 18- tutorial Sypachev S.S. 1989-04-14 sypachev_s_s@mail.ru Stepan Sypachev students
Всё ещё не понятно? – пиши вопросы на ящик
О стеке простыми словами — для студентов и просто начинающих
Привет, я студент второго курса технического университета. После пропуска нескольких пар программирования по состоянию здоровья, я столкнулся с непониманием таких тем, как «Стек» и «Очередь». Путем проб и ошибок, спустя несколько дней, до меня наконец дошло, что это такое и с чем это едят. Чтобы у вас понимание не заняло столько времени, в данной статье я расскажу о том что такое «Стек», каким образом и на каких примерах я понял что это такое. Если вам понравится, я напишу вторую часть, которая будет затрагивать уже такое понятие, как «Очередь»
Теория
На Википедии определение стека звучит так:
Стек (англ. stack — стопка; читается стэк) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Достаточно полное определение, но возможно для новичков оно будет немного трудным для понимания.
Поэтому первое, на чем бы я хотел заострить внимание, это представление стека в виде вещей из жизни. Первой на ум мне пришла интерпретация в виде стопки книг, где верхняя книга — это вершина.
На самом деле стек можно представить в виде стопки любых предметов будь то стопка листов, тетрадей, рубашек и тому подобное, но пример с книгами я думаю будет самым оптимальным.
Итак, из чего же состоит стек.
Стек состоит из ячеек(в примере — это книги), которые представлены в виде структуры, содержащей какие-либо данные и указатель типа данной структуры на следующий элемент.
Сложно? Не беда, давайте разбираться.
На данной картинке схематично изображен стек. Блок вида «Данные/*next» и есть наша ячейка. *next, как мы видим, указывает на следующий элемент, другими словами указатель *next хранит адрес следующей ячейки. Указатель *TOP указывает на вершину стек, то есть хранит её адрес.
С теорией закончили, перейдем к практике.
Практика
Для начала нам нужно создать структуру, которая будет являться нашей «ячейкой»
Код на C++
struct comp < //Структура с названием comp(от слова component) int Data; //Какие-то данные(могут быть любыми, к примеру можно написать int key; char Data; так-же можно добавить еще какие-либо данные) comp *next;//Указатель типа comp на следующий элемент >; Новичкам возможно будет не понятно, зачем наш указатель — типа comp, точнее сказать указатель типа структуры comp. Объясню, для того чтобы указатель *next мог хранить структуру comp, ей нужно обозначить тип этой структуры. Другими словами указать, что будет хранить указатель.
После того как у нас задана «Ячейка», перейдем к созданию функций.
Функции
Функция создания «Стека»/добавления элемента в «Стек»
При добавлении элемента у нас возникнет две ситуации:
- Стек пуст, и нужно создать его
- Стек уже есть и нужно лишь добавить в него новый элемент
Код на C++
void s_push(comp **top, int D) < //функция типа void(ничего не возвращает) которая принимает указатль на вершину стека и переменную которая будет записываться в ячейку comp *q; //Создаем новый указатель q типа структуры comp. По сути это и есть наш новый элемент q = new comp(); //выделяем память для нового элемента q->Data = D; //Записываем необходимое число в Data элемента if (top == NULL) < //Если вершины нет, то есть стек пустой *top = q; //вершиной стека будет новый элемент >else //если стек не пустой < q->next = *top; //Проводим связь от нового элемента, к вершине. Тоесть кладем книжку на вершину стопки. *top = q; //Обозначаем, что вершиной теперь является новый элемент > > Разберем чуть чуть по-подробнее.
Во-первых, почему функция принимает **top, то есть указатель на указатель, для того чтобы вам было наиболее понятно, я оставлю рассмотрение этого вопроса на потом. Во-вторых, по-подробнее поговорим о q->next = *top и о том, что же означает ->.
-> означает то, что грубо говоря, мы заходим в нашу структуру и достаем оттуда элемент этой структуры. В строчке q->next = *top мы из нашей ячейки достаем указатель на следующий элемент *next и заменяем его на указатель, который указывает на вершину стека *top. Другими словами мы проводим связь, от нового элемента к вершине стека. Тут ничего сложного, все как с книгами. Новую книгу мы кладем ровно на вершину стопки, то есть проводим связь от новой книги к вершине стопки книг. После этого новая книга автоматически становится вершиной, так как стек не стопка книг, нам нужно указать, что новый элемент — вершина, для этого пишется: *top = q;.
Функция удаления элемента из «Стека» по данным
Данная функция будет удалять элемент из стека, если число Data ячейки(q->Data) будет равна числу, которое мы сами обозначим.
Здесь могут быть такие варианты:
- Ячейка, которую нам нужно удалить является вершиной стека
- Ячейка, которую нам нужно удалить находится в конце, либо между двумя ячейками
Код на C++
void s_delete_key(comp **top, int N) Data == N) next;//передвигаем вершину на следующий элемент free(q);//очищаем ячейку q->Data = NULL; //Далее во избежание ошибок мы обнуляем переменные в удаленной ячейке, так как в некоторых компиляторах удаленная ячейка имеет переменные не NULL значения, а дословно "Чтение памяти невозможно" или числа "-2738568384" или другие, в зависимости от компилятора. q->next = NULL; > else//если элемент последний или находится между двумя другими элементами < prev->next = q->next;//Проводим связь от предыдущего элемента к следующему free(q);//очищаем ячейку q->Data = NULL;//обнуляем переменные q->next = NULL; > >// если Data элемента НЕ равна числу, которое нам нужно удалить prev = q; //запоминаем текущую ячейку как предыдущую q = q->next;//перемещаем указатель q на следующий элемент > > Указатель q в данном случае играет такую же роль, что и указатель в блокноте, он бегает по всему стеку, пока не станет равным NULL(while(q != NULL)), другими словами, пока стек не закончится.
Для лучшего понимания удаления элемента проведем аналогии с уже привычной стопкой книг. Если нам нужно убрать книгу сверху, мы её убираем, а книга под ней становится верхней. Тут то же самое, только в начале мы должны определить, что следующий элемент станет вершиной *top = q->next; и только потом удалить элемент free(q);
Если книга, которую нужно убрать находится между двумя книгами или между книгой и столом, предыдущая книга ляжет на следующую или на стол. Как мы уже поняли, книга у нас-это ячейка, а стол получается это NULL, то есть следующего элемента нет. Получается так же как с книгами, мы обозначаем, что предыдущая ячейка будет связана с последующей prev->next = q->next;, стоит отметить что prev->next может равняться как ячейке, так и нулю, в случае если q->next = NULL, то есть ячейки нет(книга ляжет на стол), после этого мы очищаем ячейку free(q).
Так же стоит отметить, что если не провести данную связь, участок ячеек, который лежит после удаленной ячейки станет недоступным, так как потеряется та самая связь, которая соединяет одну ячейку с другой и данный участок просто затеряется в памяти
Функция вывода данных стека на экран
Самая простая функция:
Код на C++
void s_print(comp *top) < //принимает указатель на вершину стека comp *q = top; //устанавливаем q на вершину while (q) < //пока q не пустой (while(q) эквивалентно while(q != NULL)) printf_s("%i", q->Data);//выводим на экран данные ячейки стека q = q->next;//после того как вывели передвигаем q на следующий элемент(ячейку) > > Здесь я думаю все понятно, хочу сказать лишь то, что q нужно воспринимать как бегунок, он бегает по всем ячейкам от вершины, куда мы его установили вначале: *q = top;, до последнего элемента.
Главная функция
Хорошо, основные функции по работе со стеком мы записали, вызываем.
Посмотрим код:
Код на C++
void main() < comp *top = NULL; //в начале программы у нас нет очереди, соответственно вершины нет, даем ей значение NULL //Дальше начинаем добавлять цифры от 1 до 5 в наш стек s_push(&top, 1); s_push(&top, 2); s_push(&top, 3); s_push(&top, 4); s_push(&top, 5); //после выполнения функций в стеке у нас будет 54321 s_print(top);//выводим s_delete_key(&top, 4); //Затем удаляем 4, в стеке получается 5321 printf_s("\n");//переводим на новую строку s_print(top);//выводим system("pause");//ставим на паузу >Вернемся к тому, почему же в функцию мы передавали указатель на указатель вершины. Дело в том, что если бы мы ввели в функцию только указатель на вершину, то «Стек» создавался и изменялся только внутри функции, в главной функции вершина бы как была, так и оставалась NULL. Передавая указатель на указатель мы изменяем вершину *top в главной функции. Получается если функция изменяет стек, нужно передавать в нее вершину указателем на указатель, так у нас было в функции s_push,s_delete_key. В функции s_print «Стек» не должен изменяться, поэтому мы передаем просто указатель на вершину.
Вместо цифр 1,2,3,4,5 можно так-же использовать переменные типа int.
Заключение
Полный код программы:
Код на C++
#include ; #include ; struct comp < //Структура с именем comp int Data; //Кикие то данные(могут быть любими, к примеру можно написать int key; char Data; или добавить еще какие то данные) comp *next;//Указатель типа comp на следующий эелемент >; void s_push(comp **top, int D) < //функция типа void(ничего не возвращает) которая принимает указатль на вершину стека и переменную которая будет записываться в ячейку comp *q; //Создаем новый указатель q, который приравниваем к вершине стека. По сути это и есть наш новый элемент q = new comp(); //выделяем память для нового элемента q->Data = D; //Записываем D в Data элемента if (top == NULL) < //Если вершины нет, тоесть стек пустой *top = q; //вершиной стека будет новый элемент >else //если стек не пустой < q->next = *top; //Проводим связь от нового элемента, к вершине. Тоесть кладем книжку на вершину стопки. *top = q; //Пишем, что вершиной теперь является новый элемент > > void s_delete_key(comp **top, int N) Data == N) next;//передвигаем вершину на следующий элемент free(q);//очищаем ячейку q->Data = NULL; //Далее во избежание ошибок мы обнуляем переменные в удаленной ячейке, так как в некоторых компиляторах удаленная ячейка имеет переменные не NULL значения, а дословно "Чение памяти невозможно" или числа "-2738568384" или других, в зависимости от компилятора. q->next = NULL; > else//если элемент последний или находится между двумя другими элементами < prev->next = q->next;//Проводим связь от предыдущего элемента к следующему free(q);//очищаем ячейку q->Data = NULL;//обнуляем переменные q->next = NULL; > >// если Data элемента НЕ равна числу, которое нам нужно удалить prev = q; //запоминаем текущую ячейку как предыдущую q = q->next;//перемещаем указатель q на следующий элемент > > void s_print(comp *top) < //принимает указатель на вершину стека comp *q = top; //устанавливаем q на вершину while (q) < //пока q не пустой (while(q) эквивалентно while(q != NULL)) printf_s("%i", q->Data);//выводим на экран данные ячейки стека q = q->next;//после того как вывели передвигаем q на следующий элемент(ячейку) > > void main() < comp *top = NULL; //в начале программы у нас нет очереди, соответственно вершины нет, даем ей значение NULL //Дальше начинаем добавлять цифры от 1 до 5 в наш стек s_push(&top, 1); s_push(&top, 2); s_push(&top, 3); s_push(&top, 4); s_push(&top, 5); //после выполнения функций в стеке у нас будет 54321 s_print(top);//выводим s_delete_key(&top, 4); //Затем удаляем 4, в стеке получается 5321 printf_s("\n");//переводим на новую строку s_print(top);//выводим system("pause");//ставим на паузу >54321
5321
Так как в стек элементы постоянно добавляются на вершину, выводиться элементы будут в обратном порядке
В заключение хотелось бы поблагодарить за уделенное моей статье время, я очень надеюсь что данный материал помог некоторым начинающим программистам понять, что такое «Стек», как им пользоваться и в дальнейшем у них больше не возникнет проблем. Пишите в комментариях свое мнение, а так же о том, как мне улучшить свои статьи в будущем. Спасибо за внимание.
Стек
Стек (от англ. stack — стопка) — структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел — первым вышел» (last-in, first-out — LIFO). Примером стека в реальной жизни может являться стопка тарелок: когда мы хотим вытащить тарелку, мы должны снять все тарелки выше. Вернемся к описанию операций стека:
- [math] \mathtt [/math] — проверка стека на наличие в нем элементов,
- [math] \mathtt [/math] (запись в стек) — операция вставки нового элемента,
- [math] \mathtt [/math] (снятие со стека) — операция удаления нового элемента.
Реализации
Для стека с [math]n[/math] элементами требуется [math]O(n)[/math] памяти, так как она нужна лишь для хранения самих элементов.
На массиве
Перед реализацией стека выделим ключевые поля:
- [math]\mathtt
- [math]\mathtt[/math] — индекс последнего помещенного в стек элемента.
Стек состоит из элементов [math]\mathtt
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
boolean empty(): return s.top == 0
function push(element : T): s.top = s.top + 1 s[s.top] = element
T pop(): if empty() return error "underflow" else s.top = s.top - 1 return s[s.top + 1]
Как видно из псевдокода выше, все операции со стеком выполняются за [math]O(1)[/math] .
На саморасширяющемся массиве
Возможна реализация стека на динамическом массиве, в результате чего появляется существенное преимущество над обычной реализацией: при операции push мы никогда не сможем выйти за границы массива, тем самым избежим ошибки исполнения.
Создадим вектор и определим операции стека на нём. В функции [math] \mathtt [/math] Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в [math] \mathtt [/math] , перед тем, как изъять элемент из массива, — не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.
- [math]\mathtt
- [math]\mathtt
- [math]\mathtt[/math] — верхушка стека,
- [math]\mathtt[/math] — размер массива.
function push(element : T): if head == capacity - 1 T newStack[capacity * 2] for i = 0 to capacity - 1 newStack[i] = s[i] s = newStack capacity = capacity * 2 head++ s[head] = element
T pop(): temp = s[head] head-- if head < capacity / 4 T newStack[capacity / 2] for i = 0 to capacity / 4 - 1 newStack[i] = s[i] s = newStack capacity = capacity / 2 return temp
На списке
Стек можно реализовать и на списке. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем «держать» за голову. Добавляться новые элементы посредством операции [math] \mathtt [/math] будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью [math] \mathtt [/math] будет текущая голова. После вызова функции [math] \mathtt [/math] текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции [math] \mathtt [/math] будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.
Заведем конструктор вида ListItem(next : ListItem, data : T)
- [math]\mathtt[/math] — значение в верхушке стека,
- [math]\mathtt[/math] — значение следующее за верхушкой стека.
function push(element : T): head = ListItem(head, element)
T pop(): data = head.data head = head.next return data
В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же [math]\mathtt[/math] . Стоит заметить, что стек требует [math]O(n)[/math] дополнительной памяти на указатели в списке.
См. также
Источники информации
- Википедия — Стек
- Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10
- T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1
- Динамические структуры данных: стеки
Стек
Стеком называется упорядоченный набор элементов, в котором размещение новых и удаление существующих происходит с одного конца, называемого вершиной .
Дисциплина обслуживания — это совокупность правил (упорядочение и алгоритм) обслуживания элементов динамической структуры данных.
В зависимости от дисциплины обслуживания различают те или иные структуры динамических данных.
Принцип работы стека сравнивают со стопкой листов бумаги: чтобы взять второй сверху, нужно снять верхний.
В стеке реализуется дисциплина обслуживания LIFO:
Различают аппаратный и программный стек.
Аппаратный стек используется для хранения адресов возврата из функций и их аргументов.
Программный стек – это пользовательская модель (структура) данных.
Операции для работы со стеком
Над стеком реализованы следующие операции:
- инициализация стека init(s) , где s — стек
- помещение элемента в стек push(s, i) , где s — стек, i — помещаемый элемент;
- удаление элемента из стека i=pop(s);
- получение верхнего элемента стека без его удаления i=stkTop(s) , где s — стек
- получение количества элементов стека
- определение, пуст ли стек isempty(s) возвращает 1 если стек пустой и 0 в противном случае.
- вывод элементов стека stkPrint(s) , где s — стек
Способы реализации стека
Существует несколько способов реализации стека:
- с помощью одномерного массива;
- с помощью связанного списка;
- с помощью класса объектно-ориентированного программирования.
Пример реализации стека с помощью одномерного массива
Стек можно реализовать в виде следующей структуры:
#define NMAX 100
struct stack float elem[NMAX];
int top;
>;
NMAX — максимальное количество элементов в стеке;
elem — массив из NMAX чисел типа float , предназначенный для хранения элементов стека;
top — индекс элемента, находящегося в вершине стека.
Инициализация стека
Индекс элемента, находящегося в вершине стека, равен 0.
void init( struct stack *stk) <
stk->top = 0;
>
Помещение элемента в стек
В элемент массива с индексом top записывается значение f . После этого вершина стека, соответствующая количеству элементов в массиве, перемещается на 1 элемент влево.
void push( struct stack *stk, float f) <
if (stk->top < NMAX) <
stk->elem[stk->top] = f;
stk->top++;
> else
printf( «Стек полон, количество элементов: %d !\n» , stk->top);
>
Удаление элемента из стека
Если в массиве, соответствующем стеку, есть элементы, то количество элементов уменьшается на 1. После этого возвращается последний элемент.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
float pop( struct stack *stk) <
float elem;
if ((stk->top) > 0)
<
stk->top—;
elem = stk->elem[stk->top];
return elem;
>
else
<
printf( «Стек пуст!\n» );
return 0;
>
>
Получение верхнего элемента стека без его удаления
float stkTop( struct stack *stk) <
if ((stk->top) > 0) <
return stk->elem[stk->top-1];
> else <
printf( «Стек пуст!\n» );
return 0;
>
>
Получение количества элементов стека
int getcount( struct stack *stk) <
return stk->top;
>
Определение, пуст ли стек
Если количество элементов в стеке равно 0, то стек пуст (возвращается 1).
int isempty( struct stack *stk) <
if (stk->top == 0) return 1;
else return 0;
>
Вывод элементов стека
Если стек не пуст, движемся от последнего элемента к началу массива с выводом элементов.
void stkPrint( struct stack *stk) <
int i;
i=stk->top; // i — количество элементов в стеке
if (isempty(stk) == 1) return ; // стек пуст
do <
i—;
printf( «%f\n» , stk->elem[i]);
> while (i>0);
>
Пример
Создать стек из n элементов и извлечь их из стека.
Примечание: для успешной компиляции примера необходимо добавить в код программы все функции работы со стеком, описанные выше на этой странице в порядке их рассмотрения. И не забыть подключить библиотеки stdio.h, stdlib.h .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main() <
struct stack *stk;
int i,n;
float elem;
stk = ( struct stack*)malloc( sizeof ( struct stack));
init(stk);
printf( «Введите количество элементов в стеке: » );
scanf( «%d» , &n);
for (i=0; i printf( «Введите элемент %d:» , i);
scanf( «%f» , &elem);
push(stk,elem);
>
printf( «В стеке %d элементов\n\n» , getcount(stk));
stkPrint(stk);
printf( «Верхний элемент %f\n» ,stkTop(stk));
do <
printf( «Извлекаем элемент %f, » , pop(stk));
printf( «в стеке осталось %d элементов\n» , getcount(stk));
> while (isempty(stk) == 0);
getchar(); getchar();
return 0;
>
Результат выполнения
Пример
Перевести введенное число в систему счисления с заданным основанием.
Деление числа на основание системы счисления производится до тех пор, пока в частном не получится 0.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main() <
struct stack *stk;
int n, value;
stk = ( struct stack*)malloc( sizeof ( struct stack));
init(stk);
printf( «Введите число: » );
scanf( «%d» , &value);
printf( «Введите основание: » );
scanf( «%d» , &n);
do <
push(stk, value%n);
value = value /n;
> while (value > 0);
do <
printf( «%x» ,pop(stk)); // вывод цифры (включая цифры A. F шестнадцатеричной системы счисления
> while (isempty(stk)==0);
getchar(); getchar();
return 0;
>
Результат выполнения