Privacy policyContactsAbout siteOpinionsGitHubDonate
© EVILEG 2015-2018
Recommend hosting
TIMEWEB

Стек

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

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

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

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

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

Если вы хотите, чтобы тарелка была внизу, необходимо убрать все верхние тарелки. Такая договоренность называется 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.
10% refund of hotel reservation amount on Booking
10% refund of hotel reservation amount on Booking
We offer a link with a 10% return on the amount of the order when booking a hotel through Booking

Comments

Only authorized users can post comments.
Please, Log in or Sign up
IT
March 25, 2019, 5:32 p.m.
Ilya The Engineer

Qt - Test 001. Signals and slots

  • Result:5points,
  • Rating points-10
G
March 25, 2019, 8:34 a.m.
GAG

C++ - Test 002. Constants

  • Result:41points,
  • Rating points-8
G
March 25, 2019, 8:25 a.m.
GAG

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

  • Result:66points,
  • Rating points-1
Last comments
March 26, 2019, 8:49 a.m.
Евгений Легоцкой

Да Да Да. Я тоже сейчас вспомнил, что проблема -R в том, что права и для файлов и для каталогов устанавливаются. А для веб-серверов нужно, чтобы права на каталоги были 755, а на файлы 64...
March 26, 2019, 8:47 a.m.
Ruslan Polupan

Был не прав....Почитал маны, флаг «выполнения» по-разному действует на файлы и каталоги.Правильно так chmod -R go=rX,u=rwX /path/to/target/dir
March 26, 2019, 8:35 a.m.
Евгений Легоцкой

По моему, только эта директория /path/to/target/dir и получит эти права, а все остальные вложенные остануться с тем, с чем были. UPD: Или я что-то жёстко путаю? ))) Надо переп...
March 26, 2019, 8:18 a.m.
Ruslan Polupan

А если так chmod -R 755 /path/to/target/dir
March 22, 2019, 12:32 p.m.
Евгений Легоцкой

Ну может бибилотеки не те положили? У вас сборка для MinGW, а либы для MSVC.
Now discuss on the forum
March 26, 2019, 12:07 p.m.
Евгений Легоцкой

Пожалуйста, не загружайте сейчас никакие изображения, это сейчас не работает. Вечером исправлю, остались ошибки на сервере после его переезда.
U
March 25, 2019, 12:43 p.m.
Unreal_man

Как сделать чтоб при клике на ячейку(ос андроид) ее сразу можно было редактировать?QGuiApplication::inputMethod()->show(); показывает клавиатуру, а вот что до этого прописать чтоб текст в ...
m
March 24, 2019, 10:36 a.m.
monevich

Отвечу на свой же вопрос, может кому то это пригодится. Да, можно в функции main использовать такую конструкцию. При запуске программы из Qt передаю свой аргумент в параметрах командной строк...
March 22, 2019, 12:29 p.m.
Дмитрий

Да, мьютекс добавил, но в том потоке, где сигнал вызывается.
Join us in social networks

For registered users on the site there is a minimum amount of advertising