admin管理员组

文章数量:1636931

题目链接：https://leetcode/problems/implement-stack-using-queues/
题目：

Implement the following operations of a stack using queues.

  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • empty() -- Return whether the stack is empty.
Notes:
  • You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
  • Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
  • You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
思路： 用两个队列模拟一个栈。每当push、pop的时候都要更新两个队列。 算法： [java]  view plain  copy  
  1. class MyStack {  
  2.     Queue<Integer> q1 = new LinkedList<Integer>();  
  3.     Queue<Integer> q2 = new LinkedList<Integer>();  
  4.       
  5.     // Push element x onto stack.  
  6.     public void push(int x) {  
  7.         Queue<Integer> tmp = new LinkedList<Integer>();  
  8.         q1.offer(x);  
  9.         //更新q2队列，将x放到q2正确的位置  
  10.         while(!q2.isEmpty()){  
  11.             tmp.offer(q2.poll());  
  12.         }  
  13.         q2.offer(x);  
  14.         while(!tmp.isEmpty()){  
  15.             q2.offer(tmp.poll());  
  16.         }  
  17.     }  
  18.   
  19.     // Removes the element on top of the stack.  
  20.     public void pop() {  
  21.         Queue<Integer> tmp = new LinkedList<Integer>();  
  22.         q2.poll();  
  23.         int i = 0;  
  24.         while(!q1.isEmpty()){  
  25.             i = q1.poll();  
  26.             if(!q1.isEmpty()){ //q1倒数第一个元素不要了  
  27.                 tmp.offer(i);  
  28.             }  
  29.         }  
  30.         while(!tmp.isEmpty()){  
  31.             q1.offer(tmp.poll());  
  32.         }  
  33.     }  
  34.   
  35.     // Get the top element.  
  36.     public int top() {  
  37.         return q2.peek();  
  38.     }  
  39.   
  40.     // Return whether the stack is empty.  
  41.     public boolean empty() {  
  42.         return q1.isEmpty();  
  43.     }  
  44. }  

本文标签： implementLeetCodequeuesStack

版权声明：本文标题：【Leetcode】Implement Stack using Queues 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dongtai/1729234784a1191867.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。