Стек

алгоритм, стек, сортировка

Концепція стека

Стек є корисною структурою даних у програмуванні. Це як стос тарілок, що лежать один на одному.

Подумайте про те, що ви можете зробити з такою купою тарілок:

• Покласти нову тарілку зверху;
• Перемістити верхню тарілку.

Якщо ви бажаєте, щоб тарілка була внизу, необхідно прибрати всі верхні тарілки. Така домовленість називається Last In First Out або LIFO (останній увійшов, перший вийшов) - останній елемент, який був розміщений, є першим елементом, який вийде.

Стек в умовах програмування

З погляду програмування, розміщення елемента поверх стека називається "push", а видалення елемента - "pop". Останній доданий елемент називається верхівкою стека, або top.

На зображенні видно, що елемент 2 був збережений останнім, але видаляється першим, тому що підкоряється роботі принципу LIFO (останній увійшов, вийшов перший).

Ми можемо реалізувати стек будь-якою мовою програмування, такою як C, C++, Java, Python або C#, майже з однаковою специфікацією.

Специфікація стека

Стек - це об'єкт або, конкретніше, абстрактна структура даних (ADT), яка дозволяє виконувати наступні операції:

• Push: додати елемент на початок стека;
• Pop: видалити елемент із верхньої частини стека;
• IsEmpty: перевірити, чи порожній стек;
• IsFull: перевірте, чи заповнений стек;
• Peek: отримати значення верхнього елемента, не видаляючи його.

Як працює стек

Операції працюють таким чином:

1. Вказівник TOP називається для відстеження верхнього елемента у стеку.
2. При ініціалізації стека ми встановлюємо його значення -1, щоб ми могли перевірити, чи стек є порожнім, порівнюючи TOP == -1.
3. Натиснувши на елемент, ми збільшуємо значення TOP і поміщаємо новий елемент у положення, яке вказує TOP.
4. При отриманні елемента ми повертаємо елемент, який вказує TOP, і зменшуємо його значення.
5. Перед додаванням елемента ми перевіряємо, чи заповнений стек.
6. Перед подовженням елемента ми перевіряємо, чи стек пустий.

Реалізація стека мовою програмування

Найбільш поширена реалізація стека використовує масиви, але можлива реалізація з використанням списків.

Ось реалізація, що використовує масиви С.

#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-адреса.