Implementar stack usando dos colas

Se hizo una pregunta similar anteriormente, pero la pregunta aquí es al revés, usando dos colas como stack. La pregunta…

Dadas dos colas con sus operaciones estándar (en enqueue , dequeue , isempty , size ), implementa una stack con sus operaciones estándar ( pop , push , isempty , size ).

Debe haber dos versiones de la solución.

  • Versión A : la stack debe ser eficiente al empujar un elemento; y
  • Versión B : la stack debe ser eficiente al abrir un elemento.

Estoy interesado en el algoritmo más que en cualquier implementación de lenguaje específico. Sin embargo, doy la bienvenida a las soluciones expresadas en los idiomas que estoy familiarizado ( java , c # , python , vb , javascript , php ).

Versión A (push eficiente):

  • empujar:
    • poner en cola en queue1
  • popular:
    • mientras que el tamaño de queue1 es mayor que 1, canalice los artículos descatalogados de queue1 a queue2
    • dequeue y devuelve el último elemento de queue1, luego cambia los nombres de queue1 y queue2

Versión B (pop eficiente):

  • empujar:
    • enqueue en queue2
    • poner en cola todos los elementos de queue1 en queue2, luego cambiar los nombres de queue1 y queue2
  • popular:
    • deqeue de queue1

La manera más fácil (y tal vez única) de hacerlo es empujando los nuevos elementos en la cola vacía, y luego eliminando el otro y entrando en la cola previamente vacía. De esta manera, lo último siempre está al frente de la cola. Esta sería la versión B, para la versión A, simplemente invierte el proceso decazando los elementos en la segunda fila, excepto la última.

Paso 0:

 "Stack" +---+---+---+---+---+ | | | | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | | | | | | | | | | | | +---+---+---+---+---+ +---+---+---+---+---+ 

Paso 1:

 "Stack" +---+---+---+---+---+ | 1 | | | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | 1 | | | | | | | | | | | +---+---+---+---+---+ +---+---+---+---+---+ 

Paso 2:

 "Stack" +---+---+---+---+---+ | 2 | 1 | | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | | | | | | | 2 | 1 | | | | +---+---+---+---+---+ +---+---+---+---+---+ 

Paso 3:

 "Stack" +---+---+---+---+---+ | 3 | 2 | 1 | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | 3 | 2 | 1 | | | | | | | | | +---+---+---+---+---+ +---+---+---+---+---+ 

Podemos hacer esto con una cola:

empujar:

  1. enqueue nuevo elemento.
  2. Si n es la cantidad de elementos en la cola, elimine e inserte el elemento n-1 veces.

popular:

  1. dequeue

.

 push 1 front +----+----+----+----+----+----+ | 1 | | | | | | insert 1 +----+----+----+----+----+----+ push2 front +----+----+----+----+----+----+ | 1 | 2 | | | | | insert 2 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | 2 | 1 | | | | remove and insert 1 +----+----+----+----+----+----+ insert 3 front +----+----+----+----+----+----+ | | 2 | 1 | 3 | | | insert 3 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | | 1 | 3 | 2 | | remove and insert 2 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | | | 3 | 2 | 1 | remove and insert 1 +----+----+----+----+----+----+ 

Implementación de ejemplo:

 int stack_pop (queue_data *q) { return queue_remove (q); } void stack_push (queue_data *q, int val) { int old_count = queue_get_element_count (q), i; queue_insert (q, val); for (i=0; i 
 import java.util.*; /** * * @author Mahmood */ public class StackImplUsingQueues { Queue q1 = new LinkedList(); Queue q2 = new LinkedList(); public int pop() { if (q1.peek() == null) { System.out.println("The stack is empty, nothing to return"); int i = 0; return i; } else { int pop = q1.remove(); return pop; } } public void push(int data) { if (q1.peek() == null) { q1.add(data); } else { for (int i = q1.size(); i > 0; i--) { q2.add(q1.remove()); } q1.add(data); for (int j = q2.size(); j > 0; j--) { q1.add(q2.remove()); } } } public static void main(String[] args) { StackImplUsingQueues s1 = new StackImplUsingQueues(); // Stack s1 = new Stack(); s1.push(1); s1.push(2); s1.push(3); s1.push(4); s1.push(5); s1.push(6); s1.push(7); s1.push(8); s1.push(9); s1.push(10); // s1.push(6); System.out.println("1st = " + s1.pop()); System.out.println("2nd = " + s1.pop()); System.out.println("3rd = " + s1.pop()); System.out.println("4th = " + s1.pop()); System.out.println("5th = " + s1.pop()); System.out.println("6th = " + s1.pop()); System.out.println("7th = " + s1.pop()); System.out.println("8th = " + s1.pop()); System.out.println("9th = " + s1.pop()); System.out.println("10th= " + s1.pop()); } } 

¿Podemos simplemente usar una cola para implementar una stack? Puedo usar dos colas, pero considerar una sola cola sería más eficiente. Aquí está el código:

  public void Push(T val) { queLower.Enqueue(val); } public T Pop() { if (queLower.Count == 0 ) { Console.Write("Stack is empty!"); return default(T); } if (queLower.Count > 0) { for (int i = 0; i < queLower.Count - 1;i++ ) { queLower.Enqueue(queLower.Dequeue ()); } } return queLower.Dequeue(); } 
 queue q1, q2; int i = 0; void push(int v) { if( q1.empty() && q2.empty() ) { q1.push(v); i = 0; } else { if( i == 0 ) { while( !q1.empty() ) q2.push(q1.pop()); q1.push(v); i = 1-i; } else { while( !q2.empty() ) q1.push(q2.pop()); q2.push(v); i = 1-i; } } } int pop() { if( q1.empty() && q2.empty() ) return -1; if( i == 1 ) { if( !q1.empty() ) return q1.pop(); else if( !q2.empty() ) return q2.pop(); } else { if( !q2.empty() ) return q2.pop(); else if( !q1.empty() ) return q1.pop(); } } 

Aquí está mi respuesta, donde el ‘pop’ es ineficiente. Parece que todos los algoritmos que vienen inmediatamente a la mente tienen N complejidad, donde N es el tamaño de la lista: si eliges hacer el trabajo en el ‘pop’ o si trabajas en el ‘push’

El algoritmo en el que las listas se intercambian y el cuarto puede ser mejor, ya que no se necesita un cálculo de tamaño, aunque aún es necesario realizar un ciclo y compararlo con el vacío.

puede probar que este algoritmo no puede escribirse más rápido que N al observar que la información sobre el último elemento en una cola solo está disponible conociendo el tamaño de la cola, y que debe destruir los datos para llegar a ese elemento, de ahí la segunda cola .

La única forma de hacerlo más rápido es no usar colas en primer lugar.

 from data_structures import queue class stack(object): def __init__(self): q1= queue q2= queue #only contains one item at most. a temp var. (bad?) def push(self, item): q1.enque(item) #just stick it in the first queue. #Pop is inefficient def pop(self): #'spin' the queues until q1 is ready to pop the right value. for N 0 to self.size-1 q2.enqueue(q1.dequeue) q1.enqueue(q2.dequeue) return q1.dequeue() @property def size(self): return q1.size + q2.size @property def isempty(self): if self.size > 0: return True else return False 

Aquí está mi solución que funciona para O (1) en el caso promedio. Hay dos colas: entrada y out . Ver pseudocódigo abajo:

 PUSH(X) = in.enqueue(X) POP: X = if (out.isEmpty and !in.isEmpty) DUMP(in, out) return out.dequeue DUMP(A, B) = if (!A.isEmpty) x = A.dequeue() DUMP(A, B) B.enqueue(x) 

Como se ha mencionado, ¿no funcionaría una sola cola? Es probablemente menos práctico, pero es un poco astuto.

 push(x): enqueue(x) for(queueSize - 1) enqueue(dequeue()) pop(x): dequeue() 

Aquí hay un pseudo código simple, push es O (n), pop / peek es O (1):

 Qpush = Qinstance() Qpop = Qinstance() def stack.push(item): Qpush.add(item) while Qpop.peek() != null: //transfer Qpop into Qpush Qpush.add(Qpop.remove()) swap = Qpush Qpush = Qpop Qpop = swap def stack.pop(): return Qpop.remove() def stack.peek(): return Qpop.peek() 

Deje que S1 y S2 sean las dos stacks que se utilizarán en la implementación de colas.

 struct Stack { struct Queue *Q1; struct Queue *Q2; } 

Nos aseguramos de que una cola esté vacía siempre.

Operación de inserción: cualquiera que sea la cola que no esté vacía, inserte el elemento en ella.

  • Compruebe si la cola Q1 está vacía o no. Si Q1 está vacío, encola el elemento en él.
  • De lo contrario, coloque el elemento en Q1.

Push (struct Stack *S, int data) { if(isEmptyQueue(S->Q1) EnQueue(S->Q2, data); else EnQueue(S->Q1, data); }

Complejidad del tiempo: O (1)

Operación pop: transfiera n-1 elementos a otra cola y elimine los últimos de la cola para realizar operaciones pop.

  • Si la cola Q1 no está vacía, transfiera n-1 elementos de Q1 a Q2 y luego, DeQueue el último elemento de Q1 y devuélvalo.
  • Si la cola Q2 no está vacía, transfiera n-1 elementos de Q2 a Q1 y luego, DeQueue el último elemento de Q2 y devuélvalo.

`

 int Pop(struct Stack *S){ int i, size; if(IsEmptyQueue(S->Q2)) { size=size(S->Q1); i=0; while(iQ2, Dequeue(S->Q1)) ; i++; } return DeQueue(S->Q1); } else{ size=size(S->Q2); while(iQ1, Dequeue(S->Q2)) ; i++; } return DeQueue(S->Q2); } } 

Complejidad del tiempo: el tiempo de ejecución de la operación pop es O (n) ya que cada vez que se llama pop, estamos transfiriendo todos los elementos de una cola a otra.

 Q1 = [10, 15, 20, 25, 30] Q2 = [] exp: { dequeue n-1 element from Q1 and enqueue into Q2: Q2 == [10, 15, 20, 25] now Q1 dequeue gives "30" that inserted last and working as stack } swap Q1 and Q2 then GOTO exp 
 import java.util.LinkedList; import java.util.Queue; class MyStack { Queue queue1 = new LinkedList(); Queue queue2 = new LinkedList(); // Push element x onto stack. public void push(int x) { if(isEmpty()){ queue1.offer(x); }else{ if(queue1.size()>0){ queue2.offer(x); int size = queue1.size(); while(size>0){ queue2.offer(queue1.poll()); size--; } }else if(queue2.size()>0){ queue1.offer(x); int size = queue2.size(); while(size>0){ queue1.offer(queue2.poll()); size--; } } } } // Removes the element on top of the stack. public void pop() { if(queue1.size()>0){ queue1.poll(); }else if(queue2.size()>0){ queue2.poll(); } } // Get the top element. You can make it more perfect just example public int top() { if(queue1.size()>0){ return queue1.peek(); }else if(queue2.size()>0){ return queue2.peek(); } return 0; } // Return whether the stack is empty. public boolean isEmpty() { return queue1.isEmpty() && queue2.isEmpty(); } } 

Aquí hay una solución más:

para PUSH: -Añadir el primer elemento en la cola 1. -Cuando se agrega un segundo elemento y así sucesivamente, coloque en cola el elemento en la cola 2 y luego copie todo el elemento de la cola 1 a la cola2. -para POP solo dequeue el elemento de la cola desde que insertaste el último elemento.

Asi que,

 public void push(int data){ if (queue1.isEmpty()){ queue1.enqueue(data); } else { queue2.enqueue(data); while(!queue1.isEmpty()) Queue2.enqueue(queue1.dequeue()); //EXCHANGE THE NAMES OF QUEUE 1 and QUEUE2 

}}

 public int pop(){ int popItem=queue2.dequeue(); return popItem; }' 

Hay un problema, no puedo descifrar, ¿cómo cambiar el nombre de las colas?

 #include  using namespace std; queueQ; stackStk; void PRINT(stackss , queueqq) { while( ss.size() ) { cout << ss.top() << " " ; ss.pop(); } puts(""); while( qq.size() ) { cout << qq.front() << " " ; qq.pop(); } puts("\n----------------------------------"); } void POP() { queueTmp ; while( Q.size() > 1 ) { Tmp.push( Q.front() ); Q.pop(); } cout << Q.front() << " " << Stk.top() << endl; Q.pop() , Stk.pop() ; Q = Tmp ; } void PUSH(int x ) { Q.push(x); Stk.push(x); } int main() { while( true ) { string typ ; cin >> typ ; if( typ == "push" ) { int x ; cin >> x; PUSH(x); } else POP(); PRINT(Stk,Q); } } 

Código de Python usando solo una cola

  class Queue(object): def __init__(self): self.items=[] def enqueue(self,item): self.items.insert(0,item) def dequeue(self): if(not self.isEmpty()): return self.items.pop() def isEmpty(self): return self.items==[] def size(self): return len(self.items) class stack(object): def __init__(self): self.q1= Queue() def push(self, item): self.q1.enqueue(item) def pop(self): c=self.q1.size() while(c>1): self.q1.enqueue(self.q1.dequeue()) c-=1 return self.q1.dequeue() def size(self): return self.q1.size() def isempty(self): if self.size > 0: return True else: return False 

aquí está el código de trabajo completo en c #:

Se ha implementado con Single Queue,

empujar:

 1. add new element. 2. Remove elements from Queue (totalsize-1) times and add back to the Queue 

popular:

 normal remove using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace StackImplimentationUsingQueue { class Program { public class Node { public int data; public Node link; } public class Queue { public Node rear; public Node front; public int size = 0; public void EnQueue(int data) { Node n = new Node(); n.data = data; n.link = null; if (rear == null) front = rear = n; else { rear.link = n; rear = n; } size++; Display(); } public Node DeQueue() { Node temp = new Node(); if (front == null) Console.WriteLine("Empty"); else { temp = front; front = front.link; size--; } Display(); return temp; } public void Display() { if (size == 0) Console.WriteLine("Empty"); else { Console.Clear(); Node n = front; while (n != null) { Console.WriteLine(n.data); n = n.link; } } } } public class Stack { public Queue q; public int size = 0; public Node top; public Stack() { q = new Queue(); } public void Push(int data) { Node n = new Node(); n.data = data; q.EnQueue(data); size++; int counter = size; while (counter > 1) { q.EnQueue(q.DeQueue().data); counter--; } } public void Pop() { q.DeQueue(); size--; } } static void Main(string[] args) { Stack s= new Stack(); for (int i = 1; i <= 3; i++) s.Push(i); for (int i = 1; i < 3; i++) s.Pop(); Console.ReadKey(); } } } 

Aquí hay una solución muy simple que utiliza una cola y ofrece funcionalidades como Stack.

 public class CustomStack { Queue que = new Queue(); public void push(T t) // STACK = LIFO / QUEUE = FIFO { if( que.Count == 0) { que.Enqueue(t); } else { que.Enqueue(t); for (int i = 0; i < que.Count-1; i++) { var data = que.Dequeue(); que.Enqueue(data); } } } public void pop() { Console.WriteLine("\nStack Implementation:"); foreach (var item in que) { Console.Write("\n" + item.ToString() + "\t"); } var data = que.Dequeue(); Console.Write("\n Dequeing :" + data); } public void top() { Console.Write("\n Top :" + que.Peek()); } } 

Entonces, en la clase anterior llamada "CustomStack", lo que estoy haciendo es simplemente verificar que la cola esté vacía, si está vacía, luego insertar una y desde allí en wards insertar y luego quitar insertar. Por esta lógica, primero vendrá el último. Ejemplo: En la cola inserté 1 y ahora trato de insertar 2. Retire por segunda vez 1 y vuelva a insertar para que quede en orden inverso.

Gracias.

Aquí está mi solución …

Concept_Behind :: push(struct Stack* S,int data) :: Esta función pone en cola el primer elemento en Q1 y descansa en Q2 pop(struct Stack* S) :: si Q2 no está vacío transfiere todos los elem a Q1 y devuelve el último elem en Q2 else (lo que significa que Q2 está vacío) transfiere todos los elem a Q2 y devuelve los últimos elem en Q1

Efficiency_Behind :: push(struct Stack*S,int data) :: O (1) // desde single enqueue por pop(struct Stack* S) datos pop(struct Stack* S) :: O (n) // ya que transfiere los peores datos n-1 por pop .

 #include #include struct Queue{ int front; int rear; int *arr; int size; }; struct Stack { struct Queue *Q1; struct Queue *Q2; }; struct Queue* Qconstructor(int capacity) { struct Queue *Q=malloc(sizeof(struct Queue)); Q->front=Q->rear=-1; Q->size=capacity; Q->arr=malloc(Q->size*sizeof(int)); return Q; } int isEmptyQueue(struct Queue *Q) { return (Q->front==-1); } int isFullQueue(struct Queue *Q) { return ((Q->rear+1) % Q->size ==Q->front); } void enqueue(struct Queue *Q,int data) { if(isFullQueue(Q)) { printf("Queue overflow\n"); return;} Q->rear=Q->rear+1 % Q->size; Q->arr[Q->rear]=data; if(Q->front==-1) Q->front=Q->rear; } int dequeue(struct Queue *Q) { if(isEmptyQueue(Q)){ printf("Queue underflow\n"); return; } int data=Q->arr[Q->front]; if(Q->front==Q->rear) Q->front=-1; else Q->front=Q->front+1 % Q->size; return data; } ///////////////////////*************main algo****************//////////////////////// struct Stack* Sconstructor(int capacity) { struct Stack *S=malloc(sizeof(struct Stack)); S->Q1=Qconstructor(capacity); S->Q2=Qconstructor(capacity); return S; } void push(struct Stack *S,int data) { if(isEmptyQueue(S->Q1)) enqueue(S->Q1,data); else enqueue(S->Q2,data); } int pop(struct Stack *S) { int i,tmp; if(!isEmptyQueue(S->Q2)){ for(i=S->Q2->front;i<=S->Q2->rear;i++){ tmp=dequeue(S->Q2); if(isEmptyQueue(S->Q2)) return tmp; else enqueue(S->Q1,tmp); } } else{ for(i=S->Q1->front;i<=S->Q1->rear;i++){ tmp=dequeue(S->Q1); if(isEmptyQueue(S->Q1)) return tmp; else enqueue(S->Q2,tmp); } } } ////////////////*************end of main algo my algo************ ///////////////*************push() O(1);;;;pop() O(n);;;;*******///// main() { int size; printf("Enter the number of elements in the Stack(made of 2 queue's)::\n"); scanf("%d",&size); struct Stack *S=Sconstructor(size); push(S,1); push(S,2); push(S,3); push(S,4); printf("%d\n",pop(S)); push(S,5); printf("%d\n",pop(S)); printf("%d\n",pop(S)); printf("%d\n",pop(S)); printf("%d\n",pop(S)); } 
 import java.util.LinkedList; import java.util.Queue; public class StackQueue { static Queue Q1 = new LinkedList(); static Queue Q2 = new LinkedList(); public static void main(String args[]) { push(24); push(34); push(4); push(10); push(1); push(43); push(21); System.out.println("Popped element is "+pop()); System.out.println("Popped element is "+pop()); System.out.println("Popped element is "+pop()); } public static void push(int data) { Q1.add(data); } public static int pop() { if(Q1.isEmpty()) { System.out.println("Cannot pop elements , Stack is Empty !!"); return -1; } else { while(Q1.size() > 1) { Q2.add(Q1.remove()); } int element = Q1.remove(); Queue temp = new LinkedList(); temp = Q1; Q1 = Q2; Q2 = temp; return element; } } } 
 #include "stdio.h" #include "stdlib.h" typedef struct { int *q; int size; int front; int rear; } Queue; typedef struct { Queue *q1; Queue *q2; } Stack; int queueIsEmpty(Queue *q) { if (q->front == -1 && q->rear == -1) { printf("\nQUEUE is EMPTY\n"); return 1; } return 0; } int queueIsFull(Queue *q) { if (q->rear == q->size-1) { return 1; } return 0; } int queueTop(Queue *q) { if (queueIsEmpty(q)) { return -1; } return q->q[q->front]; } int queuePop(Queue *q) { if (queueIsEmpty(q)) { return -1; } int item = q->q[q->front]; if (q->front == q->rear) { q->front = q->rear = -1; } else { q->front++; } return item; } void queuePush(Queue *q, int val) { if (queueIsFull(q)) { printf("\nQUEUE is FULL\n"); return; } if (queueIsEmpty(q)) { q->front++; q->rear++; } else { q->rear++; } q->q[q->rear] = val; } Queue *queueCreate(int maxSize) { Queue *q = (Queue*)malloc(sizeof(Queue)); q->front = q->rear = -1; q->size = maxSize; q->q = (int*)malloc(sizeof(int)*maxSize); return q; } /* Create a stack */ void stackCreate(Stack *stack, int maxSize) { Stack **s = (Stack**) stack; *s = (Stack*)malloc(sizeof(Stack)); (*s)->q1 = queueCreate(maxSize); (*s)->q2 = queueCreate(maxSize); } /* Push element x onto stack */ void stackPush(Stack *stack, int element) { Stack **s = (Stack**) stack; queuePush((*s)->q2, element); while (!queueIsEmpty((*s)->q1)) { int item = queuePop((*s)->q1); queuePush((*s)->q2, item); } Queue *tmp = (*s)->q1; (*s)->q1 = (*s)->q2; (*s)->q2 = tmp; } /* Removes the element on top of the stack */ void stackPop(Stack *stack) { Stack **s = (Stack**) stack; queuePop((*s)->q1); } /* Get the top element */ int stackTop(Stack *stack) { Stack **s = (Stack**) stack; if (!queueIsEmpty((*s)->q1)) { return queueTop((*s)->q1); } return -1; } /* Return whether the stack is empty */ bool stackEmpty(Stack *stack) { Stack **s = (Stack**) stack; if (queueIsEmpty((*s)->q1)) { return true; } return false; } /* Destroy the stack */ void stackDestroy(Stack *stack) { Stack **s = (Stack**) stack; free((*s)->q1); free((*s)->q2); free((*s)); } int main() { Stack *s = NULL; stackCreate((Stack*)&s, 10); stackPush((Stack*)&s, 44); //stackPop((Stack*)&s); printf("\n%d", stackTop((Stack*)&s)); stackDestroy((Stack*)&s); return 0; }