Implementación de lista enlazada de stack

En lugar de usar array, también podemos usar lista enlazada para implementar stack. La lista vinculada asigna la memoria dinámicamente. Sin embargo, la complejidad de tiempo en ambos escenarios es la misma para todas las operaciones, es decir, push, pop y peek.

En la implementación de lista vinculada de pila, los nodos se mantienen de forma no contigua en la memoria. Cada nodo contiene un puntero a su nodo sucesor inmediato en la pila. Se dice que la pila está desbordada si el espacio que queda en el montón de memoria no es suficiente para crear un nodo.

El nodo superior de la pila siempre contiene null en su campo de dirección. Vamos a discutir la forma en que, cada operación se realiza en la implementación de lista vinculada de pila.

Agregar un nodo a la pila (operación push)

Agregar un nodo a la pila se conoce como operación push. Empujar un elemento a una pila en una implementación de lista vinculada es diferente a la de una implementación de matriz. Para empujar un elemento a la pila, se deben seguir los siguientes pasos.

1. Cree primero un nodo y asigne memoria a él.
2. Si la lista está vacía, el elemento se empujará como nodo de inicio de la lista. Esto incluye asignar valor a la parte de datos del nodo y asignar null a la parte de dirección del nodo.
3. Si ya hay algunos nodos en la lista, entonces tenemos que agregar el nuevo elemento al principio de la lista (para no violar la propiedad de la pila). Para ello, asigne la dirección del elemento inicial al campo de dirección del nuevo nodo y convierta el nuevo nodo en el nodo inicial de la lista.

Complejidad temporal: o(1)



Implementación de C:

Eliminar un nodo de la pila (operación POP)

Eliminar un nodo de la parte superior de la pila se denomina operación pop. Eliminar un nodo de la implementación de la lista vinculada de la pila es diferente de la implementación de la matriz. En fin pop un elemento de la pila, necesitamos seguir los siguientes pasos :

1. Comprobar el subdesbordamiento condición: La de subdesbordamiento de la condición se produce cuando tratamos de pop, que ya pila vacía. La pila estará vacía si el puntero principal de la lista apunta a null.
2. Ajuste el puntero de cabeza en consecuencia: En la pila, los elementos se abren solo desde un extremo, por lo tanto, el valor almacenado en el puntero de cabeza debe eliminarse y el nodo debe liberarse. El siguiente nodo del nodo principal ahora se convierte en el nodo principal.

Complejidad temporal : o (n)

Implementación de C

Mostrar los nodos (Atravesando)

Mostrar todos los nodos de una pila necesita atravesar todos los nodos de la lista vinculada organizados en forma de pila. Para ello, debemos seguir los siguientes pasos.

1. Copie el puntero principal en un puntero temporal.
2. Mueva el puntero temporal a través de todos los nodos de la lista e imprima el campo de valor adjunto a cada nodo.

Complejidad temporal : o (n)

Implementación en C

Programa controlado por menú en C implementando todas las operaciones de pila utilizando una lista vinculada: