Концепция стека
Стек является полезной структурой данных в программировании. Это как стопка тарелок, лежащих друг на друге.
Подумайте о том, что вы можете сделать с такой кучей тарелок:
- Положить новую тарелку сверху;
- Переместить верхнюю тарелку.
Если вы хотите, чтобы тарелка была внизу, необходимо убрать все верхние тарелки. Такая договоренность называется 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.