ShadowyHalo 永久会员 2025年6月7日下午7:51

class MyQueue {
Deque inStack;//存后入的元素，后入后出
Deque outStack;//为空时将in压入out

public MyQueue() {
    inStack = new ArrayDeque<Integer>();
    outStack = new ArrayDeque<Integer>();
}

public void push(int x) {
    inStack.push(x);
}

public int pop() {
    if (outStack.isEmpty()) {
        in2out();
    }
    return outStack.pop();
}

public int peek() {
       if (outStack.isEmpty()) {
        in2out();
    }
    return outStack.peek();
}

public boolean empty() {
    return inStack.isEmpty() && outStack.isEmpty();
}

 private void in2out() {
    while (!inStack.isEmpty()) {
        outStack.push(inStack.pop());
    }
}

}

/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/

0 赞同 0 条回复

Lil Lee_ 普通 2024年12月3日下午4:38

//双栈实现
class CQueue {
    LinkedList<Integer> A, B;
    public CQueue() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }

    public void appendTail(int value) {
        A.addLast(value);
    }

    public int deleteHead() {
        if(!B.isEmpty()) return B.removeLast();
        if(A.isEmpty()) return -1;
        while(!A.isEmpty()){
            B.addLast(A.removeLast());
        }
        return B.removeLast();
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

0 赞同 0 条回复

yelinliner 普通 2024年12月2日上午11:39

###

class CQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }

    public void appendTail(int value) {
        // 第一个栈做入队操作
        stack1.push(value);
    }

    public int deleteHead() {
        // 第二个栈模拟出队操作
        if (!stack2.isEmpty()) {
            // 第二栈有值的时候直接出队
            return stack2.pop();
        } else if (!stack1.isEmpty()) {
            // 否则从第一个栈中把值入栈后再出队
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        } else {
            // 都没有元素时，返回-1
            return -1;
        }

    }
}

0 赞同 0 条回复

YULONG 永久会员 2024年12月1日上午12:06

/**
实现思路:
用两个栈两次LIFO操作实现一个队列的FIFO
一个入栈，一个出栈，pop时，如果出栈为空，则从入栈转移元素，每个数至多入栈两次，出栈两次，均摊时间复杂度为O(1)
 */

class CQueue {

    Deque<Integer> st1;
    Deque<Integer> st2;

    public CQueue() {
        st1 = new ArrayDeque<>();
        st2 = new ArrayDeque<>();
    }

    public void appendTail(int value) {
        st1.add(value);
    }

    public int deleteHead() {
        if (st2.isEmpty()){
            while (!st1.isEmpty()){
                st2.add(st1.pollLast());
            }
        }
        if (st2.isEmpty()){
            return -1;
        }
        return st2.pollLast();
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

0 赞同 0 条回复

mpweixin用户普通 2024年11月30日下午7:20

有一个细节就是 pop阶段每次都是先判断s2是否为空

class CQueue:

    def __init__(self):
        self.s1 = []
        self.s2 = []

    def appendTail(self, value: int) -> None:
        self.s1.append(value)


    def deleteHead(self) -> int:
        if self.s2:
            self.s2.pop()
        if not self.s1:
            return -1
        while self.s1:
            self.s2.append(self.s1.pop())
        return self.s2.pop()

0 赞同 0 条回复

Firefly 普通 2024年11月30日上午10:41

两个栈模拟队列
class CQueue {
public:
CQueue() {

}

void appendTail(int value) 
{
    m_sk1.push(value);
}

int deleteHead() 
{
    if(m_sk2.empty())
    {
        while(!m_sk1.empty())
        {
            m_sk2.push(m_sk1.top());
            m_sk1.pop();
        } 
    }

    if(!m_sk2.empty())
    {
        auto  nValue=m_sk2.top();
        m_sk2.pop();
        return nValue;
    }
    return -1;
}

private:
std::stack m_sk1;
std::stack m_sk2;
};

/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/

0 赞同 0 条回复

岱永久会员 2024年11月29日下午3:01

两个栈模拟队列

class CQueue {

    LinkedList<Integer> A,B;
    public CQueue() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }

    public void appendTail(int value) {
        A.addLast(value);
    }

    public int deleteHead() {
        if(!B.isEmpty()) return B.removeLast();
        if(A.isEmpty())return -1;
        while(!A.isEmpty()) B.addLast(A.removeLast());
        return B.removeLast();
    }
}

0 赞同 0 条回复

陆狗陆狗普通 2024年11月28日下午11:19

class CQueue {

