首页 > 代码库 > Lintcode: Implement Queue by Stacks 解题报告
Lintcode: Implement Queue by Stacks 解题报告
Implement Queue by Stacks
原题链接 ： http://lintcode.com/zh-cn/problem/implement-queue-by-stacks/#
As the title described, you should only use two stacks to implement a queue‘s actions.
The queue should support push(element), pop() and top() where pop is pop the first(a.k.a front) element in the queue.
Both pop and top methods should return the value of first element.
样例
For push(1), pop(), push(2), push(3), top(), pop(), you should return 1, 2 and 2
挑战
View Code
implement it by two stacks, do not use any other data structure and push, pop and top should be O(1) by AVERAGE.
SOLUTION 1:
使用两个栈，stack1和stack2。
http://www.ninechapter.com/problem/49/
对于Queue的操作对应如下：
Queue.Push:
push到Stack1
Queue.Pop:
如果Stack2非空，Stack2.pop
否则将Stack1中的所有数pop到Stack2中（相当于顺序颠倒了放入），然后Stack2.pop()
每个数进出Stack1和Stack2各1次，所以两个操作的均摊复杂度均为O(1)
1 public class Solution { 2 private Stack<Integer> stack1; 3 private Stack<Integer> stack2; 4 5 public Solution() { 6 // do initialization if necessary 7 stack1 = new Stack<Integer>(); 8 stack2 = new Stack<Integer>(); 9 }10 11 public void push(int element) {12 // write your code here13 stack1.push(element);14 }15 16 public int pop() {17 // write your code here18 if (stack2.isEmpty()) {19 while (!stack1.isEmpty()) {20 stack2.push(stack1.pop());21 }22 }23 24 return stack2.pop();25 }26 27 public int top() {28 // write your code here29 // write your code here30 if (stack2.isEmpty()) {31 while (!stack1.isEmpty()) {32 stack2.push(stack1.pop());33 }34 }35 36 return stack2.peek();37 }38 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/lintcode/stack/StackQueue.java
Lintcode: Implement Queue by Stacks 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。