Estructura de Datos las Pilas (Stack)

Una pila es una estructura de datos lineal que sigue dos métodos en el orden de las operaciones, LIFO (Last In First Out) o FILO (First In Last Out). Las siguientes operaciones se pueden realizar principalmente en pilas:

  • push : agrega un elemento a la pila, y si la pila está llena, el estado se llama desbordamiento.
  • Pop : Elimina los elementos de la pila en el orden inverso al que entraron en la pila. Si la pila está vacía, entonces el estado se llama subdesbordamiento.
  • Peek o Top : Devuelve el elemento en la parte superior de la pila.
  • isEmpty : Devuelve verdadero si la pila está vacía, falso en caso contrario.

Tabla de contenidos

Ejemplo práctico de pilas

Hay muchos ejemplos prácticos en la vida cotidiana que se pueden utilizar para comprender cómo funcionan las pilas. Por ejemplo, un grupo de platos se puede colocar uno encima del otro para formar una pila en la que el plato superior es el primer plato que se retira de la pila, y esto significa que el último plato (inferior) de esta pila permanecerá en él durante más tiempo, y se puede decir que estos platos siguen el orden LIFO/FILO.

Aplicaciones en pilas

  • Equilibrio de símbolos
  • Convertir Infijo a Postfijo / Convertir Prefijo
  • Rehacer y deshacer operaciones en muchos programas como editores de texto y Photoshop.
  • La característica de mostrar las páginas siguientes y anteriores en los navegadores web.
  • Las pilas se utilizan en muchos algoritmos, como la Torre de Hanoi , Tree Traversals y en el problema del histograma.
  • Otras aplicaciones como retroceder , el problema de la gira del caballero , rata en un laberinto y resolución de sudoku .
  • En algoritmos de imagen como orden topológico y Componentes Fuertemente Conectados.

Ejecución de pila e implementación usando arreglos

Las pilas se pueden implementar de dos maneras:

  • utilizando matrices.
  • utilizando listas enlazadas.

Los siguientes ejemplos muestran métodos para crear pilas utilizando matrices y en varios lenguajes de programación:

/* C++ program to implement basic stack
operations */
#include <bits/stdc++.h>

using namespace std;

#define MAX 1000

class Stack {
	int top;

public:
	int a[MAX]; // Maximum size of Stack

	Stack() { top = -1; }
	bool push(int x);
	int pop();
	int peek();
	bool isEmpty();
};

bool Stack::push(int x)
{
	if (top >= (MAX - 1)) {
		cout << "Stack Overflow";
		return false;
	}
	else {
		a[++top] = x;
		cout << x << " pushed into stack\n";
		return true;
	}
}

int Stack::pop()
{
	if (top < 0) {
		cout << "Stack Underflow";
		return 0;
	}
	else {
		int x = a[top--];
		return x;
	}
}
int Stack::peek()
{
	if (top < 0) {
		cout << "Stack is Empty";
		return 0;
	}
	else {
		int x = a[top];
		return x;
	}
}

bool Stack::isEmpty()
{
	return (top < 0);
}

// Driver program to test above functions
int main()
{
	class Stack s;
	s.push(10);
	s.push(20);
	s.push(30);
	cout << s.pop() << " Popped from stack\n";
	//print all elements in stack :
	cout<<"Elements present in stack : ";
	while(!s.isEmpty())
	{
		// print top element in stack
		cout<<s.peek()<<" ";
		// remove top element in stack
		s.pop();
	}

	return 0;
}

El código necesita importar la variable maxsize del módulo sys para devolver el valor ‎-infinite‎ si la pila está vacía:

# Python program for implementation of stack

# import maxsize from sys module
# Used to return -infinite when stack is empty
from sys import maxsize

# Function to create a stack. It initializes size of stack as 0
def createStack():
	stack = []
	return stack

# Stack is empty when stack size is 0
def isEmpty(stack):
	return len(stack) == 0

# Function to add an item to stack. It increases size by 1
def push(stack, item):
	stack.append(item)
	print(item + " pushed to stack ")
	
# Function to remove an item from stack. It decreases size by 1
def pop(stack):
	if (isEmpty(stack)):
		return str(-maxsize -1) # return minus infinite
	
	return stack.pop()

# Function to return the top from stack without removing it
def peek(stack):
	if (isEmpty(stack)):
		return str(-maxsize -1) # return minus infinite
	return stack[len(stack) - 1]

# Driver program to test above functions
stack = createStack()
push(stack, str(10))
push(stack, str(20))
push(stack, str(30))
print(pop(stack) + " popped from stack")
/* Java program to implement basic stack
operations */
class Stack {
	static final int MAX = 1000;
	int top;
	int a[] = new int[MAX]; // Maximum size of Stack

	boolean isEmpty()
	{
		return (top < 0);
	}
	Stack()
	{
		top = -1;
	}

	boolean push(int x)
	{
		if (top >= (MAX - 1)) {
			System.out.println("Stack Overflow");
			return false;
		}
		else {
			a[++top] = x;
			System.out.println(x + " pushed into stack");
			return true;
		}
	}

	int pop()
	{
		if (top < 0) {
			System.out.println("Stack Underflow");
			return 0;
		}
		else {
			int x = a[top--];
			return x;
		}
	}

	int peek()
	{
		if (top < 0) {
			System.out.println("Stack Underflow");
			return 0;
		}
		else {
			int x = a[top];
			return x;
		}
	}
	
