Implementación de pila utilizando una lista vinculada: C, Java y Python

Una stack es un estructura de datos lineal que sirve como una colección de elementos, con tres operaciones principales: empujar, abrir y mirar. Hemos discutido estas operaciones en el Publicación anterior y cubrió una implementación de array de la estructura de datos de stack. En esta publicación, un lista enlazada se discute la implementación de la stack.

Practice this problem

Podemos implementar fácilmente una stack a través de un lista enlazada. En la implementación de listas enlazadas, una stack es un puntero a la "cabeza" de la lista donde suceden los elementos que se empujan y extraen, con tal vez un contador para realizar un seguimiento del tamaño de la lista.

La ventaja de usar una lista enlazada sobre arrays es que es posible implementar una stack que puede crecer o reducirse tanto como sea necesario. El uso de una arrays restringirá la capacidad máxima de la arrays, lo que puede provocar un desbordamiento de la stack. Aquí, cada nuevo nodo se asignará dinámicamente, por lo que no es posible el desbordamiento a menos que se agote la memoria.

La implementación se puede ver a continuación en C, Java y Python:

C

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

#include <stdio.h>

#include <stdlib.h>

// Un nodo de lista enlazada

struct Node

{

int data; // datos enteros

struct Node* next; // puntero al siguiente nodo

};

int nodesCount;

// Función de utilidad para agregar un elemento `x` a la stack

void push(struct Node **top, int x) // insertar al principio

{

// asignar un nuevo nodo en un heap

struct Node* node = NULL;

node = (struct Node*)malloc(sizeof(struct Node));

// comtrie si la stack (heap) está llena. Entonces insertar un elemento sería

// conduce al desbordamiento de la stack

if (!node)

{

printf("Heap Overflow\n");

exit(-1);

}

printf("Inserting %d\n", x);

// establecer datos en el nodo asignado

node->data = x;

// establece el puntero .next del nuevo nodo para que apunte al actual

// nodo superior de la lista

node->next = *top;

// actualiza el puntero superior

*top = node;

// aumenta el tamaño de la stack en 1

nodesCount += 1;

}

// Función de utilidad para verificar si la stack está vacía o no

int isEmpty(struct Node* top) {

return top == NULL;

}

// Función de utilidad para devolver el elemento superior de la stack

int peek(struct Node *top)

