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