包含min函数的栈
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
import java.util.Stack;
public class Solution {
Stack<Integer> num=new Stack<>();//无论如何肯定要保存原始数据
Stack<Integer> min=new Stack<>();//随时都能返回min，涉及到状态的变化，用一个栈存，用一个min值对应多个num值，更新则添加，失效则删除
public void push(int node) {
num.push(node);
if(min.isEmpty()||node<min.peek())//如果min栈为空，或者比当前min小，那么node就是当前最小值
min.push(node);
}
public void pop() {
if(num.pop()==min.peek())//如果删除数就是当前最小值，那么剩下的数失去了这个最小值
min.pop();
}
public int top() {
return num.peek();
}
public int min() {
return min.peek();
}
}
这个题也可以采用一个min值对应一个num值的做法
public void push(int node) {
num.push(node);
if(min.isEmpty()||node<min.peek())
min.push(node);//更新则添加
else
min.push(min.peek());//未更新则累加
}
public void pop() {
num.pop();
min.pop();//一一对应，都删除
}
用两个栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
import java.util.Stack;
public class Solution {
//栈发生变化的地方只有一处，而队列有两处，所以用两个栈来模拟
Stack<Integer> stack1 = new Stack<Integer>();//模拟队列的尾
Stack<Integer> stack2 = new Stack<Integer>();模拟队列的头
public void push(int node) {
stack1.push(node);//队列和栈一样都是在尾部添加
}
public int pop() {
if(stack2.isEmpty())
{
while(!stack1.isEmpty())//但是删除的顺序是相反的，所以每次删除时，都要把栈中的数颠倒
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
栈的压入、弹出序列
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
首先是自我感觉良好的弱智算法
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
int n=pushA.length;
int[] rec=new int[n+1];
for(int i=0;i<n;i++)
rec[pushA[i]]=i+1;
for(int i=0;i<n;i++) {
if(popA[i]>n||popA[i]<1) return false;
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
//当i出栈，i前面的数字已经入过栈，如果还没有出栈，他们的顺序都应该跟入栈顺序相反
//如果有两个在i之后出栈的数j,k，即是i前面的数字且在i出栈时还没有出栈，出栈顺序却和入栈顺序相同，
//那么就是不可能的弹出序列
if (rec[popA[j]] < rec[popA[k]] && rec[popA[j]] < rec[popA[i]])
return false;
}
return true;
}
}
实际上直接模拟就完事了
import java.util.*;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> s=new Stack<>();
int pos=0;//popA的坐标
int len=popA.length;
for(int num:pushA){
s.push(num);
//pos越界时，s为空，所以不用判断pos
while(!s.isEmpty()&&s.peek()==popA[pos])
{
s.pop();
pos++;
}
}
return s.isEmpty();
}
}
