Как реализовать стек в программировании на C

Введение

Стек — это линейная структура данных, набор элементов одного типа.

В стеке вставка и удаление элементов происходит только в одной конечной точке. Поведение стека описывается как «последний пришел, первый ушел» (LIFO). Когда элемент «вталкивается» в стек, он становится первым элементом, который будет «вытолкнут» из стека. Чтобы добраться до самого старого введенного элемента, вы должны вытолкнуть все предыдущие элементы.

В этой статье вы узнаете о концепции стековой структуры данных и ее реализации с использованием массивов в C.

Операции, выполняемые над стеками

Ниже приведены основные операции, обслуживаемые стеками.

• push: добавляет элемент на вершину стека.
• pop: удаляет самый верхний элемент из стека.
• isEmpty: проверяет, пуст ли стек.
• isFull: проверяет, заполнен ли стек.
• top: отображает самый верхний элемент стека.

Основная механика стеков

Первоначально указатель (top) устанавливается для отслеживания самого верхнего элемента в стеке. Стек инициализируется значением -1.

Затем выполняется проверка, чтобы определить, пуст ли стек, путем сравнения top с -1.

По мере добавления элементов в стек позиция top обновляется.

Как только элементы извлекаются или удаляются, самый верхний элемент удаляется, а позиция top обновляется.

Реализация стека в C

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

Этот пример реализует стеки с использованием массивов в C:

#include <stdio.h>

#include <stdlib.h>

#define SIZE 4

int top = -1, inp_array[SIZE];
void push();
void pop();
void show();

int main()
{
    int choice;

    while (1)
    {
        printf("\nPerform operations on the stack:");
        printf("\n1.Push the element\n2.Pop the element\n3.Show\n4.End");
        printf("\n\nEnter the choice: ");
        scanf("%d", &choice);

        switch (choice)
        {
        case 1:
            push();
            break;
        case 2:
            pop();
            break;
        case 3:
            show();
            break;
        case 4:
            exit(0);

        default:
            printf("\nInvalid choice!!");
        }
    }
}

void push()
{
    int x;

    if (top == SIZE - 1)
    {
        printf("\nOverflow!!");
    }
    else
    {
        printf("\nEnter the element to be added onto the stack: ");
        scanf("%d", &x);
        top = top + 1;
        inp_array[top] = x;
    }
}

void pop()
{
    if (top == -1)
    {
        printf("\nUnderflow!!");
    }
    else
    {
        printf("\nPopped element: %d", inp_array[top]);
        top = top - 1;
    }
}

void show()
{
    if (top == -1)
    {
        printf("\nUnderflow!!");
    }
    else
    {
        printf("\nElements present in the stack: \n");
        for (int i = top; i >= 0; --i)
            printf("%d\n", inp_array[i]);
    }
}

Эта программа предоставляет пользователю четыре варианта:

1. Отправить элемент
2. Выделить элемент
3. Показать
4. Конец

Он ждет, пока пользователь введет число.

• Если пользователь выбирает 1, программа обрабатывает push(). Во-первых, он проверяет, эквивалентен ли top SIZE - 1. Если true, отображается Переполнение!!. В противном случае пользователю предлагается указать новый элемент для добавления в стек.
• Если пользователь выбирает 2, программа обрабатывает pop(). Во-первых, он проверяет, эквивалентен ли top -1. Если true, отображается Underflow!!. В противном случае самый верхний элемент удаляется, и программа выводит результирующий стек.
• Если пользователь выбирает 3, программа обрабатывает show(). Во-первых, он проверяет, эквивалентен ли top -1. Если true, отображается Underflow!!. В противном случае программа выводит результирующий стек.
• Если пользователь выбирает 4, программа закрывается.

Выполните этот код, чтобы push() число 10в стек:

Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End

Enter the choice: 1

Enter the element to be inserted onto the stack: 10

Затем show() элементы в стеке:

Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End

Enter the choice: 3

Elements present in the stack: 
10

Затем pop():

Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End

Enter the choice: 2
Popped element: 10

Теперь стек пуст. Повторите попытку pop():

Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End

Enter the choice: 3
Underflow!!

Продолжайте экспериментировать с этой программой, чтобы понять, как работает стек.

Временная сложность операций стека

В стеках одновременно можно получить доступ только к одному элементу.

Выполнение операций push() и pop() в стеке занимает O(1) время.

Заключение

В этой статье вы узнали о концепции стековой структуры данных и ее реализации с использованием массивов в C.

Стек используется для решения нескольких общих проблем, таких как:

1. Ханойская башня
2. Задача N-ферзей
3. Преобразование инфикса в префикс

Продолжите свое обучение с Как инициализировать массив в C.