栈和队列的转换

一、栈转队列

1、定义队列

2、放入元素

3、判断队列是否为空

4、队列的第一个元素

5、队列第一个元素的值

6、方法使用

二、队列转栈

1、定义栈

2、判断栈是否为空

3、放入元素

4、栈顶元素

5、栈顶元素的值

6、方法使用

一、栈转队列

定义两个栈，一个栈(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