	void print(){
	for(int i = top;i>-1;i--){
	System.out.print(" "+ a[i]);
	}
}
}

// Driver code
class Main {
	public static void main(String args[])
	{
		Stack s = new Stack();
		s.push(10);
		s.push(20);
		s.push(30);
		System.out.println(s.pop() + " Popped from stack");
		System.out.println("Top element is :" + s.peek());
		System.out.print("Elements present in stack :");
		s.print();
	}
}

El código anterior da el siguiente resultado:

10 empujados a la pila 
20 empujados a la pila 
30 empujados a la pila 
30 sacados de la pila

Ventajas de este método: fácil de implementar, no consume mucha memoria porque no se utilizan punteros.

Desventajas de este método: no es dinámico y no crece ni se reduce según sea necesario en tiempo de ejecución.

Implementación de pilas usando listas enhebradas

Los siguientes ejemplos muestran formas de crear pilas utilizando listas encadenadas y en varios lenguajes de programación:

// C++ program for linked list implementation of stack
#include <bits/stdc++.h>
using namespace std;

// A structure to represent a stack
class StackNode {
public:
	int data;
	StackNode* next;
};

StackNode* newNode(int data)
{
	StackNode* stackNode = new StackNode();
	stackNode->data = data;
	stackNode->next = NULL;
	return stackNode;
}

int isEmpty(StackNode* root)
{
	return !root;
}

void push(StackNode** root, int data)
{
	StackNode* stackNode = newNode(data);
	stackNode->next = *root;
	*root = stackNode;
	cout << data << " pushed to stack\n";
}

int pop(StackNode** root)
{
	if (isEmpty(*root))
		return INT_MIN;
	StackNode* temp = *root;
	*root = (*root)->next;
	int popped = temp->data;
	free(temp);

	return popped;
}

int peek(StackNode* root)
{
	if (isEmpty(root))
		return INT_MIN;
	return root->data;
}

// Driver code
int main()
{
	StackNode* root = NULL;

	push(&root, 10);
	push(&root, 20);
	push(&root, 30);

	cout << pop(&root) << " popped from stack\n";

	cout << "Top element is " << peek(root) << endl;
	
	cout<<"Elements present in stack : ";
	//print all elements in stack :
	while(!isEmpty(root))
	{
		// print top element in stack
		cout<<peek(root)<<" ";
		// remove top element in stack
		pop(&root);
	}

	return 0;
}
# Python program for linked list implementation of stack

# Class to represent a node


class StackNode:

	# Constructor to initialize a node
	def __init__(self, data):
		self.data = data
		self.next = None


class Stack:

	# Constructor to initialize the root of linked list
	def __init__(self):
		self.root = None

	def isEmpty(self):
		return True if self.root is None else False

	def push(self, data):
		newNode = StackNode(data)
		newNode.next = self.root
		self.root = newNode
		print ("% d pushed to stack" % (data))

	def pop(self):
		if (self.isEmpty()):
			return float("-inf")
		temp = self.root
		self.root = self.root.next
		popped = temp.data
		return popped

	def peek(self):
		if self.isEmpty():
			return float("-inf")
		return self.root.data


# Driver code
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)

print ("% d popped from stack" % (stack.pop()))
print ("Top element is % d " % (stack.peek()))
// Java Code for Linked List Implementation

public class StackAsLinkedList {

	StackNode root;

	static class StackNode {
		int data;
		StackNode next;

		StackNode(int data) { this.data = data; }
	}

	public boolean isEmpty()
	{
		if (root == null) {
			return true;
		}
		else
			return false;
	}

	public void push(int data)
	{
		StackNode newNode = new StackNode(data);

		if (root == null) {
			root = newNode;
		}
		else {
			StackNode temp = root;
			root = newNode;
			newNode.next = temp;
		}
		System.out.println(data + " pushed to stack");
	}

	public int pop()
	{
		int popped = Integer.MIN_VALUE;
		if (root == null) {
			System.out.println("Stack is Empty");
		}
		else {
			popped = root.data;
			root = root.next;
		}
		return popped;
	}

	public int peek()
	{
		if (root == null) {
			System.out.println("Stack is empty");
			return Integer.MIN_VALUE;
		}
		else {
			return root.data;
		}
	}

	// Driver code
	public static void main(String[] args)
	{

		StackAsLinkedList sll = new StackAsLinkedList();

		sll.push(10);
		sll.push(20);
		sll.push(30);

		System.out.println(sll.pop()
						+ " popped from stack");

		System.out.println("Top element is " + sll.peek());
	}
}

El código anterior da el siguiente resultado:

10 empujado a la pila 
20 empujado a la pila 
30 empujado a la pila 
30 extraído de la pila 
El elemento superior es 20

Ventajas de este método: este método puede crecer o reducirse según sea necesario en tiempo de ejecución.

Desventajas de este método: necesita usar más memoria porque se usan punteros.

Crear pilas usando colas

Una cola que admite operaciones como enqueue()‎ y se puede usar dequeue()‎ para crear una pila. Esta operación requiere el uso de dos colas (les daremos los nombres q1q2) y se puede realizar de dos formas:

Método 1: confiar en el impulso

Este proceso garantiza que el nuevo elemento se agregue al principio de la cola q1y, por lo tanto, el proceso emergente elimina los elementos de la cola q1 y la cola se utiliza q2 para colocar cada elemento nuevo al principio de la cola q1.

