queue,stack的相互实现

时间:2024-12-16 21:35:51

Implement Queue using Stacks

[抄题]:

[思维问题]:

[一句话思路]:

取头部、取出来的时候,用一个output来倒序

[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):

[画图]:

queue,stack的相互实现

[一刷]:

  1. this.queue = new LinkedList<Integer>(); queue的本质是链表,右边要写成linkedlist

[总结]:

[复杂度]:Time complexity: O() Space complexity: O()

[英文数据结构,为什么不用别的数据结构]:

[其他解法]:

[Follow Up]:

[题目变变变]:

class MyQueue {
Stack<Integer> input = new Stack();
Stack<Integer> output = new Stack(); public MyQueue() {
this.input = new Stack<Integer>();
this.output = new Stack<Integer>();
} /** Push element x to the back of queue. */
public void push(int x) {
input.push(x);
} /** Removes the element from in front of queue and returns that element. */
public int pop() {
peek();
return output.pop();
} /** Get the front element. */
public int peek() {
if (output.empty()) {
while (!input.empty()) {
output.push(input.pop());
}
}
return output.peek();
} /** Returns whether the queue is empty. */
public boolean empty() {
if(output.empty() && input.empty()) {
return true;
}
return false;
}
}

Implement Stack using Queues

[抄题]:

[思维问题]:

[一句话思路]:

[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):

[画图]:

[一刷]:

  1. this.queue = new LinkedList<Integer>(); 右边是LinkedList
  2. Queue的push要先把新元素加进去。不然怎么去挤谁呢……
  3. queue的操作语言是poll, add。stack是push/pop
  4. 判断空都写isempty

[二刷]:

  1. 取top时要用peek方法,直接用poll取出来的不一定是最大的
  2. 一开始只需要初始化数据结构,不需要新建对象:Queue<Integer> queue;

[总结]:

[复杂度]:Time complexity: O() Space complexity: O()

[英文数据结构,为什么不用别的数据结构]:

[其他解法]:

[Follow Up]:

[题目变变变]:

class MyStack {
Queue<Integer> queue;
/** Initialize your data structure here. */
public MyStack() {
this.queue = new LinkedList<Integer>();
} /** Push element x onto stack. */
public void push(int x) {
queue.add(x);
for (int i = 0; i < queue.size() - 1; i++) {
queue.add(queue.poll());
}
} /** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.poll();
} /** Get the top element. */
public int top() {
return queue.peek();
} /** Returns whether the stack is empty. */
public boolean empty() {
if (queue.isEmpty()) {
return true;
}
return false;
}
}