当前位置：
  1. 首页
  2. 剑指offer最优解
  3. 正文

本问题对应的 leetcode 原文链接：剑指 Offer 09. 用两个栈实现队列

问题描述

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
[[],[3],[],[],[]]
输出：[null,null,3,-1,-1]

示例 2:

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

限制：

  • 1 <= values <= 10000
  • 最多会对appendTail、deleteHead进行10000 次调用

解题思路

视频讲解直达： 本题视频讲解

代码实现

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.isEmpty()){
            return stack2.pop();
        }

        if(!stack1.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }

            return stack2.pop();
        }

        return -1;

    }
}

Python

class CQueue(object):

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

    def appendTail(self, value):
        """
        :type value: int
        :rtype: None
        """
        self.stack1.append(value)

    def deleteHead(self):
        """
        :rtype: int
        """
        if self.stack2:
            return self.stack2.pop()

        if self.stack1:
            while self.stack1:
                self.stack2.append(self.stack1.pop())

            return self.stack2.pop()

        return -1


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

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<int> stack1;
    stack<int> stack2;
};

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

Go

type CQueue struct {
    stack1 []int
    stack2 []int
}

func Constructor() CQueue {
    return CQueue{}
}

func (this *CQueue) AppendTail(value int)  {
    this.stack1 = append(this.stack1, value)
}

func (this *CQueue) DeleteHead() int {
    if len(this.stack2) > 0 {
        res := this.stack2[len(this.stack2)-1]
        this.stack2 = this.stack2[:len(this.stack2)-1]
        return res
    }

    if len(this.stack1) > 0 {
        for len(this.stack1) > 0 {
            this.stack2 = append(this.stack2, this.stack1[len(this.stack1)-1])
            this.stack1 = this.stack1[:len(this.stack1)-1]
        }

        res := this.stack2[len(this.stack2)-1]
        this.stack2 = this.stack2[:len(this.stack2)-1]
        return res
    }

    return -1
}


/**
 * Your CQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AppendTail(value);
 * param_2 := obj.DeleteHead();
 */

JS

/**
 * @constructor
 */
var CQueue = function() {
    this.stack1 = [];
    this.stack2 = [];
};

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

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    if(!this.stack2.length){
        while(this.stack1.length){
            this.stack2.push(this.stack1.pop());
        }
    }

    if(!this.stack2.length){
        return -1;
    }else{
        return this.stack2.pop();
    }
};

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

发表回复

后才能评论

评论(1)

  • Deckkker 普通 2024年4月27日 上午10:51

    class CQueue:

    def __init__(self):
    self.Stack_In = []
    self.Stack_Out = []

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

def deleteHead(self) -> int:
    if self.Is_empty():
        return -1

    if self.Stack_Out:
        return self.Stack_Out.pop()
    else:
        while self.Stack_In:
            self.Stack_Out.append(self.Stack_In.pop())
        return self.Stack_Out.pop()

def Is_empty(self):
    return not (self.Stack_In or self.Stack_Out)

    时间复杂度： O(1)，push 为 O(1)，pop 为均摊 O(1)。对于每个元素，至多入栈和出栈各两次（Stack_In和Stack_Out至多各进出栈一次），故均摊复杂度为 O(1)。

    空间复杂度：O(n)。其中 n 是操作总数。对于有 n 次 push 操作的情况，队列中会有 n 个元素，故空间复杂度为 O(n)。


剑指offer最优解系列教程