Este método se puede resumir en los siguientes pasos:

  1. El proceso push(s, x)‎donde x se agrega el elemento y la pila s a la que se agrega el elemento.
    1. Además x de la cola q2.
    2. Retire todos los elementos de la cola q1 uno por uno y los agrega a la cola q2.
    3. Cambie los nombres de los marcos q1q2, el objetivo es evitar mover todos los elementos del marco q2 al q1.
  2. proceso pop(s)‎:
    1. Retire el artículo q1 y lo devuelve.

Los siguientes ejemplos muestran formas de construir pilas usando colas y en varios lenguajes de programación:

/* Program to implement a stack using
two queue */
#include <bits/stdc++.h>

using namespace std;

class Stack {
	// Two inbuilt queues
	queue<int> q1, q2;

	// To maintain current number of
	// elements
	int curr_size;

public:
	Stack()
	{
		curr_size = 0;
	}

	void push(int x)
	{
		curr_size++;

		// Push x first in empty q2
		q2.push(x);

		// Push all the remaining
		// elements in q1 to q2.
		while (!q1.empty()) {
			q2.push(q1.front());
			q1.pop();
		}

		// swap the names of two queues
		queue<int> q = q1;
		q1 = q2;
		q2 = q;
	}

	void pop()
	{

		// if no elements are there in q1
		if (q1.empty())
			return;
		q1.pop();
		curr_size--;
	}

	int top()
	{
		if (q1.empty())
			return -1;
		return q1.front();
	}

	int size()
	{
		return curr_size;
	}
};

// Driver code
int main()
{
	Stack s;
	s.push(1);
	s.push(2);
	s.push(3);

	cout << "current size: " << s.size()
		<< endl;
	cout << s.top() << endl;
	s.pop();
	cout << s.top() << endl;
	s.pop();
	cout << s.top() << endl;

	cout << "current size: " << s.size()
		<< endl;
	return 0;
}
  • Python (nota: para que este código funcione en la versión 2 de Python, debe usar el módulo Queue en su lugar queue):
# Program to implement a stack using
# two queue
from queue import Queue

class Stack:
	
	def __init__(self):
		
		# Two inbuilt queues
		self.q1 = Queue()
		self.q2 = Queue()
			
		# To maintain current number
		# of elements
		self.curr_size = 0

	def push(self, x):
		self.curr_size += 1

		# Push x first in empty q2
		self.q2.put(x)

		# Push all the remaining
		# elements in q1 to q2.
		while (not self.q1.empty()):
			self.q2.put(self.q1.queue[0])
			self.q1.get()

		# swap the names of two queues
		self.q = self.q1
		self.q1 = self.q2
		self.q2 = self.q

	def pop(self):

		# if no elements are there in q1
		if (self.q1.empty()):
			return
		self.q1.get()
		self.curr_size -= 1

	def top(self):
		if (self.q1.empty()):
			return -1
		return self.q1.queue[0]

	def size(self):
		return self.curr_size

# Driver Code
if __name__ == '__main__':
	s = Stack()
	s.push(1)
	s.push(2)
	s.push(3)

	print("current size: ", s.size())
	print(s.top())
	s.pop()
	print(s.top())
	s.pop()
	print(s.top())

	print("current size: ", s.size())
/* Java Program to implement a stack using
two queue */
import java.util.*;

class GfG {

	static class Stack {
		// Two inbuilt queues
		static Queue<Integer> q1 = new LinkedList<Integer>();
		static Queue<Integer> q2 = new LinkedList<Integer>();

		// To maintain current number of
		// elements
		static int curr_size;

		Stack()
		{
			curr_size = 0;
		}

		static void push(int x)
		{
			curr_size++;

			// Push x first in empty q2
			q2.add(x);

			// Push all the remaining
			// elements in q1 to q2.
			while (!q1.isEmpty()) {
				q2.add(q1.peek());
				q1.remove();
			}

			// swap the names of two queues
			Queue<Integer> q = q1;
			q1 = q2;
			q2 = q;
		}

		static void pop()
		{

			// if no elements are there in q1
			if (q1.isEmpty())
				return;
			q1.remove();
			curr_size--;
		}

		static int top()
		{
			if (q1.isEmpty())
				return -1;
			return q1.peek();
		}

		static int size()
		{
			return curr_size;
		}
	}

	// driver code
	public static void main(String[] args)
	{
		Stack s = new Stack();
		s.push(1);
		s.push(2);
		s.push(3);

		System.out.println("current size: " + s.size());
		System.out.println(s.top());
		s.pop();
		System.out.println(s.top());
		s.pop();
		System.out.println(s.top());

		System.out.println("current size: " + s.size());
	}
}

El código anterior da el siguiente resultado:

tamaño actual: 3 
3 
2 
1 
tamaño actual: 1

El segundo método: confiar en el proceso pop

El nuevo elemento siempre se agrega a la cola q1 en un proceso push, y en el proceso, pop()‎ si la cola q2 está vacía, todos los elementos excepto el último elemento se moverán a la cola q2, luego el último elemento de la cola q1 se elimina y se devuelve.

Este proceso se puede resumir en los siguientes pasos:

  1. proceso push(s, x)‎:
    1. Agregado x al marco q1(suponiendo que q1 no se especifica el tamaño del marco).
  2. proceso pop(s)‎:
    1. Quite los elementos uno por uno excepto el último elemento de la cola q1 y los agrega a la cola q2.
    2. Elimina el último elemento de la cola q1 y es guardado.
    3. Cambie los nombres de los dos marcos q1q2, el objetivo es evitar que el proceso de mover todos los elementos del marco q2q1.
    4. Devuelve el artículo almacenado en el segundo paso.

