Creación de una pila (Stack) en C utilizando arreglos

Antes de crear una pila, te puede interesar:

Creación de una lista simplemente enlazada

¿Qué es una Pila?

Una pila es una estructura de datos lineal que permite acceder y almacenar valores en orden LIFO (Last In First Out, en español: Ultimo en entrar, primero en salir) o FILO (First In Last Out, Primero en entrar, ultimo en salir).

El comportamiento de una esta estructura en programación se asemeja al de una pila de objetos en el mundo real, por ejemplo, una pila de platos o piedras, como puedes ver en el siguiente diagrama:

Diagrama de una pila en programación

Una pila contiene al menos 3 operaciones básicas, todas ellas con una complejidad de O(1):

  • Apilar (PUSH)
  • Desapilar (POP)
  • Ver tope (PEEK)

Comunmente se suele acompañar a estas con algunas otras operaciones:

  • Comprobar si esta vacía
  • Inicializar
  • Mostrar
  • Búsqueda
  • Tamaño

Ejemplos de pilas en software son las operaciones de deshacer/rehacer en editores de texto e imagen, evaluación de expresiones y analisis de sintáxis, entre otros.

Como programar una pila en C

Existen diversas formas de programar una pila en C, siendo las principales mediante el uso de arreglos y listas enlazadas. En este artículo te mostraré como hacerlo mediante los arreglos, mientras que en la segunda parte te mostraré como crear una pila utilizando listas enlazadas.

La estructura de una pila en C es la siguiente:

A esta estructura agregaremos algunas funciones auxiliares más, para instanciar y comprobar cuando este llena/vacía.

A continuación definiremos las funciones principales de la pila, que nos permitirán agregar y eliminar elementos a esta.

Operaciones básicas de la pila

PUSH

Como ya vimos en el diagrama al comienzo de la entrada, la operación de apilar o PUSH, consiste en colocar un elemento en el tope de la pila.

Para lograr esta operación, tan sólo tenemos que colocar el elemento que reciba la función en el siguiente espacio dentro del arreglo:

POP

En el caso de desapilar o POP, tan sólo es necesario hacer lo inverso a la función PUSH, es decir, reducir el tope de la pila y retornar el valor del elemento.

PEEK

La función PEEK() nos permite conocer el elemento que se encuentra en el tope de la pila. Lo podemos implementar fácilmente desapilando un valor y volviendolo a apilar inmediatamente después:

Operaciones complementarias de la pila

Después de implementar PUSH(), POP() y PEEK(), además de las funciones correspondientes para conocer el estado de la pila (llena o vacía) y para crear nuevas pilas, aún nos queda por implementar:

  • Imprimir la pila
  • Buscar un dato en la pila
  • Ver tamaño de la pila

Para imprimir la pila, tan sólo hay que recorrer el arreglo que la conforma e imprimir el elemento almacenado en cada índice. La búsqueda de datos dentro de la pila tiene el mismo principio, pero terminando la función y retornando el índice donde se encuentra el valor a buscar.

Para conocer el tamaño, tan sólo hay que retornar la variable “tope” de nuestra estructura.

Finalmente, un ejemplo de uso de las funciones implementadas:

La creación de una pila utilizando arreglos es una forma sencilla de implementar esta estructura de datos, sin embargo, presenta algunas desventajas frente a la creación de una pila mediante una lista enlazada, siendo una de ellas su limitado tamaño. En la siguiente parte de esta entrada te mostraré como diseñar una pila y sus operaciones básicas utilizando punteros y nodos enlazados.

Fuente parcial: Geeks for geeks

Archivo en Github

Share Post :

More Posts