栈与队的相互转换

import java.util.LinkedList;
import java.util.Stack;

/**
* 1、利用两个栈实现一个队列 思路：插入的时候直接插入第一个栈 移除的时候,如果第二个栈为空,则把第一个站所有元素放入第二个站 从第二个站移除一个元素即可
* 2、两个队列实现一个栈 思路：插入的时候,如果两个队列都为空则插入任意一个队列,否则插入非空的那个队列
* 　　　移除的时候,把非空队列的元素全部弄到空队列里,把最后一个元素返回
* 3、利用一个队列实现一个栈 思路：利用递归的方式把队列反转,返回第一个
* 4、利用一个栈实现一个队列 思路: 利用递归的方式把数据都推出来，返回最后一个
* 5、实现栈取和进最小数都是O(1)
* 　　　思路：在插入数据的时候同时把当前最小的数也插入到栈中,从而在取的时候就娶到最小数, 同时在取的时候把该数和最小数都一起弹出
*
* @author wangjianfu
*
*/
public class TestStack1 {
public static void main(String[] args) {
MiniStack q = new MiniStack(20);
q.push(15);
q.push(10);
q.push(5);
q.push(25);
q.push(20);
q.push(15);
q.push(10);
q.push(5);
q.push(25);
q.push(20);
q.push(15);
q.push(10);
q.push(5);
q.push(25);
q.push(20);
q.push(15);
q.push(10);
q.push(5);
q.push(25);
q.push(20);

System.out.println("当前最小值:" + q.getMinNumber());

System.out.println("拿出值：" + q.pop());

System.out.println("当前最小值:" + q.getMinNumber());

System.out.println("拿出值：" + q.pop());

System.out.println("当前最小值:" + q.getMinNumber());

System.out.println("拿出值：" + q.pop());

System.out.println("当前最小值:" + q.getMinNumber());

System.out.println("拿出值：" + q.pop());
}
}

class MiniStack {
private Integer minnumber = 10000;
private int top = -1;
private Integer[] numbers;
private int length = 0;
private int maxlen;

public MiniStack(int length) {
numbers = new Integer[length];
maxlen = length/2;
}

// 插入数据
public void push(int n) {
if (length + 2 > maxlen - 1) {
System.out.println("栈 已经满了");
return;
}
minnumber = n > minnumber ? minnumber : n;
top++;
numbers[top] = n;
top++;
length++;
numbers[top] = minnumber;
}

public Integer pop() {
if (length == 0) {
System.out.println("栈为空");
return null;
}
top--;// 跳过最小的数
int result = numbers[top];
top--;
length--;
return result;
}

public Integer getMinNumber() {
if (length == 0) {
System.out.println("栈为空");
return null;
}
return numbers[top];
}

}

class Queue {
private Stack<Integer> s1 = new Stack<Integer>();
private Stack<Integer> s2 = new Stack<Integer>();

public void insert(Integer temp) {
s1.push(temp);
}

public Integer remove() {
if (s2.size() == 0) {
// 把s1元素全部弹出放入s2
while (s1.size() > 0) {
s2.push(s1.pop());
}
}
// 从s2中直接弹出一个元素
return s2.pop();
}
}

class Queue2 {
private Stack<Integer> s1 = new Stack<Integer>();

public void insert(Integer temp) {
s1.push(temp);
}

public Integer remove() {
if (s1.size() == 0) {
return null;
}
if (s1.size() == 1) {
return s1.pop();
}
int temp = s1.pop();
int result = remove();
s1.push(temp);
return result;

}
}

class Stackk {
private java.util.LinkedList<Integer> q1 = new LinkedList<Integer>();
private java.util.LinkedList<Integer> q2 = new LinkedList<Integer>();

public void insert(Integer temp) {
if (q1.size() == 0 && q2.size() == 0) {
q1.add(temp);
} else if (q1.size() > 0) {
q1.add(temp);
} else {
q2.add(temp);
}
}

public Integer remove() {
if (q1.size() > 0) {
while (q1.size() > 0) {
q2.add(q1.poll());
}
return q2.poll();
} else if (q2.size() > 0) {
while (q2.size() > 0) {
q1.add(q2.poll());
}
return q1.poll();
} else {
return null;
}
}
}

class Stackk2 {
private java.util.LinkedList<Integer> q2 = new LinkedList<Integer>();

public void insert(Integer temp) {
q2.add(temp);
}

public Integer remove() {
if (q2.size() == 0) {
return null;
}
reverse();
int result = q2.poll();
reverse();
return result;
}

public void reverse() {
if (q2.size() == 0) {
return;
}
int temp = q2.poll();
reverse();
q2.add(temp);
}

}