    private Stack<Integer> stackIn;

    private Stack<Integer> stackOut;

    public CQueue() {
        stackIn=new Stack<Integer>();
        stackOut=new Stack<Integer>();
    }

    public void appendTail(int value) {
        stackIn.push(value);
    }

    public int deleteHead() {
        // 把stackIn的元素挪到stackOut中，实现数据的反转
       if(stackOut.isEmpty() && !stackIn.isEmpty()){
            while(!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
            }
       }
       return stackOut.isEmpty()?-1:stackOut.pop();
    }
}

0 赞同 0 条回复

hjx 普通 2024年11月26日下午8:25

代码
class CQueue {
Stacks1;
Stacks2;
public CQueue() {
s1=new Stack<>();
s2=new Stack<>();
}

public void appendTail(int value) {
    s2.push(value);
}

public int deleteHead() {
    if(s1.isEmpty()&&s2.isEmpty())
        return -1;
    if(!s1.isEmpty()) 
        return s1.pop();
    else{
        while(!s2.isEmpty()){
            s1.push(s2.pop());
        }
        return s1.pop();
    }
}

}
// 4
//3 2 1

/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/

0 赞同 0 条回复

🌟 普通 2024年11月26日下午7:44

“`cpp
//测试
type MyQueue struct {
slice []int // 切片实现队列

“`cpp

0 赞同 0 条回复

生活在经验里普通 2024年11月26日上午11:18

type MyQueue struct {
    slice []int // 切片实现队列
}

func Constructor() MyQueue {
    return MyQueue{slice: make([]int, 0)}
}

func (this *MyQueue) Push(x int) {
    this.slice = append(this.slice, x)
}

func (this *MyQueue) Pop() int {
    element := this.slice[0]
    this.slice = this.slice[1:]
    return element
}

func (this *MyQueue) Peek() int {
    return this.slice[0]
}

func (this *MyQueue) Empty() bool {
    return len(this.slice) <= 0
}

0 赞同 0 条回复

越努力越幸运普通 2024年11月25日下午11:43

“`c++
class CQueue {
public:
CQueue() {

}

void appendTail(int value) {
    stack1.push(value);

}

int deleteHead() {
    if(!stack2.empty())
    {
        int res = stack2.top();
        stack2.pop();
        return res;
    }
    if(!stack1.empty())
    {
        while(!stack1.empty())
        {
            stack2.push(stack1.top());
            stack1.pop();
        }
        int res = stack2.top();
        stack2.pop();
        return res;
    }
    return -1;
}

private:
stack stack1;
stack stack2;
};

“`
使用两个栈模拟队列

0 赞同 0 条回复

秋山丽奈普通 2024年11月25日下午7:19

使用两个栈模拟队列

class CQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    public CQueue() {
        this.stackIn = new Stack<>();
        this.stackOut = new Stack<>();

    }

    public void appendTail(int value) {
        while(!this.stackOut.isEmpty()){
            this.stackIn.push(this.stackOut.pop());
       }
        this.stackIn.push(value);
    }

    public int deleteHead() {
       if(this.stackIn.isEmpty() && this.stackOut.isEmpty()){
            return -1;
       }

       while(!this.stackIn.isEmpty()){
            this.stackOut.push(this.stackIn.pop());
       }

      return  this.stackOut.pop();

    }
}

0 赞同 0 条回复

Pendulumpal 普通 2024年11月25日下午4:13

将先进后出翻转一下

