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

Введение

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

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

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

Ниже приведены основные операции, предоставляемые Stacks.

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

Базовая механика Stacks

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

Затем стек проверяется на пустоту путем сравнения вершины и -1.

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

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

Реализация стека на языке 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, программа выполняет push(). Сначала она проверяет, равен ли top SIZE – 1. Если это так, отображается сообщение “Overflow!!”. В противном случае пользователю предлагается добавить новый элемент в стек.
• Если пользователь выбирает 2, программа обрабатывает метод pop(). Сначала она проверяет, равен ли top значению -1. Если да, выводится сообщение “Underflow!!”. В противном случае верхний элемент удаляется, и программа выводит полученный стек.
• Если пользователь выбирает 3, программа обрабатывает функцию show(). Сначала она проверяет, равен ли top значению -1. Если да, выводится сообщение “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

Затем покажите элементы в Stack():

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

Теперь стек пуст. Попробуйте ещё раз вызвать Pop():

Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 3
Underflow!! Your code... */

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

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

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

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

Результат

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