leedcode225.用队列实现栈（java版）

题目:链接

题目简介

leedcode225.用队列实现栈（java版）

题目解析：题目要求用对列实现栈；目标：用队列模拟栈的特性：先进后出

明确队列和栈的特性：

队列：先进先出

特殊的队列–双端对列：两端都可以进行插入和删除

栈：先进后出

方法一：双端对列

补充java中双端创建对象和常见的方法：

创建对象：可以使用Java集合框架提供的Deque接口的实现类，例如ArrayDeque、LinkedList等。以ArrayDeque为例，可以通过以下步骤创建一个ArrayDeque对象

Deque deque = new ArrayDeque();

常见方法：

addFirst(e)：在队列头部插入元素e

addLast(e)：在队列尾部插入元素e

removeFirst()：移除并返回队列头部的元素

removeLast()：移除并返回队列尾部的元素

peekLast()方法可以获取双端队列（Deque）的队尾元素，但不会从队列中移除它

双端对列有一个很好的特性：队尾可以插入和删除，这不就是栈的特性吗？

举例：我们顺序插入 1，2，3.

leedcode225.用队列实现栈（java版）

只在队尾进行插入和删除，就是一个逻辑上的栈；

代码如下：

class MyStack {
    Deque q1;
   

    public MyStack() {
        q1=new ArrayDeque();
       
    }
    
    public void push(int x) {
        q1.addLast(x);
    }
    
    public int pop() {
         
        return q1.removeLast();
    }
    
    public int top() {
        return  q1.peekLast();
    }
    
    public boolean empty() {
        return q1.isEmpty() ;
    }
 
}

方法二:两个普通对列

若只在队尾添加元素，在队头删除元素，可以用另一个队列作为中转，交换元素顺序实现元素的先进后出；

leedcode225.用队列实现栈（java版）

代码逻辑：在添加元素之前，需要把队列1的元素移动到队列2中，在从队列2中移动到队列1中，【当然中转队列可能是多余的，我们也可以直接用一个队列实现】

    public void push(int x) {
        while (q1.size() > 0) {
            q2.add(q1.poll());
        }
        q1.add(x);
        while (q2.size() > 0) {
            q1.add(q2.poll());
        }
    }

完整代码：

class MyStack {
    Queue q1;
     Queue q2;
   

    public MyStack() {
        q1=new LinkedList();
        q2=new LinkedList();
       
    }
    
    public void push(int x) {
        while(!q1.isEmpty()){
            q2.add(q1.remove());
        }
        q1.add(x);
        while(!q2.isEmpty()){
            q1.add(q2.remove());
        }
    }
    
    public int pop() {
         
        return q1.remove();
    }
    
    public int top() {
        return  q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty() ;
    }
 
}

与用栈实现队列略有差异，大家可以参考这篇博客：用栈实现对列

方法三：一个普通对列

可以看到用两个队列先显得冗余，可以直接在一个队列中进行中转。

leedcode225.用队列实现栈（java版）

代码块：

class MyStack {
    Queue q1;
     
   

    public MyStack() {
        q1=new LinkedList();    
       
    }
    
    public void push(int x) {
        q1.add(x);
        int num=q1.size();
        while(num>1){
            q1.add(q1.remove());
            num--;
        }
         
        
    }
    
    public int pop() {
         
        return q1.remove();
    }
    
    public int top() {
        return  q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty() ;
    }
 
}

leedcode232.用栈实现队列https://blog.csdn.net/m0_74132709/article/details/136010157