剑指offer三道栈相关题目
1栈的压入顺序判断输出顺序是否正确
package offer;
import java.util.Stack;
public class Test19 {
public static boolean pushed(int[] pushed, int[] poped) {
Stack stack = new Stack<>();
//左右两个指针
int i = 0, j = 0;
while (i < pushed.length && j < poped.length) {
if (!stack.isEmpty() && stack.peek() == poped[j]) {
stack.pop();
j++;
} else {
stack.push(pushed[i]);
i++;
}
}
//剩下的元素一一匹配
//stack里面弹出的数值跟poped数值一一相等
while (!stack.isEmpty()) {
if (stack.peek() == poped[j]) {
j++;
stack.pop();
} else
//有一次不可以就返回false
return false;
}
return true;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int[] poped = {4, 5, 1, 2, 3};
System.out.println(pushed(arr, poped));
}
}
2两个栈实现队列
package offer;
import java.util.Stack;
class Solution {
Stack stack1 = new Stack<>();
Stack stack2 = new Stack<>();
//实现先入 先出 stack1存 stack2出
public void push(int n) {
stack1.push(n);
}
//实现先进先出
public int pop() {
//stack1 123
//stack1不为空的情况 数值全部进入了stack1
//2为空的情况菜往里面放
if (stack2.empty()) {
while (!stack1.isEmpty()) {
//stack2 321
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
public class Test17 {
public static void main(String[] args) {
Solution s = new Solution();
s.push(1);
s.push(2);
s.push(3);
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.pop());
}
}
3最小min函数
package offer;
import java.util.Stack;
class MinStack {
Stack stack;
Stack stackMin;
//构建函数
MinStack() {
stack = new Stack<>();
stackMin = new Stack<>();
}
public void push(int x) {
stack.push(x);
//当前新输入的数值小于最小栈的栈顶最小值
//stackMin 值为空的时候也要放进去
if (x < stackMin.peek() || stackMin.isEmpty())
stackMin.push(x);
}
void pop() {
stack.pop();
//如果输出的值正好是栈顶最小值 那么最小栈也输出
if (stack.pop().equals(stackMin.peek()))
stackMin.pop();
}
int min() {
//最小值就是栈顶的元素
return stackMin.peek();
}
}
public class Test18 {
}
三道题都用到了构建新的栈来辅助操作
目前状态:知道流程不会写代码,意味着不是真正的懂,不知道今天的努力能获得什么,但是不努力,明天什么都没有。



