目录
一、栈转队列
定义两个栈，一个栈(s1)存放要放入的元素，然后将存放的元素放入另一个栈(s2)中，因为栈是先进后出，所以两个栈的排列顺序相反，队列是先进的先出，所以s2元素的出栈顺序和栈顶元素和队列相同，所以对s2进行操作就可以实现一个队列。
1、定义队列
用两个栈来实现队列
public class MyQueue {
private Stack<Integer> s1;
private Stack<Integer> s2;
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}2、放入元素
先将元素放入s1中
public void push(int x){
s1.push(x);
}3、判断队列是否为空
队列是否为空就是判断两个栈是否为空
public boolean empty(){
return s1.empty()&&s2.empty();
}4、队列的第一个元素
队列是先进先出，栈是先进后出，将s1的元素从栈顶依次放入s2中，s2的排列顺序和队列相同，队列的第一个元素就是s2的栈顶元素，将栈顶元素取出。
public int pop(){
if (empty()){
return -1;
}if (s2.empty()){
while (!s1.empty()){
s2.push(s1.pop());
}
}
return s2.pop();
}5、队列第一个元素的值
队列第一个元素的值，就是s2的栈顶元素的值，不需要将栈顶元素从栈中取出。
public int peek(){
if (empty()){
return -1;
}if (s2.empty()){
while (!s1.empty()){
s2.push(s1.pop());
}
}
return s2.peek();
}
}6、方法使用
定义一个Main类，对定义的方法进行使用。
public class Test {
public static void main(String[] args) {
MyQueue myQueue=new MyQueue();
myQueue.push(1);
myQueue.push(2);
myQueue.push(3);
myQueue.push(4);
myQueue.push(5);
myQueue.push(6);
System.out.println(myQueue.empty());
System.out.println(myQueue.pop());
System.out.println(myQueue.peek());
}
}
执行结果：
false
1
2
二、队列转栈
定义两个队列(qu1 qu2)来实现栈，先将值先放入qu1中，之后哪个栈不为空放入哪个栈中。因为栈是先进后出，队列是先进先出，所以同样的元素放入栈和队列中，栈的栈顶元素就是队列的最后一个元素。将最后一个元素在前的元素放入另一个队列中，最后一个元素就来到了队列的第一个元素，可以直接取出，就取出了栈的栈顶元素。
1、定义栈
用两个队列来实现栈
public class MyStack {
private Queue<Integer>queue1;
private Queue<Integer>queue2;
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
2、判断栈是否为空
判断栈是否为空就是判断两个队列是否为空
public boolean empty(){
return queue1.isEmpty() && queue2.isEmpty();
}3、放入元素
在取栈顶元素时，两个队列中的元素要相互放入，所以哪个队列不为空，放入哪个队列中，当两个队列都为空，放入第一个队列中。
public void push(int x){
if (!queue1.isEmpty()){
queue1.offer(x);
}else if (!queue2.isEmpty()){
queue2.offer(x);
}
queue1.offer(x);
}4、栈顶元素
栈和队列的放入顺序相反，队列的最后一个元素就是栈顶元素
public int pop(){
if (empty()){
return -1;
}else if (!queue1.isEmpty()){
int size=queue1.size();
for (int i = 0; i < size-1; i++) {
int a= queue1.poll();
queue2.offer(a);
}
return queue1.poll();
}else {
int size=queue2.size();
for (int i = 0; i < size-1; i++) {
int a=queue2.poll();
queue1.offer(a);
}
return queue2.poll();
}
}5、栈顶元素的值
将队列中的元素都放入另一个队列中，用x来记录最后一个元素的值，就是栈顶元素的值。
public int peek(){
if (empty()){
return -1;
}else if (!queue1.isEmpty()){
int size=queue1.size();
int x=-1;
for (int i = 0; i < size; i++) {
x= queue1.poll();
queue2.offer(x);
}
return x;
}else {
int size=queue2.size();
int x=-1;
for (int i = 0; i < size-1; i++) {
x=queue2.poll();
queue1.offer(x);
}
return x;
}
}
}6、方法使用
定义一个Main类来对定义的方法进行实现
public class Main {
public static void main(String[] args) {
MyStack myStack=new MyStack();
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.push(5);
myStack.push(6);
System.out.println(myStack.empty());
System.out.println(myStack.pop());
System.out.println(myStack.peek());
}
}执行结果：
false
6
5