Los siguientes ejemplos muestran formas de construir pilas usando colas y en varios lenguajes de programación:

/* Program to implement a stack
using two queue */
#include <bits/stdc++.h>
using namespace std;

class Stack {
	queue<int> q1, q2;
	int curr_size;

public:
	Stack()
	{
		curr_size = 0;
	}

	void pop()
	{
		if (q1.empty())
			return;

		// Leave one element in q1 and
		// push others in q2.
		while (q1.size() != 1) {
			q2.push(q1.front());
			q1.pop();
		}

		// Pop the only left element
		// from q1
		q1.pop();
		curr_size--;

		// swap the names of two queues
		queue<int> q = q1;
		q1 = q2;
		q2 = q;
	}

	void push(int x)
	{
		q1.push(x);
		curr_size++;
	}

	int top()
	{
		if (q1.empty())
			return -1;

		while (q1.size() != 1) {
			q2.push(q1.front());
			q1.pop();
		}

		// last pushed element
		int temp = q1.front();

		// to empty the auxiliary queue after
		// last operation
		q1.pop();

		// push last element to q2
		q2.push(temp);

		// swap the two queues names
		queue<int> q = q1;
		q1 = q2;
		q2 = q;
		return temp;
	}

	int size()
	{
		return curr_size;
	}
};

// Driver code
int main()
{
	Stack s;
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);

	cout << "current size: " << s.size()
		<< endl;
	cout << s.top() << endl;
	s.pop();
	cout << s.top() << endl;
	s.pop();
	cout << s.top() << endl;
	cout << "current size: " << s.size()
		<< endl;
	return 0;
}
/* Java Program to implement a stack
using two queue */
import java.util.*;

class Stack {
	Queue<Integer> q1 = new LinkedList<>(), q2 = new LinkedList<>();
	int curr_size;

	public Stack()
	{
		curr_size = 0;
	}

	void remove()
	{
		if (q1.isEmpty())
			return;

		// Leave one element in q1 and
		// push others in q2.
		while (q1.size() != 1) {
			q2.add(q1.peek());
			q1.remove();
		}

		// Pop the only left element
		// from q1
		q1.remove();
		curr_size--;

		// swap the names of two queues
		Queue<Integer> q = q1;
		q1 = q2;
		q2 = q;
	}

	void add(int x)
	{
		q1.add(x);
		curr_size++;
	}

	int top()
	{
		if (q1.isEmpty())
			return -1;

		while (q1.size() != 1) {
			q2.add(q1.peek());
			q1.remove();
		}

		// last pushed element
		int temp = q1.peek();

		// to empty the auxiliary queue after
		// last operation
		q1.remove();

		// push last element to q2
		q2.add(temp);

		// swap the two queues names
		Queue<Integer> q = q1;
		q1 = q2;
		q2 = q;
		return temp;
	}

	int size()
	{
		return curr_size;
	}

	// Driver code
	public static void main(String[] args)
	{
		Stack s = new Stack();
		s.add(1);
		s.add(2);
		s.add(3);
		s.add(4);

		System.out.println("current size: " + s.size());
		System.out.println(s.top());
		s.remove();
		System.out.println(s.top());
		s.remove();
		System.out.println(s.top());
		System.out.println("current size: " + s.size());
	}
}
# Program to implement a stack using
# two queue
from queue import Queue


class Stack:

	def __init__(self):

		# Two inbuilt queues
		self.q1 = Queue()
		self.q2 = Queue()

		# To maintain current number
		# of elements
		self.curr_size = 0

	def push(self, x):
		self.q1.put(x)
		self.curr_size += 1

	def pop(self):
		# if no elements are there in q1
		if (self.q1.empty()):
			return
		# Leave one element in q1 and push others in q2
		while(self.q1.qsize() != 1):
			self.q2.put(self.q1.get())

		# Pop the only left element from q1
		popped = self.q1.get()
		self.curr_size -= 1

		# swap the names of two queues
		self.q = self.q1
		self.q1 = self.q2
		self.q2 = self.q

	def top(self):
		# if no elements are there in q1
		if (self.q1.empty()):
			return
		# Leave one element in q1 and push others in q2
		while(self.q1.qsize() != 1):
			self.q2.put(self.q1.get())

		# Pop the only left element from q1 to q2
		top = self.q1.queue[0]
		self.q2.put(self.q1.get())

		# swap the names of two queues
		self.q = self.q1
		self.q1 = self.q2
		self.q2 = self.q

		return top

	def size(self):
		return self.curr_size


# Driver Code
if __name__ == '__main__':
	s = Stack()
	s.push(1)
	s.push(2)
	s.push(3)
	s.push(4)

	print("current size: ", s.size())
	print(s.top())
	s.pop()
	print(s.top())
	s.pop()
	print(s.top())

	print("current size: ", s.size())

El código anterior da el siguiente resultado:

tamaño actual: 4 
4 
3 
2 
tamaño actual: 2

Invertir elementos de pila usando una función recursiva

Los elementos de la pila se pueden invertir usando una función recursiva sin necesidad de usar bucles iterativos como while,  for y otros en las funciones donde se pueden usar ejecutándose en la isEmpty(S)‎,  push(S) y ‎pop(S)‎.

