Концепция стека
Стек является полезной структурой данных в программировании. Это как стопка тарелок, лежащих друг на друге.
Подумайте о том, что вы можете сделать с такой кучей тарелок:
- Положить новую тарелку сверху;
- Переместить верхнюю тарелку.
Если вы хотите, чтобы тарелка была внизу, необходимо убрать все верхние тарелки. Такая договоренность называется Last In First Out или LIFO (последний вошел, первый вышел) - последний элемент, который был помещен, является первым элементом, который выйдет.
Стек в условиях программирования
С точки зрения программирования, размещение элемента поверх стека называется «push», а удаление элемента - «pop». Последний добавленный элемент называется верхушкой стека, или «top».
На изображении видно, что элемент 2 был сохранен последним, но удаляется первым, так как подчиняется работе принципа LIFO (последний вошел, первый вышел).
Мы можем реализовать стек на любом языке программирования, таком как C, C ++, Java, Python или C #, почти с одинаковой спецификацией.
Спецификация стека
Стек - это объект или, более конкретно, абстрактная структура данных (ADT), которая позволяет выполнять следующие операции:
- Push: добавить элемент в начало стека;
- Pop: удалить элемент из верхней части стека;
- IsEmpty: проверить, пустой ли стек;
- IsFull: проверьте, заполнен ли стек;
- Peek: получить значение верхнего элемента, не удаляя его.
Как работает стек
Операции работают следующим образом:
- Указатель TOP называется для отслеживания верхнего элемента в стеке.
- При инициализации стека мы устанавливаем его значение -1, чтобы мы могли проверить, является ли стек пустым, сравнивая TOP == -1.
- Нажав на элемент, мы увеличиваем значение TOP и помещаем новый элемент в положение, на которое указывает TOP.
- При получении элемента мы возвращаем элемент, на который указывает TOP, и уменьшаем его значение.
- Перед добавлением элемента мы проверяем, заполнен ли стек.
- Перед удлением элемента мы проверяем, пуст ли стек.
Реализация стека на языке программирования
Наиболее распространенная реализация стека использует массивы, но также возможна реализация с использованием списков.
Вот реализация, использующая массивы на С.
- #include<stdio.h>
- #include<conio.h>
- #include<stdlib.h>
- #define MAX 10
- struct stack
- {
- int items[MAX];
- int top;
- };
- typedef struct stack st;
- void createEmptyStack(st *s)
- {
- s->top=-1;
- }
- int isfull(st *s)
- {
- if (s->top==MAX-1)
- return 1;
- else
- return 0;
- }
- int isempty(st *s)
- {
- if (s->top==-1)
- return 1;
- else
- return 0;
- }
- void push(st *s)
- {
- int newitem;
- printf("Enter item to be inserted: ");
- scanf("%d",&newitem);
- if (isfull(s))
- {
- printf("STACK FULL");
- }
- else
- {
- s->top++;
- s->items[s->top]=newitem;
- }
- }
- void pop (st *s)
- {
- if (isempty(s))
- {
- printf("\n STACK EMPTY \n");
- }
- else
- {
- printf("Item popped= %d",s->items[s->top]);
- s->top--;
- }
- }
- void main()
- {
- int ch;
- int loop;
- loop=1;
- st *s;
- createEmptyStack(s);
- do
- {
- printf("\n ***STACK OPERATIONS");
- printf("\n 1. PUSH");
- printf("\n 2. POP");
- printf("\n 3. EXIT");
- printf("\n ***************");
- printf("\n Enter your choice: ");
- scanf("%d", &ch);
- switch (ch)
- {
- case 1:
- push(s);
- break;
- case 2:
- pop(s);
- break;
- case 3:
- printf("THANK YOU");
- loop=0;
- exit(0);
- default:
- printf("Invalid choice");
- }
- } while(loop);
- getch();
- }
Использование стека
Хотя стек представляет собой простую для реализации структуру данных, он является очень полезным. Наиболее распространенные области использования стека для выполнения следующих задач:
- Чтобы перевернуть слово - сложите все буквы в стопку и вытащите их. Из-за порядка стека LIFO, вы получите буквы в обратном порядке.
- В компиляторах - компиляторы используют стек для вычисления значения выражений, таких как 2 + 4/5 * (7-9), путем преобразования выражения в префиксную или постфиксную форму.
- В браузерах - кнопка «Назад» в браузере сохраняет все URL-адреса, которые вы посетили ранее в стеке. Каждый раз, когда вы посещаете новую страницу, она добавляется в начало стека. Когда вы нажимаете кнопку «Назад», текущий URL удаляется из стека и открывается предыдущий URL.