“`c++
class CQueue {
public:
stacksk_in;
stacksk_out;
CQueue() {

}

void appendTail(int value) {
    sk_in.push(value);
}

int deleteHead() {
    int res=-1;
    if(!sk_out.empty()){
        res=sk_out.top();
        sk_out.pop();
    }else{
        while(sk_in.size()){
            sk_out.push(sk_in.top());
            sk_in.pop();
        }
        if(sk_out.size()){
        res=sk_out.top();
        sk_out.pop();
        }
    }
    return res;
}

};

“`

0 赞同 0 条回复

无言永久会员 2024年11月25日下午12:51

class CQueue {
public:
    stack<int> stk1;
    stack<int> stk2;
    CQueue() {

    }

    void appendTail(int value) {
        // 还书
        stk1.push(value);
    }

    int deleteHead() {
        // 借书
        if(stk2.empty()) {
            if(stk1.empty()) return -1;
            while(!stk1.empty()) {
                stk2.push(stk1.top());
                stk1.pop();
            }
        }
        int res = stk2.top();
        stk2.pop();
        return res;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */
时间复杂度: O(1) 
空间复杂度: O(N)

0 赞同 0 条回复

黑键〰普通 2024年11月25日上午11:08

var CQueue = function() {
    this.inStack = []
    this.outStack = []
};

/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function(value) {
    this.inStack.push(value)
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    // 输出栈空, 没有书能借出
    if(!this.outStack.length) {
        // 输入栈空，也没有还的书
        if(!this.inStack.length) {
            return -1
        }
        // 输入栈不空，有还的书
        while(this.inStack.length) {
            // out栈逐步存入从in栈pop出来的值，实现反向
            this.outStack.push(this.inStack.pop())
        }
    }
    return this.outStack.pop()
};

/** 
 * Your CQueue object will be instantiated and called as such:
 * var obj = new CQueue()
 * obj.appendTail(value)
 * var param_2 = obj.deleteHead()
 */

基础题型，一个栈存输入，一个栈存输出。in栈每次接收还的书，out栈每次相当于把in栈逆序存了之后，就可以pop最早还进来的书了

0 赞同 0 条回复

zing 普通 2024年11月25日上午10:59

妙啊~~~

class CQueue:

    def __init__(self):
        self.A, self.B = [], []        

    def appendTail(self, value: int) -> None:
        self.A.append(value)

    def deleteHead(self) -> int:
        # 如果列表B不为空，应从B删除元素为当前队头元素，不能在B不为空的情况下把A的元素放入
        # pop()返回栈顶元素
        if self.B:  return self.B.pop()

        # B为空，再将A的元素放入B
        if not self.A: return -1
        while self.A:
            self.B.append(self.A.pop())
        return self.B.pop()

0 赞同 0 条回复

Poetry and distance 永久会员 2024年11月25日上午1:20

思路：利用二个栈实现队列功能，即在先进先出的时候将栈中的顺序遍历出来给另一个栈，使得另一个栈的开头元素就是第一个入栈的元素，使得第二个栈pop即可得到第一个栈 先进先出的结果
class CQueue {
    Stack s1;
    Stack s2;
    public CQueue() {
        s1=new Stack<>();
        s2=new Stack<>();
    }

    public void appendTail(int value) {
        s1.push(value);
    }

    public int deleteHead() {
        if(!s2.empty())
            return s2.pop();
        if(!s1.empty()){
            while(!s1.empty())
                s2.push(s1.pop());
            return s2.pop();
        }
        return -1;
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */
时间复杂度:O(n)
空间复杂度:O(n)

0 赞同 0 条回复

Xiang. 永久会员 2024年11月24日下午11:48

思路：用栈A、B来实现队列，A负责插入数据，B负责删除数据（当B为空时，则将A的数据压入B中）
class CQueue {
    Stack< Integer > A;
    Stack< Integer > B;
    public CQueue() {
        A = new Stack<>();
        B = new Stack<>();

    }

    public void appendTail(int value) {
        A.push(value);

    }

    public int deleteHead() {
        if(!B.isEmpty()){
            return B.pop();
        }

        if(!A.isEmpty()){
            while(!A.isEmpty()){
                B.push(A.pop());
            }

            return B.pop();
        }

        return -1;

    }
}

0 赞同 0 条回复

Jerry 普通 2024年11月24日下午10:49

class CQueue {
public:
    stack<int> writestack;
    stack<int> readstack;
    CQueue() {

    }

    void appendTail(int value) {
       writestack.push(value);
    }

    int deleteHead() {
        if(readstack.empty() && writestack.empty()){
            return -1;
        }
        int res;
        if(!readstack.empty()){
            res = readstack.top();
            readstack.pop();
        }
        else if(readstack.empty()){
            while(!writestack.empty()){
                int value = writestack.top();
                readstack.push(value);
                writestack.pop();
            }
            res = readstack.top();
            readstack.pop();
        }
        return res;
    }
};

两个栈模拟

0 赞同 0 条回复

张君雅小妹妹普通 2024年11月24日下午9:58

class CQueue {
    Stack<Integer> stack1;  // 要提前声明类型，否则会报Object无法转换到int
    Stack<Integer> stack2;
    public CQueue() {
        stack1 = new Stack();
        stack2 = new Stack();
    }

    public void appendTail(int value) {
        stack1.push(value);

    }

    public int deleteHead() {
        if(!stack2.isEmpty()){
            return stack2.pop();
        } else {
            if(!stack1.isEmpty()){
                while(!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
                return stack2.pop();
            } else {
                return -1;
            }
        }
    }
}

stack1为空判断很重要

0 赞同 0 条回复

苯庸普通 2024年11月24日下午5:24

class MyQueue {
Stack st1;
Stack st2;

public MyQueue() {
    st1 = new Stack();
    st2 = new Stack();
}

public void push(int x) {
    st1.push(x);
}

public int pop() {
    int peek = peek();
    if(peek != -1){
        st2.pop();
    }
    return peek;
}

public int peek() {
    if(!st2.isEmpty()){
        return st2.peek();
    }
    if(!st1.isEmpty()){
        while(!st1.isEmpty()){
            st2.push(st1.pop());
        }
        return st2.peek();
    }
    return -1;
}

public boolean empty() {
    return st1.isEmpty() && st2.isEmpty();
}

}
时间：O（1）
空间：O（n）

0 赞同 0 条回复

🍊 普通 2024年11月24日下午4:39

双栈
class CQueue {
Stack in = new Stack<>(), out = new Stack<>();
public CQueue() {

}

public void appendTail(int value) {
    in.push(value);
}

public int deleteHead() {
    if(!out.isEmpty()){
        return out.pop();
    }
    if(in.isEmpty()) return -1;
    while(!in.isEmpty()){
        out.push(in.pop());
    }
    return out.pop();
}

}

/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/

0 赞同 0 条回复

月下足迹普通 2024年11月24日下午1:44

//时间复杂度O(1)，空间复杂度O(N)

class CQueue {
Stack inStack,outStack;

    public CQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    public void appendTail(int value) {
        inStack.push(value);

    }

    public int deleteHead() {
        if(outStack.isEmpty() && inStack.isEmpty()) {
            return -1;
        }

        if(!outStack.isEmpty()) {

            return outStack.pop();

        }else {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
            return outStack.pop();
        }

        }
}

0 赞同 0 条回复

youngsir 普通 2024年11月24日上午9:57

打卡

class CQueue {
private:
    stack<int> s1;
    stack<int> s2;
public:
    CQueue() {

    }

    void appendTail(int value) {
        s1.push(value);

    }

    int deleteHead() {
        if(!s2.empty()){
            int result  = s2.top();
            s2.pop();
            return result;
        }
        if(s1.empty()){
            return -1;
        }
        if(!s1.empty()){
            int temp = s1.top();
            s1.pop();
            s2.push(temp);
        }
        int result = s2.top();
        s2.pop();
        return result;



    }
};

0 赞同 0 条回复

Tom Yuan 普通 2024年11月24日上午5:24

用两个stack两手倒
重点pop的时候如果stack2空需要将stack1里所有的元素都pop并push进stack2 来保证顺序的正确性。

class CQueue:

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def appendTail(self, value: int) -> None:
        self.stack1.append(value)

    def deleteHead(self) -> int:
        if len(self.stack2):
            return self.stack2.pop()
        elif len(self.stack1):
            while len(self.stack1):
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()
        else:
            return -1

time O(n) space O(n)

0 赞同 0 条回复

jaron 普通 2024年11月23日下午10:42

class CQueue {

    // 成员
    Stack<Integer> in;
    Stack<Integer> out;

    // 初始化
    public CQueue() {
        in = new Stack();
        out = new Stack();
    }

    public void appendTail(int value) {
        in.push(value);
    }

    public int deleteHead() {
        // out里面有东西直接取
        if (!out.isEmpty()) {
            return out.pop();
        }
        // out里面取完了才能把in的导入out中
        if (!in.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
            return out.pop();
        }
        return -1;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年11月23日下午10:27

class CQueue {
public:
    stack<int> value1;
    stack<int> value2;
    CQueue() {
    }

    void appendTail(int value) {
        value1.push(value);
    }

    int deleteHead() {
        if(!value2.empty()){
            int result = value2.top();
            value2.pop();
            return result;
        }
        if(value1.empty()){
            return -1;
        }
        while(!value1.empty()){
            int temp = value1.top();
            value1.pop();
            value2.push(temp);
        }
        int result = value2.top();
        value2.pop();
        return result;
    }
};

思路：共两个栈，一个用做输入，一个用于输出。对于新到来的数据，全部放入输入栈内；需要输出时，如果输出栈不空，则输出栈栈顶即为结果，如果输出栈为空，则将输入栈的内容逐一弹出并压入输出栈内，此时输出栈栈顶即为结果。
时间复杂度O(N)，空间复杂度O(N)。

0 赞同 0 条回复

lQl 永久会员 2024年11月23日下午10:02

时间复杂度O(n)
空间复杂度O(n)

class CQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
    public CQueue() {
        s1 = new Stack<Integer>();
        s2 = new Stack<Integer>();
    }

    public void appendTail(int value) {
        while(!s2.empty()){
            s1.push(s2.pop());
        }
        s1.push(value);
    }

    public int deleteHead() {
        while(!s1.empty()){
            s2.push(s1.pop());
        }
        if(!s2.empty())
        return s2.pop();
        else
        return -1;
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

0 赞同 0 条回复

晓宇普通 2024年11月23日下午9:39

class CQueue {
private:
    stack s1;
    stack s2;
public:
    CQueue() {
        
    }
    
    void appendTail(int value) {
        s1.push(value);
    }
    
    int deleteHead() {

        int ans;
        if(!s2.empty()){
            ans = s2.top();
            s2.pop();
            return ans;
        }
        if(s1.empty()) return -1;
        while(!s1.empty()){
            s2.push(s1.top());
            s1.pop();
        }
        ans = s2.top();
        s2.pop();
        return ans;
    
        // while(!s1.empty()){
        //     s2.push(s1.top());
        //     s1.pop();
        // }
        // if(s2.empty()) return -1;
        
        // int ans = s2.top();
        // s2.pop();
        // while(!s2.empty()){
        //     s1.push(s2.top());
        //     s2.pop();
        // }
        // return ans;
    }
};

时间复杂度：o(n) 空间复杂度:o(n)

0 赞同 0 条回复

Renasc 普通 2024年11月23日下午9:05

class CQueue {

    // 创建两个栈，用于入队和出队
    Stack<Integer> in = new Stack<>();
    Stack<Integer> out = new Stack<>();

    // 构造函数初始化
    public CQueue() {
        in = new Stack<>();
        out = new Stack<>();
    }

    // 入队
    public void appendTail(int value) {
        in.push(value);
    }

    // 出队
    public int deleteHead() {
        // 先检查out栈里有没有元素
        if (!out.isEmpty()) {
            return out.pop();
        }

        // 如果out栈没有元素，则把in栈中的元素 出栈  到out栈中, 然后再出栈
        if (!in.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }

            return out.pop();
        }

        // 如果in栈中都没有元素了，就直接返回-1
        return -1;
    }
}

0 赞同 0 条回复

Kisara 普通 2024年11月23日下午8:54

class CQueue {

    Stack<Integer> stack1;
    Stack<Integer> stack2;
    //初始化
    public CQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }

    //入队
    public void appendTail(int value) {
        stack1.push(value);
    }

    //出队
    public int deleteHead() {
        if(stack2.empty()&&stack1.empty()) return -1;
        if(stack2.empty()&&!stack1.empty()){
            while(!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

入队操作时间复杂度为O(1)
出队操作最坏情况下O(N) 平均复杂度其实是O(1)
空间复杂度O(N)

0 赞同 0 条回复

休一普通 2024年11月23日下午8:43

1.思路分析

a.创建两个栈，一个用于作为输入函数的使用对象，一个作为输出函数的使用对象。
b.如果需要输出，则将输入栈的元素全部放置到输出栈中，由于栈起到逆序打印的作用，如果逆序两次，则会变成队列的正序。

2.代码

class MyQueue {
private:
    stack<int> sIn;
    stack<int> sOut;
public:
    MyQueue() {

    }

    void push(int x) {
        sIn.push(x);
    }

    int pop() {
        if(sOut.empty())
        {
            while(!sIn.empty())
            {
                int val = sIn.top();
                sIn.pop();
                sOut.push(val);
            }
        }
        int res = sOut.top();
        sOut.pop();
        return res;
    }

    int peek() {
        int res =  this->pop();
        sOut.push(res);
        return res;
    }

    bool empty() {
        return sIn.empty() && sOut.empty();
    }
};

3.复杂度分析

a.时间复杂度，o(n)将 in 栈中的所有元素逐一弹出并压入 out 栈。
b.空间复杂度，o(n)创建了额外的栈数据结构用于模拟队列。

0 赞同 0 条回复

迢迢星野普通 2024年11月23日下午7:59

class CQueue {
    Stack<Integer> in;
    Stack<Integer> out;

    public CQueue() {
        in = new Stack<>();
        out = new Stack<>();
    }

    public void appendTail(int value) {
        // 入队操作：in 操作元素入队
        in.push(value);
    }

    public int deleteHead() {
        // 将 in 中的元素逐一出栈，并添加到 out，此时 out 的栈顶元素就是队头元素
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
        return out.isEmpty() ? -1 : out.pop();
    }
}

思路

基于两个栈（in 和 out）实现的队列，分别用于实现队列的入队和出队操作。

构造方法

初始化两个栈。

入队方法

appendTail(int value) 将元素 value 压入 in 栈。
时间复杂度：O(1)，in 栈的入栈操作。
空间复杂度：O(n)，两个栈

出队方法

deleteHead()：out 栈的栈顶元素就是队列的头部元素。
如果 out 栈为空，将 in 栈中的所有元素逐一弹出并压入 out 栈，此时 out 栈的栈顶元素就是队列头部元素。
返回出队的元素：要么是 -1，要么是 out 的栈顶元素。
时间复杂度：O(n)，将 in 栈中的所有元素逐一弹出并压入 out 栈。
空间复杂度：O(n)，两个栈。

1 赞同 0 条回复

【基本数据结构】剑指 Offer 09. 用两个栈实现队列

共以下 34 个回答

1.思路分析

2.代码

3.复杂度分析

思路

构造方法

入队方法

出队方法

# 回答此问题取消回复

【基本数据结构】剑指 Offer 09. 用两个栈实现队列

共以下 34 个回答

1.思路分析

2.代码

3.复杂度分析

思路

构造方法

入队方法

出队方法

# 回答此问题 取消回复

# 回答此问题取消回复