Stack

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

Stack concept

The stack is a useful data structure in programming. It's like a stack of plates stacked on top of each other.

Think about what you can do with such a bunch of plates:

• Put a new plate on top;
• Move the top plate.

If you want the plate to be at the bottom, you must remove all the top plates. This arrangement is called Last In First Out or LIFO (last in, first out) - the last element that is put in is the first element to come out.

Stack in programming conditions

In terms of programming, placing an element on top of the stack is called "push" and removing an element is called "pop". The last element added is called the top of the stack, or "top".

In the image, you can see that element 2 was saved last, but is removed first, as it obeys the LIFO (last in, first out) principle.

We can implement a stack in any programming language like C, C++, Java, Python or C# with almost the same specification.

Stack Specification

A stack is an object, or more specifically an abstract data structure (ADT), that allows you to perform the following operations:

• Push: add an element to the top of the stack;
• Pop: remove an element from the top of the stack;
• IsEmpty: check if the stack is empty;
• IsFull: check if the stack is full;
• Peek: Get the value of the top element without removing it.

How the stack works

Operations work like this:

1. The TOP pointer is called to keep track of the top element on the stack.
2. When initializing the stack, we set its value to -1 so that we can check if the stack is empty by comparing TOP == -1.
3. By clicking on an element, we increment the value of TOP and place the new element at the position pointed to by TOP.
4. When we get an element, we return the element pointed to by TOP and decrement its value.
5. Before adding an element, we check if the stack is full.
6. Before removing an element, we check if the stack is empty.

Implementing a stack in a programming language

The most common implementation of a stack uses arrays, but implementations using lists are also possible.

Here is an implementation using arrays in C.

#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();
}

Using the stack

Although the stack is an easy data structure to implement, it is very useful. The most common uses for the stack are for the following tasks:

• To flip a word - put all the letters in a pile and pull them out. Due to the order of the LIFO stack, you will get the letters in reverse order.
• In compilers - compilers use the stack to calculate the value of expressions such as 2 + 4/5 * (7-9) by converting the expression to prefix or postfix form.
• In browsers - The back button in the browser saves all the URLs you have visited previously in the stack. Each time you visit a new page, it is added to the top of the stack. When you click the back button, the current URL is removed from the stack and the previous URL is opened.