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
- Ejecución de pila e implementación usando arreglos
- Crear pilas usando colas
- Invertir elementos de pila usando una función recursiva
- Organice los elementos de la pila usando funciones recursivas
- Ejemplos y aplicación en código
- Organizar los elementos de la pila usando otra pila
- Fuentes del Artículo
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 q1
y q2
) 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 q1
y, 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:
- El proceso
push(s, x)
dondex
se agrega el elemento y la pilas
a la que se agrega el elemento.- Además
x
de la colaq2
. - Retire todos los elementos de la cola
q1
uno por uno y los agrega a la colaq2
. - Cambie los nombres de los marcos
q1
yq2
, el objetivo es evitar mover todos los elementos del marcoq2
alq1
.
- Además
- proceso
pop(s)
:- Retire el artículo
q1
y lo devuelve.
- Retire el artículo
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 lugarqueue
):
# 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:
- proceso
push(s, x)
:- Agregado
x
al marcoq1
(suponiendo queq1
no se especifica el tamaño del marco).
- Agregado
- proceso
pop(s)
:- Quite los elementos uno por uno excepto el último elemento de la cola
q1
y los agrega a la colaq2
. - Elimina el último elemento de la cola q1 y es guardado.
- Cambie los nombres de los dos marcos
q1
yq2
, el objetivo es evitar que el proceso de mover todos los elementos del marcoq2
aq1
. - Devuelve el artículo almacenado en el segundo paso.
- Quite los elementos uno por uno excepto el último elemento de la cola
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 while
y for
, 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:
- Cree una pila temporal (
tmpStack
por ejemplo). - Siempre que la pila original no esté vacía, se debe hacer lo siguiente:
- Desproteja un elemento de la pila original y asígnele el nombre
temp
. - 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. - Empuje el elemento
temp
en la pila.
- Desproteja un elemento de la pila original y asígnele el nombre
- 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
- Página de documentación de estructura de datos de GeekforGeeks Estructura de datos de pila (introducción y programa).
- Página de documentación de estructuras de datos en GeeksforGeeks Implemente Stack usando Colas.
- Página de documentación de estructuras de datos en GeeksforGeeks Invertir una pila usando recursividad.
- Página de documentación de estructuras de datos en GeeksforGeeks Ordene una pila usando la recursión.
- Página de documentación de estructuras de datos en GeeksforGeeks Ordenar pila usando una pila temporal.
- Múltiples Constantes en TypeScript
- Estructura de Datos las Colas
- Estructura de Datos las Pilas (Stack)
- Widget Drawer en Flutter
- Clase Scaffold en Flutter
- Estructura del lenguaje Python
- Iteradores y generadores en TypeScript
- Símbolo en TypeScript (Symbol)
- Tipos Avanzados en TypeScript
- Tipos de Compatibilidad en TypeScript
- Inferir Tipos en TypeScript
- Tipos Generalizados (Generics) en TypeScript
- Tipos Básicos de Datos en TypeScript
- Interfaces en TypeScript
- Declaración de Variables en TypeScript
- Funciones en TypeScript
- Categorías en TypeScript
- Introducción a TypeScript
- Clase MaterialApp en Flutter
- Clase Container en Flutter
- ¿Qué son los Widgets en Flutter?
- Introducción a la Arquitectura de Aplicaciones con Flutter
- Lista Doblemente Enlazada
- Listas Vinculadas en Estructura de Datos
- Introducción a las Matrices(Arrays)
- Estructuras de Datos en los Algoritmos de Programación
- Expresión const en JavaScript
- Expresión let en JavaScript
- Introducción al Lenguaje de Programación CSS
- Intérprete de Python
- Expresión var en JavaScript
- Expresión try…catch en JavaScript
- Expresión throw en JavaScript
- Continue en JavaScript
- Switch en JavaScript
- Expresiones if…else en JavaScript
- Declaración vacía o empty en JavaScript
- Break en JavaScript
- Sentencia block en JavaScript
- Arguments en JavaScript
- Promise en JavaScript
- Number en JavaScript
- Características JSON en JavaScript
- Array en JavaScript