1、实现一个栈，实现push和pop操作，并在O(1)的时间复杂度内获取当前栈中的min值。
基本思路：
设计一个类StackWithMin，里面有两个栈结构data和min，data 就是存取原本数据的，而min存取当前data中最小的那个数据，data和min栈中的数据个数要始终保持一致（也就是说min中的最小数据会重复）。
import java.util.Stack;
public class StackWithMin{
private Stack<Integer> data;
private Stack<Integer> min;
public StackWithMin(){
data = new Stack();
min = new Stack();
}
public boolean isEmpty(){
return data.isEmpty() && min.isEmpty();
}
public void push(int val){
data.push(val);
if (min.size() == 0 || val < min.peek()){
min.push(val);
}else {
min.push(min.peek());
}
}
public int pop(){
min.pop();
return data.pop();
}
public int getMin(){
return min.peek();
}
public int size(){
return data.size();
}
}
2、两个栈实现一个队列
基本思路：
设计一个类 QueueWithTwoStacks，该类中有两个成员变量in,out，类型是java.util.Stack，入队操作的时候将数据保存在in中，出队操作的时候调用out.pop()方法，如果out为空的话就将in中的数据出栈，并依次push到out中。
栈是一种后进先出的结构，队列是一种先进先出的结构，两个栈“负负为正”就刚好实现一个队列，实现起来还是蛮简单的。
import java.util.Stack;
public class QueueWithTwoStacks {
private Stack<Integer> in;
private Stack<Integer> out;
public QueueWithTwoStacks(){
in = new Stack<Integer>();
out = new Stack<Integer>();
}
public boolean isEmpty(){
return in.isEmpty() && out.isEmpty();
}
public void enqueue(int val){
in.push(val);
}
public int dequeue(){
if (out.isEmpty()){
while (!in.isEmpty())
out.push(in.pop());
}
return out.pop();
}
public int size(){
return in.size() + out.size();
}
}
3、两个队列实现一个栈
基本思路：
设计一个类 StackWithTwoQueues，该类中包含两个队列 queue，queue2，类型是 LinkedList<Integer>（单链表可表示队列)，入栈时哪个队列不是空的，就将数据offer到该队列中，出栈要将当前非空队列假如是queue1的前n-1个数据出队，并依次将这些数据offer到另外一个空队列queue2中，最后将queue1的最后一个数据出队并返回即可。
出栈时谨记保留非空队列中的最后一个数据，将前n-1个数据依次保存到另外一个空队列中，当非空队列中最后一个数据弹出后，原来的非空队列变为空队列，原来的空队列变为非空队列，以后对调操作，如此反复，即可实现栈的出栈操作。
import java.util.LinkedList;
public class StackWithTwoQueues{
private LinkedList<Integer> queue1;
private LinkedList<Integer> queue2;
public StackWithTwoQueues(){
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
public boolean isEmpty(){
return queue1.isEmpty() && queue2.isEmpty();
}
public void push(int val){
if (queue2.isEmpty())
queue1.offer(val);
else if (queue1.isEmpty())
queue2.offer(val);
}
public int pop(){
int ret = -1;
if (queue2.isEmpty()){
while (queue1.size() > 1){
queue2.offer(queue1.poll());
}
ret = queue1.poll();
}
else if (queue1.isEmpty()){
while (queue2.size() > 1){
queue1.offer(queue2.poll());
}
ret = queue2.poll();
}
return ret;
}
public int size(){
return queue1.size() + queue2.size();
}
}
4、给定入栈序列，判断所给出的出栈序列是否合法
如 入栈： 1，2，3，4，5
出栈：4，5，3，2，1 合法
出栈：3，1，2，4，5 不合法
出栈：4，5，3，2 不合法
基本思路：
首先，要确保入栈序列的长度和出栈序列的长度相等。
其次，将入栈序列的每一个元素入栈，入栈后看栈顶的元素是否和出栈序列的当前位置中的值相等，如果相等，那么就出栈，并将出栈序列的索引位置+1
最后，循环完成之后，返回栈的大小是否为0，即 return stack.size() == 0;
import java.util.Stack;
public static boolean isPopSequenceLegal(int[] in,int[] out){
if (in == null || out == null || in.length != out.length)
return false;
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0, j = 0; i < in.length; i ++){
stack.push(in[i]);
while (j < out.length && stack.size() > 0 && stack.peek() == out[j]){
++j;
stack.pop();
}
}
return stack.size();
}
5、用一个数据实现两个栈
基本思路：
将数组从中间分为左右两部分，左边的部分入栈时++,右边的部分入栈时--即可，当中间碰头后扩容即可，代码实现的时候注意一点：
就是push和pop要传入两个参数，一个参数Tag,代表的是哪个栈，另外一个参数是具体的数值，比较简单，这里就不写代码了！
网友评论