【Java数据结构】详解Stack与Queue（四）

🔒文章目录：

1.❤️❤️前言~🥳🎉🎉🎉

2.用队列实现栈 

3.用栈实现队列

4.栈和队列存放null

5.总结 

---

1.❤️❤️前言~🥳🎉🎉🎉

  

2.用队列实现栈 

📌题目描述：

📋题目示例 

⏳解题思路  

  代码示例 （包含测试模拟的栈功能是否实现的代码） 

class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;
    public MyStack() {
        queue1 =new LinkedList<>();
      queue2=new LinkedList<>();

        }
    public void push(int x) {
        if(!queue1.isEmpty())
            queue1.offer(x);
        else {
            if (!queue2.isEmpty())
                queue2.offer(x);
            else
                queue1.offer(x);
        }
    }

    public int pop() {
    if(!queue1.isEmpty()){
    while(queue1.size()!=1){
       queue2.offer(queue1.poll()) ;
    }
    return queue1.poll();
    }
    else {
        while(queue2.size()!=1){
            queue1.offer(queue2.poll()) ;
        }
        return queue2.poll();
    }
    }

    public int top() {
        if(!queue1.isEmpty()){
            while(queue1.size()!=1){
                queue2.offer(queue1.poll()) ;
            }
          int key= queue1.poll();
            queue2.offer(key);
            return key;
        }
        else {
            while(queue2.size()!=1){
                queue1.offer(queue2.poll()) ;
            }
            int key= queue2.poll();
            queue1.offer(key);
            return key;
        }
    }

    public boolean empty() {
     if(queue1.isEmpty()&&queue2.isEmpty())
         return true;
     else
         return false;
    }
}

      //每次调用 pop 和 top 都保证栈不为空
 

public class Test{
    public static void main(String[] args) {
        MyStack myStack=new MyStack();
        myStack.push(1);//入栈
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        System.out.println(myStack.top());//获取栈顶元素
        System.out.println(myStack.pop());//出栈
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.empty());
//判断栈是否为空，如果为空返回true，否则返回false
    }

}

---

该题链接：用队列实现栈

3.用栈实现队列

📌题目描述：

📋题目示例

⏳解题思路 

   代码示例 （包含测试模拟的队列功能是否实现的代码）

class MyQueue {
  public Stack<Integer> stack1;
  public Stack<Integer> stack2;
    public MyQueue() {
      stack1=new Stack<>();
      stack2=new Stack<>();
    }
    
    public void push(int x) {
      stack1.push(x);
    }
    
    public int pop() {
     if(stack2.empty()){
       while(!stack1.empty())
       stack2.push(stack1.pop());
     }
       return stack2.pop();
    }
    
    public int peek() {
      if(stack2.empty()){
        while(!stack1.empty())
          stack2.push(stack1.pop());
      }
      return stack2.peek();
    }

    
    public boolean empty() {
          if(stack1.empty()&&stack2.empty())
            return true;
          else
            return false;
    }
}
// 一个空的队列不会调用 pop 或者 peek 操作



public class Test1 {
    public static void main(String[] args) {
      MyQueue myQueue=new MyQueue();
      myQueue.push(4);
      myQueue.push(3);
      myQueue.push(2);
      myQueue.push(1);

      System.out.println(myQueue.peek());
      myQueue.pop();
      myQueue.pop();
      System.out.println(myQueue.peek());
      System.out.println(myQueue.empty());
    }
  }

该题链接：用栈实现队列 

4.栈和队列存放null

public class Test1 {
    public static void main(String[] args) {
        Stack<Integer> stack=new Stack<>();//如下证明栈能存放null
        stack.push(null);
        System.out.println(stack.size());
        System.out.println(stack.peek());
        System.out.println(stack.pop());

        Queue<Integer> queue=new LinkedList<>();//如下证明队列能存放null
        queue.offer(null);
        System.out.println(queue.size());
        System.out.println(queue.peek());
        System.out.println(queue.poll());
    }
}

---

5.总结