Este método consiste en mantener todos los valores en la pila de llamadas de función hasta que obtengamos una pila vacía, momento en el que comenzamos a insertar los elementos uno por uno en la parte inferior de la pila.

Supongamos que tenemos la siguiente pila:

    1 <-- superior 
    2 
    3 
    4

Primero insertamos el elemento 4 en la parte inferior de la pila.

    4 <-- superior

Luego insertamos el elemento 3 en la parte inferior de la pila.

    4 <-- los     
    3 primeros

Luego insertamos el elemento 2 en la parte inferior de la pila.

    4 <-- top     
    3 
    2

Luego insertamos el elemento 1 en la parte inferior de la pila.

    4 <-- arriba     
    3 
    2 
    1

Entonces, necesitaremos una función que escale los elementos en la parte inferior de la pila como se muestra arriba.

Función insertAtBottom()‎: la función elimina todos los elementos de la pila y los almacena en la pila de llamadas de función mediante recursividad. Cuando la pila se vacía, la función empuja los elementos almacenados en la pila de llamadas.

Funciónreverse()‎ : esta función insertAtBottom()‎utiliza principalmente la función para eliminar todos los elementos uno por uno y agregar los elementos eliminados al final de la pila.

// C++ code to reverse a
// stack using recursion
#include<bits/stdc++.h>
using namespace std;

// using std::stack for
// stack implementation
stack<char> st;

// initializing a string to store
// result of reversed stack
string ns;

// Below is a recursive function
// that inserts an element
// at the bottom of a stack.
void insert_at_bottom(char x)
{

	if(st.size() == 0)
	st.push(x);

	else
	{
		
		// All items are held in Function Call
		// Stack until we reach end of the stack
		// When the stack becomes empty, the
		// st.size() becomes 0, the above if
		// part is executed and the item is
		// inserted at the bottom
			
		char a = st.top();
		st.pop();
		insert_at_bottom(x);

		// push allthe items held in
		// Function Call Stack
		// once the item is inserted
		// at the bottom
		st.push(a);
	}
}

// Below is the function that
// reverses the given stack using
// insert_at_bottom()
void reverse()
{
	if(st.size()>0)
	{
		
		// Hold all items in Function
		// Call Stack until we
		// reach end of the stack
		char x = st.top();
		st.pop();
		reverse();
		
		// Insert all the items held
		// in Function Call Stack
		// one by one from the bottom
		// to top. Every item is
		// inserted at the bottom
		insert_at_bottom(x);
	}
}

// Driver Code
int main()
{
	
	// push elements into
	// the stack
	st.push('1');
	st.push('2');
	st.push('3');
	st.push('4');
	
	cout<<"Original Stack"<<endl;
	
	// print the elements
	// of original stack
	cout<<"1"<<" "<<"2"<<" "
		<<"3"<<" "<<"4"
		<<endl;
	
	// function to reverse
	// the stack
	reverse();
	cout<<"Reversed Stack"
		<<endl;
	
	// storing values of reversed
	// stack into a string for display
	while(!st.empty())
	{
		char p=st.top();
		st.pop();
		ns+=p;
	}
	
	//display of reversed stack
	cout<<ns[3]<<" "<<ns[2]<<" "
		<<ns[1]<<" "<<ns[0]<<endl;
	return 0;
}
# Python program to reverse a
# stack using recursion

# Below is a recursive function
# that inserts an element
# at the bottom of a stack.
def insertAtBottom(stack, item):
	if isEmpty(stack):
		push(stack, item)
	else:
		temp = pop(stack)
		insertAtBottom(stack, item)
		push(stack, temp)

# Below is the function that
# reverses the given stack
# using insertAtBottom()
def reverse(stack):
	if not isEmpty(stack):
		temp = pop(stack)
		reverse(stack)
		insertAtBottom(stack, temp)

# Below is a complete running
# program for testing above
# functions.

# Function to create a stack.
# It initializes size of stack
# as 0
def createStack():
	stack = []
	return stack

# Function to check if
# the stack is empty
def isEmpty( stack ):
	return len(stack) == 0

# Function to push an
# item to stack
def push( stack, item ):
	stack.append( item )

# Function to pop an
# item from stack
def pop( stack ):

	# If stack is empty
	# then error
	if(isEmpty( stack )):
		print("Stack Underflow ")
		exit(1)

	return stack.pop()

# Function to print the stack
def prints(stack):
	for i in range(len(stack)-1, -1, -1):
		print(stack[i], end = ' ')
	print()

# Driver Code

stack = createStack()
push( stack, str(4) )
push( stack, str(3) )
push( stack, str(2) )
push( stack, str(1) )
print("Original Stack ")
prints(stack)

reverse(stack)

print("Reversed Stack ")
prints(stack)
// Java code to reverse a
// stack using recursion
import java.util.Stack;

class Test {
	
	// using Stack class for
	// stack implementation
	static Stack<Character> st = new Stack<>();
	
	// Below is a recursive function
	// that inserts an element
	// at the bottom of a stack.
	static void insert_at_bottom(char x)
	{

		if(st.isEmpty())
			st.push(x);

		else
		{
			
			// All items are held in Function
			// Call Stack until we reach end
			// of the stack. When the stack becomes
			// empty, the st.size() becomes 0, the
			// above if part is executed and
			// the item is inserted at the bottom
			char a = st.peek();
			st.pop();
			insert_at_bottom(x);

			// push allthe items held
			// in Function Call Stack
			// once the item is inserted
			// at the bottom
			st.push(a);
		}
	}
	
