¿Cómo implementar una cola usando dos pilas?
Supongamos que tenemos dos pilas y ninguna otra variable temporal.
¿Es posible "construir" una estructura de datos de cola utilizando solo las dos pilas?
Mantén 2 pilas, llamémoslas inbox y outbox.
Encolar :
- Empuje el nuevo elemento en
inbox
Dequeue :
Si
outboxestá vacío, rellénelo haciendo estallar cada elemento deinboxy presionándolo sobreoutboxPop y devuelve el elemento superior de
outbox
Usando este método, cada elemento estará en cada pila exactamente una vez, lo que significa que cada elemento se empujará dos veces y se abrirá dos veces, dando operaciones de tiempo constante amortizado.
Aquí hay una implementación en Java:
public class Queue<E>
{
private Stack<E> inbox = new Stack<E>();
private Stack<E> outbox = new Stack<E>();
public void queue(E item) {
inbox.Push(item);
}
public E dequeue() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.Push(inbox.pop());
}
}
return outbox.pop();
}
}
A - Cómo invertir una pila
Para entender cómo construir una cola usando dos pilas, debes entender cómo revertir una pila de forma clara. Recuerda cómo funciona la pila, es muy similar a la pila de platos en tu cocina. El último plato lavado estará en la parte superior de la pila limpia, que se llama L ast I n F irst O ut (LIFO) en informática.
Imaginemos nuestra pila como una botella como abajo;
Si presionamos enteros 1,2,3 respectivamente, entonces 3 estarán en la parte superior de la pila. Debido a que 1 será empujado primero, luego 2 se colocará en la parte superior de 1. Finalmente, 3 se colocará en la parte superior de la pila y el último estado de nuestra pila representada como una botella será la siguiente:
Ahora tenemos nuestra pila representada ya que una botella se rellena con valores 3,2,1. Y queremos invertir la pila para que el elemento superior de la pila sea 1 y el elemento inferior de la pila sea 3. ¿Qué podemos hacer? ¿Podemos tomar la botella y mantenerla boca abajo para que todos los valores se inviertan en orden?
Sí podemos hacerlo, pero eso es una botella. Para hacer el mismo proceso, necesitamos tener una segunda pila que almacenará los primeros elementos de la pila en orden inverso. Pongamos nuestra pila poblada a la izquierda y nuestra nueva pila vacía a la derecha. Para invertir el orden de los elementos, vamos a hacer estallar cada elemento de la pila izquierda y empujarlos a la pila derecha. Puedes ver lo que sucede a medida que lo hacemos en la imagen de abajo;
Así que sabemos cómo revertir una pila.
B - Usando dos pilas como una cola
En la parte anterior, he explicado cómo podemos invertir el orden de los elementos de pila. Esto fue importante, ya que si presionamos y colocamos elementos en la pila, la salida será exactamente en el orden inverso de una cola. Pensando en un ejemplo, empujemos la matriz de enteros {1, 2, 3, 4, 5} a una pila. Si hacemos estallar los elementos e imprimimos hasta que la pila esté vacía, obtendremos la matriz en el orden inverso al orden de empuje, que será {5, 4, 3, 2, 1} Recuerde que para la misma entrada, si sacamos la cola de la cola hasta que la cola esté vacía, la salida será {1, 2, 3, 4, 5}. Por lo tanto, es obvio que para el mismo orden de entrada de elementos, la salida de la cola es exactamente la inversa de la salida de una pila. Como sabemos cómo invertir una pila usando una pila extra, podemos construir una cola usando dos pilas.
Nuestro modelo de cola constará de dos pilas. Se utilizará una pila para la operación enqueue (pila n. ° 1 a la izquierda, se llamará como pila de entrada), otra pila se utilizará para la operación dequeue (pila n. ° 2 a la derecha, se llamará como pila de salida). Echa un vistazo a la imagen de abajo;
Nuestro pseudo-código es el siguiente;
Operación en cola
Push every input element to the Input Stack
Operación Dequeue
If ( Output Stack is Empty)
pop every element in the Input Stack
and Push them to the Output Stack until Input Stack is Empty
pop from Output Stack
Pongamos en cola los números enteros {1, 2, 3} respectivamente. Los enteros se presionarán en la Pila de entrada (Pila # 1) que se encuentra a la izquierda;
Entonces, ¿qué sucederá si ejecutamos una operación de salida? Cada vez que se ejecuta una operación de salida de cola, la cola comprobará si la Pila de salida está vacía o no (vea el pseudo-código arriba) Si la Pila de salida está vacía, entonces la Pila de entrada se extraerá en la salida para que los elementos de la pila de entrada se invertirá. Antes de devolver un valor, el estado de la cola será el siguiente;
Verifique el orden de los elementos en la pila de salida (pila n. ° 2). Es obvio que podemos extraer los elementos de la pila de salida para que la salida sea la misma que si se sacara de la cola. Por lo tanto, si ejecutamos dos operaciones de salida de cola, primero obtendremos {1, 2} respectivamente. Entonces el elemento 3 será el único elemento de la pila de salida, y la pila de entrada estará vacía. Si ponemos en cola los elementos 4 y 5, entonces el estado de la cola será el siguiente;
Ahora, la Pila de salida no está vacía, y si ejecutamos una operación de salida de cola, solo 3 saldrán de la Pila de salida. Entonces el estado será visto como abajo;
Nuevamente, si ejecutamos dos operaciones más de salida de cola, en la primera operación de salida, la cola verificará si la Pila de salida está vacía, lo cual es cierto. Luego saque los elementos de la pila de entrada y empújelos a la pila de salida hasta que la pila de entrada esté vacía, entonces el estado de la cola será el siguiente:
Fácil de ver, la salida de las dos operaciones de salida de la cola será {4, 5}
C - Implementación de la cola construida con dos pilas
Aquí hay una implementación en Java. No voy a usar la implementación existente de Stack, por lo que el ejemplo aquí va a reinventar la rueda;
C - 1) Clase MyStack: una implementación de pila simple
public class MyStack<T> {
// inner generic Node class
private class Node<T> {
T data;
Node<T> next;
public Node(T data) {
this.data = data;
}
}
private Node<T> head;
private int size;
public void Push(T e) {
Node<T> newElem = new Node(e);
if(head == null) {
head = newElem;
} else {
newElem.next = head;
head = newElem; // new elem on the top of the stack
}
size++;
}
public T pop() {
if(head == null)
return null;
T elem = head.data;
head = head.next; // top of the stack is head.next
size--;
return elem;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void printStack() {
System.out.print("Stack: ");
if(size == 0)
System.out.print("Empty !");
else
for(Node<T> temp = head; temp != null; temp = temp.next)
System.out.printf("%s ", temp.data);
System.out.printf("\n");
}
}
C - 2) Clase MyQueue: Implementación de cola usando dos pilas
public class MyQueue<T> {
private MyStack<T> inputStack; // for enqueue
private MyStack<T> outputStack; // for dequeue
private int size;
public MyQueue() {
inputStack = new MyStack<>();
outputStack = new MyStack<>();
}
public void enqueue(T e) {
inputStack.Push(e);
size++;
}
public T dequeue() {
// fill out all the Input if output stack is empty
if(outputStack.isEmpty())
while(!inputStack.isEmpty())
outputStack.Push(inputStack.pop());
T temp = null;
if(!outputStack.isEmpty()) {
temp = outputStack.pop();
size--;
}
return temp;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}
C - 3) Código de demostración
public class TestMyQueue {
public static void main(String[] args) {
MyQueue<Integer> queue = new MyQueue<>();
// enqueue integers 1..3
for(int i = 1; i <= 3; i++)
queue.enqueue(i);
// execute 2 dequeue operations
for(int i = 0; i < 2; i++)
System.out.println("Dequeued: " + queue.dequeue());
// enqueue integers 4..5
for(int i = 4; i <= 5; i++)
queue.enqueue(i);
// dequeue the rest
while(!queue.isEmpty())
System.out.println("Dequeued: " + queue.dequeue());
}
}
C - 4) Salida de muestra
Dequeued: 1
Dequeued: 2
Dequeued: 3
Dequeued: 4
Dequeued: 5
Incluso puedes simular una cola usando solo una pila. La segunda pila (temporal) puede simularse mediante la pila de llamadas de llamadas recursivas al método de inserción.
El principio sigue siendo el mismo cuando se inserta un nuevo elemento en la cola:
- Necesitas transferir elementos de una pila a otra pila temporal para revertir su orden.
- Luego, empuje el nuevo elemento a insertar, en la pila temporal
- Luego transfiere los elementos a la pila original
- El nuevo elemento estará en la parte inferior de la pila, y el elemento más antiguo estará en la parte superior (el primero que se abrirá)
Una clase de cola que usa solo una pila, sería la siguiente:
public class SimulatedQueue<E> {
private Java.util.Stack<E> stack = new Java.util.Stack<E>();
public void insert(E elem) {
if (!stack.empty()) {
E topElem = stack.pop();
insert(elem);
stack.Push(topElem);
}
else
stack.Push(elem);
}
public E remove() {
return stack.pop();
}
}
Sin embargo, las complejidades del tiempo serían peores. Una buena implementación de cola hace todo en tiempo constante.
Editar
No estoy seguro de por qué mi respuesta ha sido rechazada aquí. Si programamos, nos preocupa la complejidad del tiempo y el uso de dos pilas estándar para hacer una cola es ineficiente. Es un punto muy válido y relevante. Si alguien más siente la necesidad de votar más abajo, me gustaría saber por qué.
Un poco más de detalle : sobre por qué usar dos pilas es peor que solo una cola: si usa dos pilas, y alguien llama a la cola de salida cuando la bandeja de salida está vacía, necesita tiempo lineal para llegar al final bandeja de entrada (como se puede ver en el código de Dave).
Puede implementar una cola como una lista enlazada individualmente (cada elemento apunta al siguiente elemento insertado), manteniendo un puntero adicional al último elemento insertado para los empujes (o convirtiéndolo en una lista cíclica). Implementar la cola y la cola de espera en esta estructura de datos es muy fácil de hacer en un tiempo constante. Ese es el peor de los casos en tiempo constante, no amortizado. Y, como los comentarios parecen pedir esta aclaración, el tiempo constante en el peor de los casos es estrictamente mejor que el tiempo constante amortizado.
Deje que la cola a ser implementada sea q y las pilas utilizadas para implementar q sean pila1 y pila2.
q se puede implementar en dos maneras:
Método 1 (haciendo que la operación enQueue sea costosa)
Este método se asegura de que el elemento recién ingresado esté siempre en la parte superior de la pila 1, de modo que la operación de DEQueue simplemente salga de la pila1. Para poner el elemento en la parte superior de stack1, se usa stack2.
enQueue(q, x)
1) While stack1 is not empty, Push everything from stack1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
deQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it.
Método 2 (haciendo que la operación de DEQueue sea costosa)
En este método, en la operación en cola, el nuevo elemento se ingresa en la parte superior de stack1. En la operación de cola de espera, si la pila2 está vacía, todos los elementos se mueven a la pila2 y finalmente se devuelve la parte superior de la pila2.
enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, Push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.
El método 2 es definitivamente mejor que el método 1. El método 1 mueve todos los elementos dos veces en la operación enQueue, mientras que el método 2 (en la operación deQueue) mueve los elementos una vez y mueve los elementos solo si la pila2 está vacía.
Una solución en c #
public class Queue<T> where T : class
{
private Stack<T> input = new Stack<T>();
private Stack<T> output = new Stack<T>();
public void Enqueue(T t)
{
input.Push(t);
}
public T Dequeue()
{
if (output.Count == 0)
{
while (input.Count != 0)
{
output.Push(input.Pop());
}
}
return output.Pop();
}
}
Tendrás que sacar todo de la primera pila para obtener el elemento inferior. Luego, vuelva a colocarlos en la segunda pila para cada operación de "salida de cola".
para c # developer aquí está el programa completo:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace QueueImplimentationUsingStack
{
class Program
{
public class Stack<T>
{
public int size;
public Node<T> head;
public void Push(T data)
{
Node<T> node = new Node<T>();
node.data = data;
if (head == null)
head = node;
else
{
node.link = head;
head = node;
}
size++;
Display();
}
public Node<T> Pop()
{
if (head == null)
return null;
else
{
Node<T> temp = head;
//temp.link = null;
head = head.link;
size--;
Display();
return temp;
}
}
public void Display()
{
if (size == 0)
Console.WriteLine("Empty");
else
{
Console.Clear();
Node<T> temp = head;
while (temp!= null)
{
Console.WriteLine(temp.data);
temp = temp.link;
}
}
}
}
public class Queue<T>
{
public int size;
public Stack<T> inbox;
public Stack<T> outbox;
public Queue()
{
inbox = new Stack<T>();
outbox = new Stack<T>();
}
public void EnQueue(T data)
{
inbox.Push(data);
size++;
}
public Node<T> DeQueue()
{
if (outbox.size == 0)
{
while (inbox.size != 0)
{
outbox.Push(inbox.Pop().data);
}
}
Node<T> temp = new Node<T>();
if (outbox.size != 0)
{
temp = outbox.Pop();
size--;
}
return temp;
}
}
public class Node<T>
{
public T data;
public Node<T> link;
}
static void Main(string[] args)
{
Queue<int> q = new Queue<int>();
for (int i = 1; i <= 3; i++)
q.EnQueue(i);
// q.Display();
for (int i = 1; i < 3; i++)
q.DeQueue();
//q.Display();
Console.ReadKey();
}
}
}
Dos pilas en la cola se definen como pila1 y pila2.
En cola: Los elementos euqueued siempre se insertan en pila1
Dequeue: La parte superior de pila2 puede ser desplegado ya que es el primer elemento insertado en la cola cuando pila2 no está vacío. Cuando pila2 está vacío, sacamos todos los elementos de pila1 y empujarlos en pila2 uno a uno. El primer elemento de una cola se inserta en la parte inferior de pila1. Se puede desplegar directamente después de las operaciones de popping y push ya que está en la parte superior de pila2.
El siguiente es el mismo código de ejemplo de C++:
template <typename T> class CQueue
{
public:
CQueue(void);
~CQueue(void);
void appendTail(const T& node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};
template<typename T> void CQueue<T>::appendTail(const T& element) {
stack1.Push(element);
}
template<typename T> T CQueue<T>::deleteHead() {
if(stack2.size()<= 0) {
while(stack1.size()>0) {
T& data = stack1.top();
stack1.pop();
stack2.Push(data);
}
}
if(stack2.size() == 0)
throw new exception("queue is empty");
T head = stack2.top();
stack2.pop();
return head;
}
Esta solución es prestada de mi blog . El análisis más detallado con simulaciones de operación paso a paso está disponible en la página web de mi blog.
// Two stacks s1 Original and s2 as Temp one
private Stack<Integer> s1 = new Stack<Integer>();
private Stack<Integer> s2 = new Stack<Integer>();
/*
* Here we insert the data into the stack and if data all ready exist on
* stack than we copy the entire stack s1 to s2 recursively and Push the new
* element data onto s1 and than again recursively call the s2 to pop on s1.
*
* Note here we can use either way ie We can keep pushing on s1 and than
* while popping we can remove the first element from s2 by copying
* recursively the data and removing the first index element.
*/
public void insert( int data )
{
if( s1.size() == 0 )
{
s1.Push( data );
}
else
{
while( !s1.isEmpty() )
{
s2.Push( s1.pop() );
}
s1.Push( data );
while( !s2.isEmpty() )
{
s1.Push( s2.pop() );
}
}
}
public void remove()
{
if( s1.isEmpty() )
{
System.out.println( "Empty" );
}
else
{
s1.pop();
}
}
Una implementación de una cola usando dos pilas en Swift:
struct Stack<Element> {
var items = [Element]()
var count : Int {
return items.count
}
mutating func Push(_ item: Element) {
items.append(item)
}
mutating func pop() -> Element? {
return items.removeLast()
}
func peek() -> Element? {
return items.last
}
}
struct Queue<Element> {
var inStack = Stack<Element>()
var outStack = Stack<Element>()
mutating func enqueue(_ item: Element) {
inStack.Push(item)
}
mutating func dequeue() -> Element? {
fillOutStack()
return outStack.pop()
}
mutating func peek() -> Element? {
fillOutStack()
return outStack.peek()
}
private mutating func fillOutStack() {
if outStack.count == 0 {
while inStack.count != 0 {
outStack.Push(inStack.pop()!)
}
}
}
}
Si bien obtendrá una gran cantidad de publicaciones relacionadas con la implementación de una cola con dos acumulaciones: 1. Haciendo que el proceso de enQueue sea mucho más costoso 2. O haciendo que el proceso de deQueue sea mucho más costoso
https://www.geeksforgeeks.org/queue-using-stacks/
Una forma importante que descubrí en la publicación anterior fue construir una cola con solo la estructura de datos de la pila y la pila de llamadas de recursión.
Si bien se puede argumentar que, literalmente, esto todavía está usando dos pilas, pero idealmente, se está usando solo una estructura de datos de pila.
A continuación se muestra la explicación del problema:
Declare una sola pila para enQueuing y deQueing los datos y empuje los datos en la pila.
mientras que el deQueueing tiene una condición base donde el elemento de la pila se abre cuando el tamaño de la pila es 1. Esto asegurará que no haya un desbordamiento de pila durante la recursión del deQueue.
Mientras que deQueueing primero pop los datos de la parte superior de la pila. Idealmente, este elemento será el elemento que está presente en la parte superior de la pila. Ahora, una vez hecho esto, recursivamente llame a la función deQueue y luego presione el elemento que se encuentra arriba en la pila.
El código se verá a continuación:
if (s1.isEmpty())
System.out.println("The Queue is empty");
else if (s1.size() == 1)
return s1.pop();
else {
int x = s1.pop();
int result = deQueue();
s1.Push(x);
return result;
De esta manera, puede crear una cola utilizando una estructura de datos de pila única y la pila de llamadas de recursión.
aquí está mi solución en Java usando la lista enlazada.
class queue<T>{
static class Node<T>{
private T data;
private Node<T> next;
Node(T data){
this.data = data;
next = null;
}
}
Node firstTop;
Node secondTop;
void Push(T data){
Node temp = new Node(data);
temp.next = firstTop;
firstTop = temp;
}
void pop(){
if(firstTop == null){
return;
}
Node temp = firstTop;
while(temp != null){
Node temp1 = new Node(temp.data);
temp1.next = secondTop;
secondTop = temp1;
temp = temp.next;
}
secondTop = secondTop.next;
firstTop = null;
while(secondTop != null){
Node temp3 = new Node(secondTop.data);
temp3.next = firstTop;
firstTop = temp3;
secondTop = secondTop.next;
}
}
}
Nota: En este caso, la operación de pop consume mucho tiempo. Así que no sugeriré crear una cola usando dos pilas.
Responderé esta pregunta en Go porque Go no tiene una gran cantidad de colecciones en su biblioteca estándar.
Dado que una pila es realmente fácil de implementar, pensé que intentaría usar dos pilas para lograr una cola de doble finalización. Para comprender mejor cómo llegué a mi respuesta, he dividido la implementación en dos partes, es de esperar que la primera parte sea más fácil de entender, pero está incompleta.
type IntQueue struct {
front []int
back []int
}
func (q *IntQueue) PushFront(v int) {
q.front = append(q.front, v)
}
func (q *IntQueue) Front() int {
if len(q.front) > 0 {
return q.front[len(q.front)-1]
} else {
return q.back[0]
}
}
func (q *IntQueue) PopFront() {
if len(q.front) > 0 {
q.front = q.front[:len(q.front)-1]
} else {
q.back = q.back[1:]
}
}
func (q *IntQueue) PushBack(v int) {
q.back = append(q.back, v)
}
func (q *IntQueue) Back() int {
if len(q.back) > 0 {
return q.back[len(q.back)-1]
} else {
return q.front[0]
}
}
func (q *IntQueue) PopBack() {
if len(q.back) > 0 {
q.back = q.back[:len(q.back)-1]
} else {
q.front = q.front[1:]
}
}
Son básicamente dos pilas donde permitimos que la parte inferior de las pilas se manipulen unas con otras. También he usado las convenciones de nomenclatura de STL, donde las operaciones tradicionales de empujar, estallar y echar un vistazo de una pila tienen un prefijo delantero/trasero, ya sea que se refieran al frente o al dorso de la cola.
El problema con el código anterior es que no usa la memoria de manera muy eficiente. En realidad, crece sin cesar hasta que te quedas sin espacio. Es realmente malo. La solución para esto es simplemente reutilizar la parte inferior del espacio de la pila siempre que sea posible. Tenemos que introducir un desplazamiento para hacer un seguimiento de esto, ya que una porción en Ir no puede crecer en el frente una vez que se ha reducido.
type IntQueue struct {
front []int
frontOffset int
back []int
backOffset int
}
func (q *IntQueue) PushFront(v int) {
if q.backOffset > 0 {
i := q.backOffset - 1
q.back[i] = v
q.backOffset = i
} else {
q.front = append(q.front, v)
}
}
func (q *IntQueue) Front() int {
if len(q.front) > 0 {
return q.front[len(q.front)-1]
} else {
return q.back[q.backOffset]
}
}
func (q *IntQueue) PopFront() {
if len(q.front) > 0 {
q.front = q.front[:len(q.front)-1]
} else {
if len(q.back) > 0 {
q.backOffset++
} else {
panic("Cannot pop front of empty queue.")
}
}
}
func (q *IntQueue) PushBack(v int) {
if q.frontOffset > 0 {
i := q.frontOffset - 1
q.front[i] = v
q.frontOffset = i
} else {
q.back = append(q.back, v)
}
}
func (q *IntQueue) Back() int {
if len(q.back) > 0 {
return q.back[len(q.back)-1]
} else {
return q.front[q.frontOffset]
}
}
func (q *IntQueue) PopBack() {
if len(q.back) > 0 {
q.back = q.back[:len(q.back)-1]
} else {
if len(q.front) > 0 {
q.frontOffset++
} else {
panic("Cannot pop back of empty queue.")
}
}
}
Son muchas funciones pequeñas, pero de las 6 funciones, 3 de ellas son solo espejos de la otra.
A continuación se muestra la solución en lenguaje javascript utilizando la sintaxis ES6.
Stack.js
//stack using array
class Stack {
constructor() {
this.data = [];
}
Push(data) {
this.data.Push(data);
}
pop() {
return this.data.pop();
}
peek() {
return this.data[this.data.length - 1];
}
size(){
return this.data.length;
}
}
export { Stack };
QueueUsingTwoStacks.js
import { Stack } from "./Stack";
class QueueUsingTwoStacks {
constructor() {
this.stack1 = new Stack();
this.stack2 = new Stack();
}
enqueue(data) {
this.stack1.Push(data);
}
dequeue() {
//if both stacks are empty, return undefined
if (this.stack1.size() === 0 && this.stack2.size() === 0)
return undefined;
//if stack2 is empty, pop all elements from stack1 to stack2 till stack1 is empty
if (this.stack2.size() === 0) {
while (this.stack1.size() !== 0) {
this.stack2.Push(this.stack1.pop());
}
}
//pop and return the element from stack 2
return this.stack2.pop();
}
}
export { QueueUsingTwoStacks };
A continuación se muestra el uso:
index.js
import { StackUsingTwoQueues } from './StackUsingTwoQueues';
let que = new QueueUsingTwoStacks();
que.enqueue("A");
que.enqueue("B");
que.enqueue("C");
console.log(que.dequeue()); //output: "A"
public class QueueUsingStacks<T>
{
private LinkedListStack<T> stack1;
private LinkedListStack<T> stack2;
public QueueUsingStacks()
{
stack1=new LinkedListStack<T>();
stack2 = new LinkedListStack<T>();
}
public void Copy(LinkedListStack<T> source,LinkedListStack<T> dest )
{
while(source.Head!=null)
{
dest.Push(source.Head.Data);
source.Head = source.Head.Next;
}
}
public void Enqueue(T entry)
{
stack1.Push(entry);
}
public T Dequeue()
{
T obj;
if (stack2 != null)
{
Copy(stack1, stack2);
obj = stack2.Pop();
Copy(stack2, stack1);
}
else
{
throw new Exception("Stack is empty");
}
return obj;
}
public void Display()
{
stack1.Display();
}
}
Para cada operación de puesta en cola, agregamos a la parte superior de la pila1. Para cada salida de cola, vaciamos el contenido de stack1 en stack2, y eliminamos el elemento en la parte superior de la pila. La complejidad del tiempo es O(n) para dequeue, ya que tenemos que copiar la pila1 en stack2. La complejidad de tiempo de la puesta en cola es la misma que una pila regular
Con O(1)dequeue(), que es igual que pythonquick's answer :
// time: O(n), space: O(n)
enqueue(x):
if stack.isEmpty():
stack.Push(x)
return
temp = stack.pop()
enqueue(x)
stack.Push(temp)
// time: O(1)
x dequeue():
return stack.pop()
Con O(1)enqueue() (esto no se menciona en esta publicación, por lo que esta respuesta), que también utiliza la función de retroceso para aumentar la velocidad y devolver el elemento más inferior.
// O(1)
enqueue(x):
stack.Push(x)
// time: O(n), space: O(n)
x dequeue():
temp = stack.pop()
if stack.isEmpty():
x = temp
else:
x = dequeue()
stack.Push(temp)
return x
Obviamente, es un buen ejercicio de codificación, ya que es ineficiente pero elegante a pesar de todo.