Стек

Content
Концепция стека

Стек является полезной структурой данных в программировании. Это как стопка тарелок, лежащих друг на друге.

Подумайте о том, что вы можете сделать с такой кучей тарелок:

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

Если вы хотите, чтобы тарелка была внизу, необходимо убрать все верхние тарелки. Такая договоренность называется 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.
We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.

Comments

Only authorized users can post comments.
Please, Log in or Sign up
How to become an author?

Contribute to the evolution of the EVILEG community.

Learn how to become a site author.

Learn it
Donate

Good day, Dear Users!!!

I am Evgenii Legotckoi, developer of EVILEG. And it is my hobby project, which helps to learn programming another programmers and developers

If the site helped you, and you want also support the development of the site, than you can donate by following ways

PayPalYandex.Money
Timeweb

Let me recommend you the excellent hosting on which EVILEG is located.

For many years, Timeweb has been proving his stability.

For projects on Django I recommend VDS hosting

View Hosting Timeweb
MN
May 25, 2020, 11:33 a.m.
Mitja Nagibin

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:50points,
  • Rating points-4
f
May 25, 2020, 5:05 a.m.
falcon

C++ - Test 001. The first program and data types

  • Result:66points,
  • Rating points-1
jm
May 25, 2020, 3:30 a.m.
just maks

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:80points,
  • Rating points4
Last comments
T1
T1
May 26, 2020, 6:22 a.m.
Tima 1

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

полностью повторил структору проекта. В форму дабавил tableView. Но при запуске получаю форму только с пустым tableView. Можете подсказать в чем пробелма?
May 26, 2020, 6:02 a.m.
Evgenij Legotskoj

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

Потому что это файл который нужно создать, а не библиотека. В статье есть содержание этого файла. Добавляйте в проект. Копируйте содержимое из статьи.
T1
May 26, 2020, 6 a.m.
Tima 1

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

не удается подключиить библеотеку include "database.h" выдает ошибку. Можете помочь?
S
May 22, 2020, 10:10 a.m.
Serg7878

Django - Tutorial 013. Contact form based on Django

Спасибо, Евгений. Все заработало. def contacts(request): if request.method == 'POST': form = ContactForm(request.POST) if form.is_valid(): email_subject =…
Now discuss on the forum
May 26, 2020, 5:16 a.m.
BlinCT

Отсутствие драйвера SQLite в пакете Qt 4 на Linux

Вот честно непонимаю почему до сих пор используют qt4, там же столько всего отсутствует, много фишек и возможностей нету там. То есть используя такое старье приходится много писать самому а не и…
DK
May 26, 2020, 2:24 a.m.
Dzhon Kofi

Disable autoscroll

такие естественные решения все перепробовал. Получилось вчера так: const int maximumScroll = ui->_samples->verticalScrollBar()->maximum();const int sliderPos = ui->_samp…
May 26, 2020, 12:43 a.m.
Ruslan Polupan

Посоветуйте новичку (базы данных и Qt, что учить)

Без БД сейчас практически никуда. Поэтому SQL надо знать. SQLite самы простой вариант, но имхо лучще начать с бд клиент-сервер. Настроить сервер. Подключаться клиентом. Просто это помогает понят…
EJ
May 25, 2020, 2:42 p.m.
Esteban José María

Компиляция пустого проекта Qt Android

qt 5.12.8 BUILD SUCCESSFUL in 42s 28 actionable tasks: 28 executed Android package built successfully in 68.251 ms. Ну, буду разбираться по-тихоньку. :)
s
May 25, 2020, 1:24 p.m.
sander-007

Использование файлов в памяти (memory file mapping)

Добрый вечер, проблемы работы с файлом Exel нет вообще. Весь смысл в том чтобы не создавать на диске физический файл (требования безопасности), дабы потом не чистить. А так вопрос только в этом …
About
Services
© EVILEG 2015-2020
Recommend hosting TIMEWEB