	// Below is the function that
	// reverses the given stack using
	// insert_at_bottom()
	static void reverse()
	{
		if(st.size() > 0)
		{
			
			// Hold all items in Function
			// Call Stack until we
			// reach end of the stack
			char x = st.peek();
			st.pop();
			reverse();
			
			// Insert all the items held
			// in Function Call Stack
			// one by one from the bottom
			// to top. Every item is
			// inserted at the bottom
			insert_at_bottom(x);
		}
	}
	
	// Driver Code
	public static void main(String[] args)
	{
		
		// push elements into
		// the stack
		st.push('1');
		st.push('2');
		st.push('3');
		st.push('4');
		
		System.out.println("Original Stack");
		
		System.out.println(st);
		
		// function to reverse
		// the stack
		reverse();
		
		System.out.println("Reversed Stack");
		
		System.out.println(st);
	}
}

El código anterior da los siguientes datos:

Pila original 
 1 2 3 4 
 Pila invertida 
 4 3 2 1

Organice los elementos de la pila usando funciones recursivas

Los elementos de la pila se pueden organizar usando funciones recursivas y sin bucles como whilefor, se pueden usar las siguientes funciones:

  • is_empty(S)‎: La función comprueba si la pila está vacía o no.
  • push(S)‎: La función agrega un nuevo elemento a la pila.
  • pop(S)‎: La función elimina el elemento superior de la pila.
  • top(S)‎: La función devuelve el valor del elemento superior de la pila. Tenga en cuenta que esta función no elimina elementos de la pila.

Ejemplo:

Entrada: -3 <--- Principales 
        14 
        18 
        -5 
        30 

Salida: 30 <--- Principales 
        18 
        14 
        -3 
        -5

La forma en que se organizan los elementos de la pila es muy similar a la forma en que se invierten los elementos. El método consiste en almacenar todos los valores en la pila de llamadas de función hasta que la pila esté vacía, momento en el que insertamos todos los valores almacenados uno por uno y en orden.

Algoritmo utilizado

El siguiente algoritmo se puede utilizar para organizar los elementos en la pila:

sortStack(stack S)
    if stack is not empty:
        temp = pop(S);  
        sortStack(S); 
        sortedInsert(S, temp);

El siguiente algoritmo muestra cómo insertar el elemento en la pila y en orden:

sortedInsert(Stack S, element)
    if stack is empty OR element > top element
        push(S, elem)
    else
        temp = pop(S)
        sortedInsert(S, element)
        push(S, temp)

Ejemplo ilustrativo

Supongamos que tenemos la siguiente pila:

-3 <-- parte superior de la pila 
14 
18 
-5 
30

El primer paso es eliminar todos los elementos de la pila y almacenarlos en una variable temporal temp. Después de eliminar todos los elementos, el marco de la pila de la función se verá así:

temp = -3 --> apilar marco #1 
temp = 14 --> apilar marco #2 
temp = 18 --> apilar marco #3 
temp = -5 --> apilar marco #4 
temp = 30 --> apilar marco #5

Se llama a la función insert_in_sorted_order()‎después de que la pila esté vacía para insertar el valor 30 (del marco de pila 5) en la parte inferior de la pila, por lo que la pila se convierte en:

30 <-- la parte superior de la pila

La función toma el siguiente elemento ‎-5(del cuadro de pila 4) y dado que ‎-5 < 30 el elemento -5 se inserta en la parte inferior de la pila, la pila se convierte en:

30 <-- parte superior de la pila 
-5

La función selecciona el siguiente elemento 18(desde el marco de la pila 3) y dado que ‎18 < 30 el elemento 18 se insertará debajo del elemento 30, la pila se convierte en:

30 <-- parte superior de la pila 
18     
-5

La función toma el siguiente elemento 14(del marco de la pila 2) y, dado que ‎14 < 30‎‎14 < 18 el elemento 14 se insertará debajo del elemento 18, por lo que la pila se convierte en:

30 <-- parte superior de la pila 
18 
14     
-5

La función toma el siguiente elemento ‎-3(del marco de la pila 1) y dado que ‎-3 < 30‎ el elemento se insertarán debajo del elemento, la pila se convierte en: ‎-3 < 18‎-3 < 14‎-314

30 <-- parte superior de la pila 
18 
14 
-3     
-5

Ejemplos y aplicación en código

Los siguientes ejemplos muestran cómo se organizan los elementos de la pila en varios lenguajes de programación:

// C++ program to sort a stack using recursion
#include <iostream>
using namespace std;

// Stack is represented using linked list
struct stack {
	int data;
	struct stack* next;
};

// Utility function to initialize stack
void initStack(struct stack** s) { *s = NULL; }

// Utility function to check if stack is empty
int isEmpty(struct stack* s)
{
	if (s == NULL)
		return 1;
	return 0;
}

// Utility function to push an item to stack
void push(struct stack** s, int x)
{
	struct stack* p = (struct stack*)malloc(sizeof(*p));

	if (p == NULL) {
		fprintf(stderr, "Memory allocation failed.\n");
		return;
	}

	p->data = x;
	p->next = *s;
	*s = p;
}

// Utility function to remove an item from stack
int pop(struct stack** s)
{
	int x;
	struct stack* temp;

	x = (*s)->data;
	temp = *s;
	(*s) = (*s)->next;
	free(temp);

	return x;
}

// Function to find top item
int top(struct stack* s) { return (s->data); }

