Para implementar una pila utilizando el concepto de lista de enlace único, todas las operaciones de lista de enlace único se realizan en función de las operaciones de pila LIFO (último en entrar, primero en salir) y con la ayuda de ese conocimiento vamos a implementar una pila utilizando lista de enlace único. Usando listas enlazadas individualmente, implementamos la pila almacenando la información en forma de Nodes y necesitamos seguir las reglas de la pila e implementar usando Nodes de lista enlazada individualmente. Por lo tanto, debemos seguir una regla simple en la implementación de una pila que es el último en entrar, primero en salir y todas las operaciones se pueden realizar con la ayuda de una variable superior. Aprendamos cómo realizar operaciones Pop, Push, Peek, Display en el siguiente artículo.
Una pila se puede implementar fácilmente usando la lista enlazada. En la implementación de pila, una pila contiene un puntero superior. que es la «cabeza» de la pila donde se empujan y sacan elementos al principio de la lista. El primer Node tiene nulo en el campo de enlace y el segundo enlace de Node tiene la dirección del primer Node en el campo de enlace y así sucesivamente y la dirección del último Node en el puntero «superior».
La principal ventaja de usar una lista enlazada sobre una array es que es posible implementar una pila que puede reducirse o crecer tanto como sea necesario. Al usar la array, se restringirá la capacidad máxima de la array, lo que puede provocar un desbordamiento de la pila. Aquí cada nuevo Node se asignará dinámicamente. por lo que el desbordamiento no es posible.
Operaciones de pila:
- push() : inserta un nuevo elemento en la pila, es decir, simplemente inserta un nuevo elemento al comienzo de la lista enlazada.
- pop() : Devuelve el elemento superior de la pila, es decir, simplemente elimina el primer elemento de la lista enlazada.
- peek() : Devuelve el elemento superior.
- display(): Imprime todos los elementos en Stack.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Implement a stack
//using singly linked list
#include <bits/stdc++.h>
using namespace std;
// Declare linked list node
struct Node
{
int data;
Node* link;
};
Node* top;
// Utility function to add an element
// data in the stack insert at the beginning
void push(int data)
{
// Create new node temp and allocate memory in heap
Node* temp = new Node();
// Check if stack (heap) is full.
// Then inserting an element would
// lead to stack overflow
if (!temp)
{
cout << "\nStack Overflow";
exit(1);
}
// Initialize data into temp data field
temp->data = data;
// Put top pointer reference into temp link
temp->link = top;
// Make temp as top of Stack
top = temp;
}
// Utility function to check if
// the stack is empty or not
int isEmpty()
{
//If top is NULL it means that
//there are no elements are in stack
return top == NULL;
}
// Utility function to return top element in a stack
int peek()
{
// If stack is not empty , return the top element
if (!isEmpty())
return top->data;
else
exit(1);
}
// Utility function to pop top
// element from the stack
void pop()
{
Node* temp;
// Check for stack underflow
if (top == NULL)
{
cout << "\nStack Underflow" << endl;
exit(1);
}
else
{
// Assign top to temp
temp = top;
// Assign second node to top
top = top->link;
//This will automatically destroy
//the link between first node and second node
// Release memory of top node
//i.e delete the node
free(temp);
}
}
// Function to print all the
// elements of the stack
void display()
{
Node* temp;
// Check for stack underflow
if (top == NULL)
{
cout << "\nStack Underflow";
exit(1);
}
else
{
temp = top;
while (temp != NULL)
{
// Print node data
cout << temp->data << "-> ";
// Assign temp link to temp
temp = temp->link;
}
}
}
// Driver Code
int main()
{
// Push the elements of stack
push(11);
push(22);
push(33);
push(44);
// Display stack elements
display();
// Print top element of stack
cout << "\nTop element is "
<< peek() << endl;
// Delete top elements of stack
pop();
pop();
// Display stack elements
display();
// Print top element of stack
cout << "\nTop element is "
<< peek() << endl;
return 0;
}
Java
// Java program to Implement a stack
// using singly linked list
// import package
import static java.lang.System.exit;
// Create Stack Using Linked list
class StackUsingLinkedlist {
// A linked list node
private class Node {
int data; // integer data
Node link; // reference variable Node type
}
// create global top reference variable global
Node top;
// Constructor
StackUsingLinkedlist()
{
this.top = null;
}
// Utility function to add an element x in the stack
public void push(int x) // insert at the beginning
{
// create new node temp and allocate memory
Node temp = new Node();
// check if stack (heap) is full. Then inserting an
// element would lead to stack overflow
if (temp == null) {
System.out.print("\nHeap Overflow");
return;
}
// initialize data into temp data field
temp.data = x;
// put top reference into temp link
temp.link = top;
// update top reference
top = temp;
}
// Utility function to check if the stack is empty or not
public boolean isEmpty()
{
return top == null;
}
// Utility function to return top element in a stack
public int peek()
{
// check for empty stack
if (!isEmpty()) {
return top.data;
}
else {
System.out.println("Stack is empty");
return -1;
}
}
// Utility function to pop top element from the stack
public void pop() // remove at the beginning
{
// check for stack underflow
if (top == null) {
System.out.print("\nStack Underflow");
return;
}
// update the top pointer to point to the next node
top = (top).link;
}
public void display()
{
// check for stack underflow
if (top == null) {
System.out.printf("\nStack Underflow");
exit(1);
}
else {
Node temp = top;
while (temp != null) {
// print node data
System.out.printf("%d->", temp.data);
// assign temp link to temp
temp = temp.link;
}
}
}
}
// main class
public class GFG {
public static void main(String[] args)
{
// create Object of Implementing class
StackUsingLinkedlist obj = new StackUsingLinkedlist();
// insert Stack value
obj.push(11);
obj.push(22);
obj.push(33);
obj.push(44);
// print Stack elements
obj.display();
// print Top element of Stack
System.out.printf("\nTop element is %d\n", obj.peek());
// Delete top element of Stack
obj.pop();
obj.pop();
// print Stack elements
obj.display();
// print Top element of Stack
System.out.printf("\nTop element is %d\n", obj.peek());
}
}
Python3
'''Python supports automatic garbage collection so deallocation of memory
is done implicitly. However to force it to deallocate each node after use,
add the following code:
import gc #added at the start of program
gc.collect() #to be added wherever memory is to be deallocated
'''
class Node:
# Class to create nodes of linked list
# constructor initializes node automatically
def __init__(self,data):
self.data = data
self.next = None
class Stack:
# head is default NULL
def __init__(self):
self.head = None
# Checks if stack is empty
def isempty(self):
if self.head == None:
return True
else:
return False
# Method to add data to the stack
# adds to the start of the stack
def push(self,data):
if self.head == None:
self.head=Node(data)
else:
newnode = Node(data)
newnode.next = self.head
self.head = newnode
# Remove element that is the current head (start of the stack)
def pop(self):
if self.isempty():
return None
else:
# Removes the head node and makes
#the preceding one the new head
poppednode = self.head
self.head = self.head.next
poppednode.next = None
return poppednode.data
# Returns the head node data
def peek(self):
if self.isempty():
return None
else:
return self.head.data
# Prints out the stack
def display(self):
iternode = self.head
if self.isempty():
print("Stack Underflow")
else:
while(iternode != None):
print(iternode.data,"->",end = " ")
iternode = iternode.next
return
# Driver code
MyStack = Stack()
MyStack.push(11)
MyStack.push(22)
MyStack.push(33)
MyStack.push(44)
# Display stack elements
MyStack.display()
# Print top element of stack
print("\nTop element is ",MyStack.peek())
# Delete top elements of stack
MyStack.pop()
MyStack.pop()
# Display stack elements
MyStack.display()
# Print top element of stack
print("\nTop element is ", MyStack.peek())
# This code is contributed by Mathew George
C#
// C# program to Implement a stack
// using singly linked list
// import package
using System;
// Create Stack Using Linked list
public class StackUsingLinkedlist
{
// A linked list node
private class Node
{
// integer data
public int data;
// reference variable Node type
public Node link;
}
// create global top reference variable
Node top;
// Constructor
public StackUsingLinkedlist()
{
this.top = null;
}
// Utility function to add
// an element x in the stack
// insert at the beginning
public void push(int x)
{
// create new node temp and allocate memory
Node temp = new Node();
// check if stack (heap) is full.
// Then inserting an element
// would lead to stack overflow
if (temp == null)
{
Console.Write("\nHeap Overflow");
return;
}
// initialize data into temp data field
temp.data = x;
// put top reference into temp link
temp.link = top;
// update top reference
top = temp;
}
// Utility function to check if
// the stack is empty or not
public bool isEmpty()
{
return top == null;
}
// Utility function to return
// top element in a stack
public int peek()
{
// check for empty stack
if (!isEmpty())
{
return top.data;
}
else
{
Console.WriteLine("Stack is empty");
return -1;
}
}
// Utility function to pop top element from the stack
public void pop() // remove at the beginning
{
// check for stack underflow
if (top == null)
{
Console.Write("\nStack Underflow");
return;
}
// update the top pointer to
// point to the next node
top = (top).link;
}
public void display()
{
// check for stack underflow
if (top == null)
{
Console.Write("\nStack Underflow");
return;
}
else
{
Node temp = top;
while (temp != null)
{
// print node data
Console.Write("{0}->", temp.data);
// assign temp link to temp
temp = temp.link;
}
}
}
}
// Driver code
public class GFG
{
public static void Main(String[] args)
{
// create Object of Implementing class
StackUsingLinkedlist obj = new StackUsingLinkedlist();
// insert Stack value
obj.push(11);
obj.push(22);
obj.push(33);
obj.push(44);
// print Stack elements
obj.display();
// print Top element of Stack
Console.Write("\nTop element is {0}\n", obj.peek());
// Delete top element of Stack
obj.pop();
obj.pop();
// print Stack elements
obj.display();
// print Top element of Stack
Console.Write("\nTop element is {0}\n", obj.peek());
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to Implement a stack
// using singly linked list
// import package
// A linked list node
class Node
{
constructor()
{
this.data=0;
this.link=null;
}
}
// Create Stack Using Linked list
class StackUsingLinkedlist
{
constructor()
{
this.top=null;
}
// Utility function to add an element x in the stack
push(x)
{
// create new node temp and allocate memory
let temp = new Node();
// check if stack (heap) is full. Then inserting an
// element would lead to stack overflow
if (temp == null) {
document.write("<br>Heap Overflow");
return;
}
// initialize data into temp data field
temp.data = x;
// put top reference into temp link
temp.link = this.top;
// update top reference
this.top = temp;
}
// Utility function to check if the stack is empty or not
isEmpty()
{
return this.top == null;
}
// Utility function to return top element in a stack
peek()
{
// check for empty stack
if (!this.isEmpty()) {
return this.top.data;
}
else {
document.write("Stack is empty<br>");
return -1;
}
}
// Utility function to pop top element from the stack
pop() // remove at the beginning
{
// check for stack underflow
if (this.top == null) {
document.write("<br>Stack Underflow");
return;
}
// update the top pointer to point to the next node
this.top = this.top.link;
}
display()
{
// check for stack underflow
if (this.top == null) {
document.write("<br>Stack Underflow");
}
else {
let temp = this.top;
while (temp != null) {
// print node data
document.write(temp.data+"->");
// assign temp link to temp
temp = temp.link;
}
}
}
}
// main class
// create Object of Implementing class
let obj = new StackUsingLinkedlist();
// insert Stack value
obj.push(11);
obj.push(22);
obj.push(33);
obj.push(44);
// print Stack elements
obj.display();
// print Top element of Stack
document.write("<br>Top element is ", obj.peek()+"<br>");
// Delete top element of Stack
obj.pop();
obj.pop();
// print Stack elements
obj.display();
// print Top element of Stack
document.write("<br>Top element is ", obj.peek()+"<br>");
// This code is contributed by rag2127
</script>
Producción:
44->33->22->11-> Top element is 44 22->11-> Top element is 22
La complejidad de tiempo para todas las operaciones push(), pop() y peek() es O(1) ya que no estamos realizando ningún tipo de recorrido sobre la lista. Realizamos todas las operaciones solo a través del puntero actual.
Complejidad espacial : O(n) donde n es el tamaño de la pila