Implemente las siguientes operaciones de una pila usando colas.
push (x): empuja el elemento x hacia la pila.
pop (): elimina el elemento en la parte superior de la pila.
top (): obtiene el elemento superior.
empty (): devuelve si la pila está vacía.
Nota: solo se permiten operaciones de cola estándar, es decir, poll (), oferta (), peek (), size () e isEmpty () en Java.
Análisis
Este problema se puede resolver utilizando dos colas.
Solución Java
class MyStack { LinkedList<Integer> queue1 = new LinkedList<Integer>(); LinkedList<Integer> queue2 = new LinkedList<Integer>(); // Push element x onto stack. public void push(int x) { if(empty()){ 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. 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 empty() { return queue1.isEmpty() & queue2.isEmpty(); } } |