// Recursive function to insert an item x in sorted way
void sortedInsert(struct stack** s, int x)
{
	// Base case: Either stack is empty or newly inserted
	// item is greater than top (more than all existing)
	if (isEmpty(*s) or x > top(*s)) {
		push(s, x);
		return;
	}

	// If top is greater, remove the top item and recur
	int temp = pop(s);
	sortedInsert(s, x);

	// Put back the top item removed earlier
	push(s, temp);
}

// Function to sort stack
void sortStack(struct stack** s)
{
	// If stack is not empty
	if (!isEmpty(*s)) {
		// Remove the top item
		int x = pop(s);

		// Sort remaining stack
		sortStack(s);

		// Push the top item back in sorted stack
		sortedInsert(s, x);
	}
}

// Utility function to print contents of stack
void printStack(struct stack* s)
{
	while (s) {
		cout << s->data << " ";
		s = s->next;
	}
	cout << "\n";
}

// Driver code
int main(void)
{
	struct stack* top;

	initStack(&top);
	push(&top, 30);
	push(&top, -5);
	push(&top, 18);
	push(&top, 14);
	push(&top, -3);

	cout << "Stack elements before sorting:\n";
	printStack(top);

	sortStack(&top);
	cout << "\n";

	cout << "Stack elements after sorting:\n";
	printStack(top);

	return 0;
}
// Java program to sort a Stack using recursion
// Note that here predefined Stack class is used
// for stack operation

import java.util.ListIterator;
import java.util.Stack;

class Test
{
	// Recursive Method to insert an item x in sorted way
	static void sortedInsert(Stack<Integer> s, int x)
	{
		// Base case: Either stack is empty or newly
		// inserted item is greater than top (more than all
		// existing)
		if (s.isEmpty() || x > s.peek())
		{
			s.push(x);
			return;
		}

		// If top is greater, remove the top item and recur
		int temp = s.pop();
		sortedInsert(s, x);

		// Put back the top item removed earlier
		s.push(temp);
	}

	// Method to sort stack
	static void sortStack(Stack<Integer> s)
	{
		// If stack is not empty
		if (!s.isEmpty())
		{
			// Remove the top item
			int x = s.pop();

			// Sort remaining stack
			sortStack(s);

			// Push the top item back in sorted stack
			sortedInsert(s, x);
		}
	}

	// Utility Method to print contents of stack
	static void printStack(Stack<Integer> s)
	{
		ListIterator<Integer> lt = s.listIterator();

		// forwarding
		while (lt.hasNext())
			lt.next();

		// printing from top to bottom
		while (lt.hasPrevious())
			System.out.print(lt.previous() + " ");
	}

	// Driver code
	public static void main(String[] args)
	{
		Stack<Integer> s = new Stack<>();
		s.push(30);
		s.push(-5);
		s.push(18);
		s.push(14);
		s.push(-3);

		System.out.println(
			"Stack elements before sorting: ");
		printStack(s);

		sortStack(s);

		System.out.println(
			" \n\nStack elements after sorting:");
		printStack(s);
	}
}
# Python program to sort a stack using recursion

# Recursive method to insert element in sorted way


def sortedInsert(s, element):

	# Base case: Either stack is empty or newly inserted
	# item is greater than top (more than all existing)
	if len(s) == 0 or element > s[-1]:
		s.append(element)
		return
	else:

		# Remove the top item and recur
		temp = s.pop()
		sortedInsert(s, element)

		# Put back the top item removed earlier
		s.append(temp)

# Method to sort stack


def sortStack(s):

	# If stack is not empty
	if len(s) != 0:

		# Remove the top item
		temp = s.pop()

		# Sort remaining stack
		sortStack(s)

		# Push the top item back in sorted stack
		sortedInsert(s, temp)

# Printing contents of stack


def printStack(s):
	for i in s[::-1]:
		print(i, end=" ")
	print()


# Driver Code
if __name__ == '__main__':
	s = []
	s.append(30)
	s.append(-5)
	s.append(18)
	s.append(14)
	s.append(-3)

	print("Stack elements before sorting: ")
	printStack(s)

	sortStack(s)

	print("\nStack elements after sorting: ")
	printStack(s)

Los códigos anteriores da los siguientes datos:

Apilar elementos antes de ordenar:
-3 14 18 -5 30

Apilar elementos después de ordenar:
30 18 14 -3 -5

Organizar los elementos de la pila usando otra pila

Los elementos de una pila en particular se pueden organizar usando otra pila temporal, y esto se puede hacer siguiendo el siguiente algoritmo:

  1. Cree una pila temporal ( tmpStack por ejemplo).
  2. Siempre que la pila original no esté vacía, se debe hacer lo siguiente:
    1. Desproteja un elemento de la pila original y asígnele el nombre temp.
    2. Siempre que la pila temporal no esté vacía y el valor del elemento superior en la pila temporal sea mayor que el valor de temp arrastre un elemento de la pila temporal y lo empujamos a la pila original.
    3. Empuje el elemento temp en la pila.
  3. Los números ordenados estarán en la pila temporal tmpStack.

Este algoritmo se puede representar mediante los siguientes pasos simplificados:

input: [34, 3, 31, 98, 92, 23]

Elemento tomado: 23
input: [34, 3, 31, 98, 92]
tmpStack: [23]

Elemento tomado: 92
input: [34, 3, 31, 98]
tmpStack: [23, 92]

Elemento tomado:: 98
input: [34, 3, 31]
tmpStack: [23, 92, 98]