{

// comprobar si hay una stack vacía

if (!isEmpty(top)) {

return top->data;

}

else {

printf("The stack is empty\n");

exit(EXIT_FAILURE);

}

// Función de utilidad para sacar un elemento superior de la stack

int pop(struct Node** top) // eliminar al principio

{

struct Node *node;

// comprobar si hay subdesbordamiento de stack

if (*top == NULL)

{

printf("Stack Underflow\n");

exit(EXIT_FAILURE);

}

// tomar nota de los datos del nodo superior

int x = peek(*top);

printf("Removing %d\n", x);

node = *top;

// actualiza el puntero superior para que apunte al siguiente nodo

*top = (*top)->next;

// disminuye el tamaño de la stack en 1

nodesCount -= 1;

// memoria asignada libre

free(node);

return x;

}

// Función de utilidad para devolver el número de nodos de la stack

int size() {

return nodesCount;

}

int main(void)

{

struct Node* top = NULL;

push(&top, 1);

push(&top, 2);

push(&top, 3);

printf("The top element is %d\n", peek(top));

pop(&top);

if (isEmpty(top)) {

printf("The stack is empty\n");

}

else {

printf("The stack is not empty\n");

}

return 0;

}

Descargar Ejecutar código

Java

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

// Un nodo de lista enlazada

class Node

{

int data; // datos enteros

Node next; // puntero al siguiente nodo

}

class Stack

{

private Node top;

private int nodesCount;

public Stack() {

this.top = null;

this.nodesCount = 0;

}

// Función de utilidad para agregar un elemento `x` a la stack

public void push(int x) // insertar al principio

{

// asignar un nuevo nodo en un heap

Node node = new Node();

// comtrie si la stack (heap) está llena. Entonces insertar un elemento sería

// conduce al desbordamiento de la stack

if (node == null)

{

System.out.println("Heap Overflow");

return;

}

System.out.println("Inserting " + x);

// establecer datos en el nodo asignado

node.data = x;

// establece el puntero .next del nuevo nodo para que apunte al actual

// nodo superior de la lista

node.next = top;

// actualiza el puntero superior

top = node;

// aumenta el tamaño de la stack en 1

this.nodesCount += 1;

}

// Función de utilidad para verificar si la stack está vacía o no

public boolean isEmpty() {

return top == null;

}

// Función de utilidad para devolver el elemento superior de la stack

public int peek()

{

// comprobar si hay una stack vacía

if (isEmpty()) {

System.out.println("The stack is empty");

System.exit(-1);

}

return top.data;

}

// Función de utilidad para sacar un elemento superior de la stack

public int pop() // eliminar al principio

{

// comprobar si hay subdesbordamiento de stack

if (isEmpty())

{

System.out.println("Stack Underflow");

System.exit(-1);

}

// tomar nota de los datos del nodo superior

int top = peek();

System.out.println("Removing " + top);

// disminuye el tamaño de la stack en 1

this.nodesCount -= 1;

// actualiza el puntero superior para que apunte al siguiente nodo

this.top = (this.top).next;

return top;

}

// Función de utilidad para devolver el tamaño de la stack

public int size() {

return this.nodesCount;

}

class Main

{

public static void main(String[] args)

{

Stack stack = new Stack();

stack.push(1);

stack.push(2);

stack.push(3);

System.out.println("The top element is " + stack.peek());

stack.pop();

if (stack.isEmpty()) {

System.out.println("The stack is empty");

}

else {

System.out.println("The stack is not empty");

}

Descargar Ejecutar código

Python

# A Nodo de lista enlazada

class Node:

def __init__(self, key, next=None):

self.key = key

self.next = next

class Stack:

def __init__(self):

self.top = None

self.nodesCount = 0

# Función de utilidad para agregar un elemento `x` a la stack

def push(self, x): # Inserto # al principio

# asigna un nuevo nodo en un heap

node = Node(x)

# comtrie si la stack (heap) está llena. Entonces insertar un elemento sería

# conduce a desbordamiento de stack

if node is None:

print('Heap Overflow')

return

# establecer datos en el nodo asignado

node.data = x

# establece el puntero .next del nuevo nodo para que apunte al actual

# nodo superior de la lista

node.next = self.top

# Puntero superior de actualización

self.top = node

# aumenta el tamaño de la stack en 1

self.nodesCount += 1

# Función de utilidad para comprobar si la stack está vacía o no

def isEmpty(self):

return self.top is None

# Función de utilidad para devolver el elemento superior de la stack

def peek(self):

# comtrie si hay una stack vacía

if not self.isEmpty():

return self.top.data

else:

print('The stack is empty')

exit(-1)

# Función de utilidad para sacar un elemento superior de la stack

def pop(self): # eliminar al principio

# comtrie si hay subdesbordamiento de stack

if self.top is None:

print('Stack Underflow')

exit(-1)

# toma nota de los datos del nodo superior

top = self.top.data

# actualiza el puntero superior para apuntar al siguiente nodo

self.top = self.top.next

# reduce el tamaño de la stack en 1

self.nodesCount -= 1

return top

# Función para devolver el tamaño de la stack

def size(self):

return self.nodesCount

if __name__ == '__main__':

stack = Stack()

stack.push(1)

stack.push(2)

stack.push(3)

print('Top element is', stack.peek())

stack.pop()

if stack.isEmpty():

print('The stack is empty')

else:

print('The stack is not empty')

Descargar Ejecutar código

Output:

Inserting 1
Inserting 2
Inserting 3
The top element is 3
Removing 3
Removing 2
Removing 1
The stack is empty

La complejidad temporal de las operaciones push y pop es O(1).

Referencias: https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Implementación de stack usando una lista enlazada: C, Java y Python

C

Java

Python