Cómo implementar una pila en programación en C

Introducción

Una pila es una estructura de datos lineal, una colección de elementos del mismo tipo. En una pila, la inserción y eliminación de elementos ocurre solo en un extremo. El comportamiento de una pila se describe como "último en entrar, primero en salir" (LIFO). Cuando un elemento se inserta en la pila, es el primero en extraerse. Para llegar al elemento insertado más antiguo, es necesario extraer todos los elementos anteriores.

En este artículo, aprenderá sobre el concepto de la estructura de datos de pila y su implementación utilizando matrices en C.

Operaciones realizadas en pilas

A continuación se muestran las operaciones básicas proporcionadas por Stacks.

• push: agrega un elemento a la parte superior de la pila.
• pop: elimina el elemento superior de la pila.
• isEmpty: Comprueba si la pila está vacía.
• isFull: Comprueba si la pila está llena o no.
• superior: muestra el elemento más superior de la pila.

La mecánica subyacente de Stacks

Inicialmente, se establece un puntero (arriba) para rastrear el elemento superior de la pila. La pila se inicializa a -1.

Luego, se verifica que la pila esté vacía comparando top y -1.

A medida que se agregan elementos a la pila, se actualiza la posición superior.

Tan pronto como se extraen o eliminan elementos, se elimina el elemento superior y se actualiza la posición superior.

Implementación de pila en C

Las PILAS se pueden representar utilizando estructuras, punteros, matrices o listas enlazadas.

Este ejemplo implementa pilas usando matrices en 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]);
}
}

Este programa ofrece al usuario cuatro opciones:

• Empujando un elemento
• Hacer estallar un elemento
• Espectáculo
• Fin

Espera a que el usuario ingrese un número.

• Si el usuario selecciona 1, el programa ejecuta una función push(). Primero comprueba si top es igual a SIZE – 1. Si es verdadero, se muestra "¡¡Desbordamiento!!". De lo contrario, se solicita al usuario que proporcione un nuevo elemento para agregarlo a la pila.
• Si el usuario selecciona 2, el programa ejecuta un pop(). Primero comprueba si top es igual a -1. Si es verdadero, se muestra "¡Desbordamiento!". De lo contrario, se elimina el elemento top y el programa muestra la pila resultante.
• Si el usuario selecciona 3, el programa ejecuta show(). Primero comprueba si top es igual a -1. Si es verdadero, se muestra "¡Underflow!!". De lo contrario, el programa muestra la pila resultante.
• Si el usuario selecciona 4, el programa sale.

Ejecute este código para insertar el número “10” en la pila:

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

A continuación muestra los elementos en 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

Luego pop():

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

Ahora la pila está vacía. Prueba Pop() de nuevo:

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... */

Continúe experimentando con este programa para comprender cómo funciona una pila.

Complejidad temporal de las operaciones de pila

Sólo se puede acceder a un elemento a la vez en las pilas.

Al realizar operaciones push() y pop() en la pila, se necesita O(1) tiempo.

Resultado

En este artículo, aprendió sobre el concepto de la estructura de datos de pila y su implementación utilizando matrices en C.