Elemento tomado: 31
input: [34, 3, 98, 92]
tmpStack: [23, 31]

Elemento tomado: 92
input: [34, 3, 98]
tmpStack: [23, 31, 92]

Elemento tomado: 98
input: [34, 3]
tmpStack: [23, 31, 92, 98]

Elemento tomado: 3
input: [34, 98, 92, 31, 23]
tmpStack: [3]

Elemento tomado: 23
input: [34, 98, 92, 31]
tmpStack: [3, 23]

Elemento tomado: 31
input: [34, 98, 92]
tmpStack: [3, 23, 31]

Elemento tomado: 92
input: [34, 98]
tmpStack: [3, 23, 31, 92]

Elemento tomado: 98
input: [34]
tmpStack: [3, 23, 31, 92, 98]

Elemento tomado: 34
input: [98, 92]
tmpStack: [3, 23, 31, 34]

Elemento tomado: 92
input: [98]
tmpStack: [3, 23, 31, 34, 92]

Elemento tomado: 98
input: []
tmpStack: [3, 23, 31, 34, 92, 98]

final sorted list: [3, 23, 31, 34, 92, 98]

Ejemplos y aplicaciones en código

Los siguientes ejemplos muestran cómo organizar los elementos de la pila utilizando otra pila temporal y en varios lenguajes de programación:

// C++ program to sort a stack using an
// auxiliary stack.
#include <bits/stdc++.h>
using namespace std;

// This function return the sorted stack
stack<int> sortStack(stack<int> &input)
{
	stack<int> tmpStack;

	while (!input.empty())
	{
		// pop out the first element
		int tmp = input.top();
		input.pop();

		// while temporary stack is not empty and top
		// of stack is greater than temp
		while (!tmpStack.empty() && tmpStack.top() > tmp)
		{
			// pop from temporary stack and push
			// it to the input stack
			input.push(tmpStack.top());
			tmpStack.pop();
		}

		// push temp in temporary of stack
		tmpStack.push(tmp);
	}

	return tmpStack;
}

// main function
int main()
{
	stack<int> input;
	input.push(34);
	input.push(3);
	input.push(31);
	input.push(98);
	input.push(92);
	input.push(23);

	// This is the temporary stack
	stack<int> tmpStack = sortStack(input);
	cout << "Sorted numbers are:\n";

	while (!tmpStack.empty())
	{
		cout << tmpStack.top()<< " ";
		tmpStack.pop();
	}
}
# Python program to sort a
# stack using auxiliary stack.

# This function return the sorted stack
def sortStack ( stack ):
	tmpStack = createStack()
	while(isEmpty(stack) == False):
		
		# pop out the first element
		tmp = top(stack)
		pop(stack)

		# while temporary stack is not
		# empty and top of stack is
		# greater than temp
		while(isEmpty(tmpStack) == False and
			int(top(tmpStack)) > int(tmp)):
			
			# pop from temporary stack and
			# push it to the input stack
			push(stack,top(tmpStack))
			pop(tmpStack)

		# push temp in temporary of stack
		push(tmpStack,tmp)
	
	return tmpStack

# Below is a complete running
# program for testing above
# function.

# Function to create a stack.
# It initializes size of stack
# as 0
def createStack():
	stack = []
	return stack

# Function to check if
# the stack is empty
def isEmpty( stack ):
	return len(stack) == 0

# Function to push an
# item to stack
def push( stack, item ):
	stack.append( item )

# Function to get top
# item of stack
def top( stack ):
	p = len(stack)
	return stack[p-1]

# Function to pop an
# item from stack
def pop( stack ):

	# If stack is empty
	# then error
	if(isEmpty( stack )):
		print("Stack Underflow ")
		exit(1)

	return stack.pop()

# Function to print the stack
def prints(stack):
	for i in range(len(stack)-1, -1, -1):
		print(stack[i], end = ' ')
	print()

# Driver Code
stack = createStack()
push( stack, str(34) )
push( stack, str(3) )
push( stack, str(31) )
push( stack, str(98) )
push( stack, str(92) )
push( stack, str(23) )

print("Sorted numbers are: ")
sortedst = sortStack ( stack )
prints(sortedst)
// Java program to sort a stack using
// a auxiliary stack.
import java.util.*;

class SortStack
{
	// This function return the sorted stack
	public static Stack<Integer> sortstack(Stack<Integer>
											input)
	{
		Stack<Integer> tmpStack = new Stack<Integer>();
		while(!input.isEmpty())
		{
			// pop out the first element
			int tmp = input.pop();
		
			// while temporary stack is not empty and
			// top of stack is greater than temp
			while(!tmpStack.isEmpty() && tmpStack.peek()
												> tmp)
			{
				// pop from temporary stack and
				// push it to the input stack
			input.push(tmpStack.pop());
			}
			
			// push temp in temporary of stack
			tmpStack.push(tmp);
		}
		return tmpStack;
	}
	
	// Driver Code
	public static void main(String args[])
	{
		Stack<Integer> input = new Stack<Integer>();
		input.add(34);
		input.add(3);
		input.add(31);
		input.add(98);
		input.add(92);
		input.add(23);
	
		// This is the temporary stack
		Stack<Integer> tmpStack=sortstack(input);
		System.out.println("Sorted numbers are:");
	
		while (!tmpStack.empty())
		{
			System.out.print(tmpStack.pop()+" ");
		}
	}
}

Fuentes del Artículo