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