如何用栈来模拟队列，如何用队列模拟栈？？_简述用栈模拟队列的行为

 
 
  首先要明白栈和队列两者之间的不同
栈是一种先进后出的数据结构
队列是一种先进先出的数据结构
  分析完两者的结构特点之后再进行模拟
 

一.用栈模拟实现队列

  
  用栈模拟队列，就要完成队列的一些基本操作：
offer(x) – 将一个元素放入队列的尾部。
poll() – 从队列首部移除元素。
peek() – 返回队列首部的元素,但不删除。
isEmpty() – 返回队列是否为空。

  栈和队列特性是完全不一样的，所以用一个栈来模拟显然是不行的，所以考虑用两个栈来模拟实现

  1.offer(x)操作：入队操作很简单，就直接让元素入到s1栈中即可
  2.poll()操作： 出队列是从队头出，所以对应元素应该是s1栈最底部的元素出，而对于栈是拿不到栈底元素的，此时可以让s1中的所有元素依次出栈再压入s2中，那么s2的栈顶其实就是队头元素了，其实就是s1模拟入队列，s2模拟出队列。
  注意：s1用来入队列，s2用来模拟出队列，但每次出队列时要先判断s2是否为空，当s2为空时，就要先将s1中的元素导到s2中再出队列
  3.peek()操作：查看队头元素，前面的基本操作和poll一样，就是现在不是出队列了，而是查看队头元素（也就是查看s2此时栈顶元素）
  4.isEmpty()操作：若s1和s2都为空，队列肯定就是空的
 
 
 
参考代码：

class MyQueue<E>{
    private Stack<E> s1;
    private Stack<E> s2;

    public MyQueue(){
        s1=new Stack<>();
        s2=new Stack<>();
    }

    //入队列，相当于入栈s1
    public void offer(E e){
        s1.push(e);
    }

    //出队列,相当于出栈s2
    public E poll(){
        if(s2.empty()){
        //s2为空时，将s1中元素都入栈到s2
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    

    //获取队头元素
    public E peek(){
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }

    //判断队列是否为空
    public boolean isEmpty(){
        return s1.empty() && s2.empty();
    }

}


public class Test{
    public static void main(String[] args) {
        MyQueue<String> my=new MyQueue<>();
        my.offer("qwer");
        my.offer("asdf");
        my.offer("zxcv");
        System.out.println(my.poll());
        System.out.println(my.peek());
        my.poll();
        my.poll();
        System.out.println(my.isEmpty());
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

运行结果：
  上述代码只是简单的实现了一个队列，出栈和查看栈顶元素默认栈中有元素。
 
 
 
 

二.用队列模拟实现栈

 
 用队列模拟栈，就要完成栈的一些基本操作：
push(x) – 元素 x 入栈
pop() – 移除栈顶元素
peek() – 获取栈顶元素
empty() – 返回栈是否为空
 
  还是用两个队列来模拟实现栈

 
  1.push(x)操作：入栈操作，就将x元素入到q1即可
  2.pop()操作： 模拟出栈，要出的就是最后一个入到q1中的元素，而q1是队列，要想让队尾元素出来，就需要先将它之前的元素出队列。那么就让q1队尾之前的所有元素先出q1队列再入队列到q2保存，之后q1再出队列得到的元素就是队尾元素了，也就模拟了栈顶元素出栈。
  注意：这里要用到循环，所以为了统一操作，出完队列之后还要将q1和q2换位置
  3.peek()操作：查看栈顶元素，前面的基本操作和pop一样，就是现在不是出栈了，而是查看栈顶元素（也就是查看q1此时的队头元素），查看完后去q1最后一个元素也要入到q2中，然后再将q1和q2互换
  4.empty()操作：若q1为空，栈肯定就是空的

 
 

参考代码：

import java.util.*;

class MyStack<E>{
    private Queue<E> q1;
    private Queue<E> q2;

    public MyStack(){
        q1=new LinkedList<>();
        q2=new LinkedList<>();
    }


    //1.入栈操作，就是入q1队列
    public void push(E e){
        q1.offer(e);
    }


    //2.出栈操作（出队列）
    public E pop(){
        while(q1.size()>1){
            q2.offer(q1.poll());
        }
        E ret=q1.poll();
        //交换q1和q2的位置
        Queue<E> tmp=q1;
        q1=q2;
        q2=tmp;
        return ret;
    }


    //3.查看栈顶元素
    public E peek(){
        while(q1.size()>1){
            q2.offer(q1.poll());
        }
        E ret=q1.peek();
        //将q1最后一个元素入队列到q2
        q2.offer(q1.poll());
        //交换q1和q2的位置
        Queue<E> tmp=q1;
        q1=q2;
        q2=tmp;
        return ret;
    }

    //4.判断栈是否为空
    public boolean empty(){
        return q1.isEmpty();
    }
}

public class Test{
    public static void main(String[] args) {
        MyStack<Integer> my=new MyStack<>();
        my.push(1);
        my.push(2);
        my.push(3);
        System.out.println(my.peek());
        my.pop();
        System.out.println(my.peek());
        my.pop();
        my.pop();
        System.out.println(my.empty());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

 
 
运行结果：