基础知识
使用ArrayDeque 实现栈和队列
stack push pop peek isEmpty() size()
queue offer poll peek isEmpty() size()
LeetCode 232.用栈实现队列
分析1.0
队列先进先出，栈先进后出，每次获得栈中的最后一个元素，需要借助两个栈，操作完成之后再将元素push回去。
设一个栈为stack，存放元素，另一个栈为tool，用于实现元素转置，就是来回倒腾
class MyQueue {
ArrayDeque stack, tool;
public MyQueue() {
this.stack = new ArrayDeque();
this.tool = new ArrayDeque();
}
public void push(int x) {
stack.push(x);
}
public int pop() {
int ans = -1;
while(!stack.isEmpty()){
tool.push(stack.pop());
}
if(!tool.isEmpty()){
ans = (int)tool.pop();
}
while(!tool.isEmpty()){
stack.push(tool.pop());
}
return ans;
}
public int peek() {
int ans = -1;
while(!stack.isEmpty()){
tool.push(stack.pop());
}
if(!tool.isEmpty()){
ans = (int)tool.peek();
}
while(!tool.isEmpty()){
stack.push(tool.pop());
}
return ans;
}
public boolean empty() {
return stack.isEmpty();
}
}失误
Stack提前定义一下泛型
LeetCode 225. 用队列实现栈
分析1.0
队列，先进先出，队列分为队尾队头，要实现栈操作，pop时pop队尾，push时直接push就好，到的是队尾
要用一个队列实现栈，pop队头后再push进队尾，留下来最后一个元素即可，如何定位第一个或最后一个元素
class MyStack {
ArrayDeque<Integer> list;
public MyStack() {
this.list = new ArrayDeque();
}
public void push(int x) {
list.offer(x);
}
public int pop() {
int flag = list.peek();
int temp = 0;
while(true){
temp = list.poll();
if(list.isEmpty() || list.peek() == flag){
break;
}
list.offer(temp);
}
return temp;
}
public int top() {
int flag = list.peek();
int temp = 0;
while(true){
temp = list.poll();
list.offer(temp);
if(list.peek() == flag){
break;
}
}
return temp;
}
public boolean empty() {
return list.isEmpty();
}
}总结
- 循环代码块中实现元素定位
常用变量名增量更新
size、val、ans、cnt、cur、pre、next、left、right、index、gap、tar、res、src、len、start、end、flag
