糖香香普通 2023年6月29日下午7:58

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(int i) {
            if (!stack2.isEmpty()) {
                return stack2.pop();
            } else {
                if (stack1.isEmpty()){
                    return -1;
                } else {
                    while (!stack1.isEmpty()){
                        stack2.push(stack1.pop());
                    }
                    return stack2.pop();
                }
            }
        }

    }

0 赞同 0 条回复

CrazyJavaBoy 永久会员 2023年3月24日上午10:39

class CQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public CQueue() {
        //注意要初始化 不然无法调用方法 
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

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

    public int deleteHead() {
        //stack2用来出队 如果stack2不是空就pop 
        if(!stack2.isEmpty()) { 
        //或者是stack2.size()!=0 因为isEmpty()与size()方法底层都是根据elementCount元素数量
            return stack2.pop();
        }
        //此时stack2为空 先让stack1全部出栈入到stack2 然后stack2 pop()
        if(!stack1.isEmpty()) {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
        return -1;
    }
}

0 赞同 0 条回复

lucca 普通 2022年12月31日下午5:19

ab两个栈，push时加到a，pop时从b取，如果b为空，就从a取，如果a也空，就返回-1

class CQueue {


    Stack<Integer> a = new Stack<>(), b = new Stack<>();
    public CQueue() {}

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

    public int deleteHead() {
        if (b.empty()) {
            if (a.empty()) return -1;
            while (!a.empty()) b.push(a.pop());
        }
        return b.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 条回复

努力刷题普通 2022年11月30日上午4:34

用两个栈实现一个队列
class CQueue(object):

    def __init__(self):
        self.stk_in = []
        self.stk_out = []

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


    def deleteHead(self):
        """
        :rtype: int
        """
        if not self.stk_out:
            while self.stk_in:
                self.stk_out.append(self.stk_in.pop())
        if self.stk_out:
            return self.stk_out.pop()
        return -1

0 赞同 0 条回复

Xiao 普通 2022年11月21日下午8:55

class CQueue {
    LinkedList<Integer> a;
    LinkedList<Integer> b;
    public CQueue() {
        a=new LinkedList<>();
        b=new LinkedList<>();
    }

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

    public int deleteHead() {
        /*
        三种情况
        当栈 B 不为空： B中仍有已完成倒序的元素，因此直接返回 B 的栈顶元素。
        否则当 A 为空： 即两个栈都为空，无元素，因此返回 -1−1 。
        否则将栈 A 元素全部转移至栈 B 中，实现元素倒序，并返回栈 B 的栈顶元素。
        */
        if(!b.isEmpty()){
            return b.removeLast();
        }
        if(a.isEmpty()){
            return -1;
        }else{
            while(!a.isEmpty()){
                b.addLast(a.removeLast());
            }
            return b.removeLast();
        }
    }
}

0 赞同 0 条回复

PatNick 普通 2022年11月20日下午1:46

class CQueue:

    def __init__(self):
        # 两个栈
        # list1用于入队列
        self.list1 = []
        # 用于出队列
        self.list2 = []

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

    def deleteHead(self) -> int:
        if len(self.list1) == 0:
            return -1
        else:
            # 每次都需要重制list2和list1内容，速度较慢
            # 原栈反转
           self.list2 = self.list1[::-1]
            # 弹出
           re = self.list2.pop()
            # 原栈中也删除
           self.list1 = self.list1[1:]

           return re

    def deleteHead1(self) -> int:

        # 如果list2有元素，直接pop
        if len(self.list2):
            return self.list2.pop()
        # list1list2都为空说明所有元素都被pop了
        else:
            if not len(self.list1):
                return -1
            # list2为空，但list1不为空，将list1中所有元素copy到list2中pop，并将list1清空用于下一次入队列
            else:
                self.list2 = self.list1[::-1]
                self.list1 = []
                return self.list2.pop()

0 赞同 0 条回复

🚲南下普通 2022年11月10日上午9:48

class CQueue {
public:
    stack<int> stIn;
    stack<int> stOut;

    CQueue() {

    }

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

    int deleteHead() {
        if(stOut.empty()){
            if(stIn.empty()){ //需要判断stIn是否为空
                return -1;
            }
            while(!stIn.empty()){
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }
};

0 赞同 0 条回复

如梦似歌普通 2022年11月9日下午8:47

class CQueue {
        //输入栈，用于appendTail进队操作
        Stack stack_1;

       //输出栈，用于deleteHead出队操作
        Stack stack_2;

public CQueue() {
    stack_1 = new Stack<>();
    stack_2 = new Stack<>();
}

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

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

}

0 赞同 0 条回复

hmmm 普通 2022年11月8日下午9:48

“`c++
class CQueue {
stack stack1;
stack stack2;
public:
CQueue() {
// 创建空队列
}

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

int deleteHead() {
    // 队头删除
    if(!stack2.empty()) //stack2非空
    {
        int x = stack2.top();
        stack2.pop();
        return x;
    }

    if(!stack1.empty())  //stack1非空
    {
        while(!stack1.empty())
        {
            stack2.push(stack1.top());
            stack1.pop();
        }
        int y = stack2.top();
        stack2.pop();
        return y;
    }
    return -1;
}

};

时间复杂度：O(1) appendTail为O(1),deleteHead为均摊O(1),对于每个元素至多入栈和出栈各两次，故均摊复杂度为O(1)【事实上最坏的时间复杂度是O(N)，因为包含while循环，但由于一个元素最多只可能搬运一次，所以均摊时间复杂度为O(1)】
空间复杂度：O(n) 其中n为操作总数，对于有n次appendTail操作的情况，队列中会有n个元素，故空间复杂度为O(n)

0 赞同 0 条回复

cute. 普通 2022年10月31日下午3:34

实现思路: 利用栈先进后出、队列先进进出的特点，队列尾部插入整数用于入栈的数组push实现，队列头部删除整数，先判断用于出栈的数组是否有值，没有值则将用于入栈的数组pop出的数组push进出栈数组，实现逆置，则出栈数组pop出的数值是对头的值

var CQueue = function() {
    // 输入栈，用于压入appendTail传入的数据
    this.inStack = [];
    // 输出栈，用于deleteHead操作
    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) {
        while(this.inStack.length) {
          this.outStack.push(this.inStack.pop());
        }
    }
    return this.outStack.length ? this.outStack.pop() : -1;
};

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

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

0 赞同 0 条回复

王艺超普通 2022年10月31日下午3:15

这道题只需要理解，队列是先进先出，栈是先进后出，再运用两个栈就可以实现先进先出了

class CQueue {
public:
    stack<int> inStack, outStack;

    void in2out()
    {
        while(!inStack.empty())
        {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }


public:
    CQueue() {

    }

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

    int deleteHead() {
        if(outStack.empty())
        {
            if(inStack.empty())
            {
                return -1;
            }
            in2out();
        }
        int temp = outStack.top();
        outStack.pop();
        return temp;
    }
};

0 赞同 0 条回复

泡芙永久会员 2022年10月31日上午10:01

思路：是232. 用栈实现队列的简化版，双栈实现队列其实就是将两个栈以相反的顺序放置（一个开口朝前s2，一个开口朝后s1），当调用 push 让元素入队时，只要把元素压入 s1 即可。调用peek查看队头元素利用栈先进后出的原则，当 s2 为空时，可以把 s1 的所有元素取出再添加进 s2，这时就是队列的先进先出顺序了。对于 pop 操作，先调用peek，只要保证s2不为空即可。
Time：O(1)，事实上最坏的时间复杂度是O(N)，因为包含while循环，但由于一个元素最多只可能搬运一次，所以均摊时间复杂度为O(1)
Space：O(N)，调用栈

class CQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;

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

    // 添加元素到队尾
    public void appendTail(int value) {
        s1.push(value);
    }

    // 删除队头的元素并返回
    public int deleteHead() {
        // 如果s2不为空，且s2的栈顶元素就是两个栈中最早加入的元素
        if(!s2.isEmpty()) {
            return s2.pop();
        }
        // 如果s1不为空，s2为空，则将栈s1中的元素倒序进入栈s2
        if(!s1.isEmpty()) {
            //把s1元素压入s2
            while(!s1.isEmpty()) {
                s2.push(s1.pop());
            }
            return s2.pop();
        }
        // 如果s1和s2都为空，返回-1
        return -1;
    }
}

0 赞同 0 条回复

cxxz 普通 2022年10月30日下午11:23

两次先入先出就是正常的队列的顺序了。

class CQueue {
public:
    stack<int> sk1; 
    stack<int> sk2;
    CQueue() {
    }

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

    // 新插入到队列尾的元素对于取出队列头无影响 所以sk1的push对于取head无影响
    int deleteHead() {
        if (!sk2.empty()){
            int ret = sk2.top();
            sk2.pop();
            return ret;
        }

        if ( !sk1.empty() ) {
            while ( !sk1.empty() ) {
                int temp = sk1.top();
                sk1.pop();
                sk2.push(temp);
            }

            int head = sk2.top();
            sk2.pop();
            return head;
        } else {
            return -1;
        }        
    }
};

0 赞同 0 条回复

阿白普通 2022年10月29日下午8:16

栈inStack负责输入，栈outStack负责输出；
如果outStack空了，就从inStack反向推入

class CQueue {
public:
    CQueue() {

    }

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

    int deleteHead() {
        if (outStack.empty())
        {
            while (!inStack.empty())
            {
                outStack.push(inStack.top());
                inStack.pop();
            }   
            if(!outStack.empty())
            {
                int a = outStack.top();
                outStack.pop();
                return a;   
            }
            else
                return -1;
        }
        else
        {
            int a = outStack.top();
            outStack.pop();
            return a;   
        }       
    }
private:
    std::stack<int> inStack, outStack;
};

0 赞同 0 条回复

xye 普通 2022年10月28日下午9:51

type CQueue struct {
    inStack, outStack []int
}


func Constructor() CQueue {
    return CQueue{}
}


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


func (this *CQueue) DeleteHead() int {
    if len(this.outStack) != 0 {
        tmp := this.outStack[len(this.outStack)-1]
        this.outStack = this.outStack[:len(this.outStack)-1]
        return tmp
    }else{
        if len(this.inStack) != 0 {
            for i, j:= 0, len(this.inStack); i < j; i++ {
                this.outStack = append(this.outStack, this.inStack[len(this.inStack)-1])
                this.inStack = this.inStack[:len(this.inStack)-1]
            }
            tmp := this.outStack[len(this.outStack)-1]
            this.outStack = this.outStack[:len(this.outStack)-1]
            return tmp
        }
        return -1
    }
}

利用数组做成两个栈，一个进一个出

0 赞同 0 条回复

Asphyxia 普通 2022年10月28日下午1:17

一个负责进，一个负责出

class Solution
{
public:
    void push(int node) {
        while(!stack1.empty()){
            int val = stack1.top();
            stack2.push(val);
            stack1.pop();
        }
        stack1.push(node);
        while(!stack2.empty()){
            int val = stack2.top();
            stack1.push(val);
            stack2.pop();
        }
    }

    int pop() {
        int val = stack1.top();
        stack1.pop();
        return val;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

0 赞同 0 条回复

潜行1 我是火车王！普通 2022年10月27日下午8:36

标准解法

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 not self.stack_out:
            if not self.stack_in:
                return -1
            else:
                while self.stack_in:
                    self.stack_out.append(self.stack_in.pop())

        return self.stack_out.pop()




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

0 赞同 0 条回复

just 普通 2022年10月27日下午8:05

//典中典
class CQueue {
private:
stack stin,stout;
public:
CQueue() {

}

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

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

}

};

0 赞同 0 条回复

星河普通 2022年10月27日下午6: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();
    }
}
时间O(1)，空间O(N)

0 赞同 0 条回复

一只骆驼普通 2022年10月27日下午5:09

用deque去实现，尽管只用了stack功能，但是运行时间也快很多;
两个栈，一个进一个出，当出的栈为空时，将进的栈里的元素倾倒进出的栈

Class CQueue {
    Deque stack1;
    Deque stack2;
    public CQueue() {
        stack1 = new LinkedList();
        stack2 = new LinkedList();
    }

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

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

    }
}

0 赞同 0 条回复

Chin 普通 2022年10月27日下午3:04

class CQueue {
   //  一个负责进，一个负责出
    Stack<Integer> stackIn = null;
    Stack<Integer> stackOut = null;
    public CQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

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

    public int deleteHead() {
        while(!stackIn.isEmpty()){
            stackOut.push(stackIn.pop());
        }
       return stackOut.isEmpty() ? -1 : stackOut.pop();
    }
}

0 赞同 0 条回复

lobort 普通 2022年10月27日下午2:16

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() {
        // if(in.isEmpty()&&out.isEmpty()){     
        //     return -1;
        // }
        // 这里会有三种种情况： 
                //1、 数据全在out里面 直接返回out的顶部数据   
                //2、in 里面有数据  需要先将in里面的数据群不转到out里面  才返回out的顶部数据
                //3、out、in里面都没有数据  空队列  按照题目要求返回-1
        if(!out.isEmpty()){
            return out.pop();
        }
        if(!in.isEmpty()){
            while(! in.isEmpty()){
                out.push(in.pop());
            }
            return out.pop();
        }
        return -1;
    }
}

0 赞同 0 条回复

追普通 2022年10月27日上午10:28

class CQueue {
public:

    stack<int> stack1;
    stack<int> stack2;
    CQueue() {
    }

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

    int deleteHead() {
        if(stack1.empty())  return -1;   //如果输入栈为空，则返回-1

        while(!stack1.empty()){
            stack2.push(stack1.top());
            stack1.pop();
        }
        int res = stack2.top();
        stack2.pop();              //当输入栈的数据全部给到输出栈之后，输出栈删除数据
//删除操作完成之后，如果输出栈内的元素不为空，则将输出栈的元素转回到输入栈，以保证数据顺序
        while(!stack2.empty()){    
            stack1.push(stack2.top());
            stack2.pop();
        }
        return res;
    }
};

注意：在删除数据之后需要将输入栈数据导回到输出栈，以保证后面输入元素与队列的顺序保持一致

0 赞同 0 条回复

绍熙普通 2022年10月27日上午10:08

解题思路：
栈无法实现队列功能：栈底元素（对应队首元素）无法直接删除，需要将上方所有元素出栈。
双栈可实现列表倒序：设有含三个元素的栈 A = [1,2,3]A=[1,2,3] 和空栈 B = []B=[]。若循环执行 AA 元素出栈并添加入栈 BB ，直到栈 AA 为空，则 A = []A=[] , B = [3,2,1]B=[3,2,1] ，即栈 BB 元素实现栈 AA 元素倒序。
利用栈 BB 删除队首元素：倒序后，BB 执行出栈则相当于删除了 AA 的栈底元素，即对应队首元素。

“`
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 条回复

酥合普通 2022年10月26日下午11:07

class CQueue {

    private Stack<Integer> a;
    private Stack<Integer> b;

    public CQueue() {
        a = new Stack<Integer>();
        b = new Stack<Integer>();
    }

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

    public int deleteHead() {
        if(a.empty() && b.empty()) {
            return -1;
        }
        if(!b.empty()) {
            return b.pop();
        }

        while(!a.empty()) {
            b.push(a.pop());
        }
        return b.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 条回复

Y7n05h 普通 2022年10月26日下午9:55

class CQueue {
    vector<int> in;
    vector<int> out;

public:
    CQueue() = default;
    void appendTail(int value) {
        in.push_back(value);
    }

    int deleteHead() {
        if (out.empty()) {
            if (in.empty()) return -1;
            for (auto i = in.crbegin(); i != in.crend(); ++i) {
                out.push_back(*i);
            }
            in.clear();
        }
        auto ret = out.back();
        out.pop_back();
        return ret;
    }
};

空间复杂度：O(n)

0 赞同 0 条回复

symbol 普通 2022年10月26日下午8:35

type CQueue struct {
    inStack,outStack []int 
}


func Constructor() CQueue {
    return CQueue{}
}


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


func (this *CQueue) DeleteHead() int {
    if len(this.outStack) == 0{
        if len(this.inStack) == 0{ //两个占都为空了 返回-1
            return -1
        }
        this.inStack2outStack() //元素搬迁
    }
    value := this.outStack[len(this.outStack)-1] //弹出栈顶元素
    this.outStack = this.outStack[:len(this.outStack)-1] //更新栈元素
    return value
}
func (this *CQueue)inStack2outStack(){
    for len(this.inStack) > 0{
        value := this.inStack[len(this.inStack)-1]
        this.outStack = append(this.outStack, value)
        this.inStack = this.inStack[:len(this.inStack)-1] //更新栈元素
    }
}

0 赞同 0 条回复

虾仁猪心普通 2022年10月26日下午6:58

思路：

设置两个栈，一个叫入栈stackIn(作用是先将元素放入这个栈)，一个叫出栈stackOut(模拟队列出栈时使用的栈)。
入队的操作，将元素放入stackIn这个栈。
当遇到出栈的操作时，
- 先执行dummyStackIn（）操作，这个函数是将stackIn中的所有元素，放入到stackOut这个栈中
- 再判断此时stackOut这个栈是否时空栈，如果为空，则返回-1，不为空，则执行出栈操作来模拟出队
dummyStackIn函数详解
- 先判断stackOut这个栈是否是空栈，如果不是空栈直接返回。
- 如果stackOut这个栈是空栈，那么将stackIn栈中的元素全部添加到stackOut这个栈中。

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

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

    public int deleteHead() {
        dummyStackIn();
        if(stackOut.isEmpty()){
            return -1;
        }
        return stackOut.pop();

    }
    public void dummyStackIn(){
        while(!stackOut.isEmpty()){
            return;
        }
        while(!stackIn.isEmpty()){
            stackOut.push(stackIn.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 条回复

mpweixin用户永久会员 2022年10月26日下午6:51

“`{r}
class CQueue {
private Stack stack1;
private Stack 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{
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        return stack2.isEmpty() ? -1 : stack2.pop();
    }
}

}

“`
我觉得好难，看到解析才有的思路。

0 赞同 0 条回复

乱世枭雄普通 2022年10月26日下午6:35

思路：
栈是先进后出，队列是先进先出，
两个栈，进栈1，出栈1，进栈2，出栈2，按这个顺序模拟队列
进不用考虑特殊情况，
出栈时要先判断栈1是否为空，不为空时先出1进2

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;
    }
}

0 赞同 0 条回复

你有点可爱喔普通 2022年10月26日下午5:19

基本思路：首先要知道栈和队列的特性。两个栈实现，一个实现入队操作，另一个实现出队操作。当然这种做法需要的是考虑出队的那个栈中为空与为空的情况下。为空的时候，需要将栈1中的元素pop出，将其push到出队栈中。这样就能保证队列先进先出的特性。

class CQueue {

    Stack<Integer> s1;
    Stack<Integer> s2;

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

    //压入栈1
    public void appendTail(int value) {
        s1.push(value);
    }

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

0 赞同 0 条回复

刺猬普通 2022年10月26日下午4:26

class CQueue {
private: 
    stack<int> inStack, outStack;
public:
    CQueue() {

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

    int deleteHead() {
        if(outStack.empty()) {
            if(inStack.empty())
                return -1;
            while(inStack.empty() == 0) {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        int value = outStack.top();
        outStack.pop();
        return value; 
    }
};

两栈实现队列

0 赞同 0 条回复

派大星普通 2022年10月26日下午2:02

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() {
        if(in.empty()&&out.empty()){
            return -1;
        }
        if(!out.empty()){
            int a = out.pop();
            return a;
        }else{
            while(!in.empty()){
                out.push(in.pop());
            }
            int a = out.pop();
            return a;
        }
    }
}

0 赞同 0 条回复

晨普通 2022年10月26日下午1:43

思路：栈的特性是先进后出，队列的特性是先进先出，通过设置两个栈，入栈直接加入栈1，出栈需要将栈1 元素压入栈2后，从栈2 出

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
        """
        # 1.栈2中有元素
        if self.stack2:
            return self.stack2.pop()
        # 2.栈1、栈2为空
        if not self.stack1:
            return -1
        # 3.栈1有元素
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

0 赞同 0 条回复

云雾里普通 2022年10月26日下午1:20

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() {
        //出栈为空，将判断入栈是否为空
        if(out.isEmpty()){
            //入栈为空，说明没有数据保存，返回-1
            if(in.empty()){
                return -1;
            }
            //入栈不为空，将入栈数据弹出存入出栈，使入栈数据倒序进入出栈
            while (!in.isEmpty()){
                out.push(in.pop());
            }
        }
        //出栈栈顶弹出即是存入入栈的顺序，即实现FIFO
        return out.pop();
    }
}

0 赞同 0 条回复

小肸永久会员 2022年10月26日下午12:42

思路：栈的特性是先进后出，而队列的特性是先进先出，怎么用栈实现队列，可以用两个栈来实现，一个栈stack1负责入队的元素，一个栈负责出队的元素。当有元素e需要入队时，把元素e放进栈stack1中，当有元素需要出队时，首先看看栈stack2是否为空，stack2不为空，直接将stack2栈顶的元素出栈，作为出队的元素；stack2为空，就将栈stack1的元素全部入栈到栈stack2中，再判断stack2是否为空，为空返回-1，不为空返回stack2的栈顶元素。入队的时间复杂度为O（1），出队的时间复杂度取决于当前栈stack2是否为空，stack2不为空，出队的时间复杂度为O(1），stack2为空，出队的时间复杂度为O(stack1.size())（即取决于栈stack1里面元素的个数），空间复杂度就是元素的个数。

class CQueue {
    private Stack<Integer> stack1;
    private 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 {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            if (stack2.isEmpty()) {
                return -1;
            } else {
                return stack2.pop();
            }
        }
    }
}

0 赞同 0 条回复

马啸天永久会员 2022年10月26日下午12:37

public class CQueue {

    //stack1 实现入队列
    //stack2 实现出队列
    Stack<Integer> stack1;
    Stack<Integer> stack2;

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

    public void appendTail(int value) {
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        stack1.push(value);
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    }

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

}

0 赞同 0 条回复

庄重普通 2022年10月26日上午11:46

class CQueue {
public:
    CQueue() {
        //清空两个栈
        while(!s1.empty()) s1.pop();
        while(!s2.empty()) s2.pop();
    }

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

    int deleteHead() {
        if(s1.empty() && s2.empty()) return -1;
        int ret = 0;
        //防止出现剩一个元素，弹出之后变为空，执行下一个if，return要在if里执行
        if(!s2.empty()){
            ret = s2.top();
            s2.pop();
            return ret;
        }
        if(s2.empty()){
            //已经判断s1不为空了啊
            for(;!s1.empty();){//for(int i = 0;i < s1.size();++i)这里为啥不能这样写？
//原因size是变化的，需要注意一下
                s2.push(s1.top());
                s1.pop();
            }
            ret = s2.top();
            s2.pop();
            return ret;
        }
        return -1;

    }
    stack s1;
    stack s2;
};
//时间复杂度O(n) n为队列长度
//空间复杂度O(1)

0 赞同 0 条回复

Tolkien 永久会员 2022年10月26日上午11:04

时间复杂度：O(1)
空间复杂度：O(n)
代码

class CQueue {
    Stack stack1;
    Stack stack2;

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

    public void appendTail(int value) {
        // 1. stack1存储队列数据
        stack1.push(value);
    }

    public int deleteHead() {
        // 3. 若stack2存在数据，则说明已在stack2里存储队列数据
        if (!stack2.isEmpty()) {
            return stack2.pop();
        }

        // 2. stack2倒序存储stack1内容，使栈底变栈顶，出栈变出队
        if (!stack1.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }

        return -1;
    }
}

0 赞同 0 条回复

@ 普通 2022年10月26日上午10:52

两个栈a和b,a栈用来存放数据,b栈存放的是的a依次出栈的数据，这样a栈出栈的顺序就刚好等于队列出队的顺序

class CQueue {
    Deque<Integer> stack1;//用来存放数据
    Deque<Integer> stack2;//用来出队的

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

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

    }

    public int deleteHead() {
        if(stack2.isEmpty() && stack1.isEmpty())
            return -1;

        if(stack2.isEmpty()){

            while(!stack1.isEmpty())
                stack2.push(stack1.pop());

        }


        return stack2.pop();

    }

    public static void main(String[] args) {
        CQueue cQueue = new CQueue();
        cQueue.appendTail(5);
        cQueue.appendTail(2);
        System.out.println(cQueue.deleteHead());
        System.out.println(cQueue.deleteHead());
    }
}

0 赞同 0 条回复

wxc 普通 2022年10月26日上午10:27

额

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 not self.stack1 :
            return -1
        while self.stack1 :
            self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

0 赞同 0 条回复

猫猫真可爱普通 2022年10月26日上午9:46

题目的输入一个是操作，一个是当前操作所操作的数据，输出是返回值。

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

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

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

0 赞同 0 条回复

是梦终空永久会员 2022年10月26日上午8:37

定义全局变量size，加入就++，删除就– 为0就无元素了，然后s2为空，s1不为空时候,把s1的元素给s2，
时间O(1)
空间O(n)

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

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

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

0 赞同 0 条回复

黎昕普通 2022年10月26日上午1:29

C语言实现

typedef struct {
    int pushstack[5000];
    int popstack[5000];
    int pushcur;//pushstack为空时指向0
    int popcur;//popstack为空时指向0
} CQueue;


CQueue* cQueueCreate() {
    CQueue* obj = (CQueue*)malloc(sizeof(CQueue));
    obj->pushcur = 0;
    obj->popcur = 0;
    return obj;
}

void cQueueAppendTail(CQueue* obj, int value) {
    if (obj->pushcur == 5000 && obj->popcur == 0) {
        for (int i = 0; i < 5000; i++) {
            obj->popstack[obj->popcur++] = obj->pushstack[obj->pushcur--];
        }
    }
    else {
        obj->pushstack[obj->pushcur++] = value;
    }
}

int cQueueDeleteHead(CQueue* obj) {
    if (obj->popcur == 0) {
        while (obj->pushcur != 0) {
            int tmp= obj->pushstack[obj->pushcur-1];
            obj->pushcur--;
            obj->popstack[obj->popcur++] = tmp;
        }
    }
    if (obj->popcur == 0)return -1;
    else {
        int tmp = obj->popstack[obj->popcur - 1];
        obj->popcur--;
        return tmp;
    }
}

void cQueueFree(CQueue* obj) {
    free(obj);
}

/**
 * Your CQueue struct will be instantiated and called as such:
 * CQueue* obj = cQueueCreate();
 * cQueueAppendTail(obj, value);

 * int param_2 = cQueueDeleteHead(obj);

 * cQueueFree(obj);
*/

0 赞同 0 条回复

cxc 普通 2022年10月26日上午12:03

class CQueue {
    LinkedList<Integer> a, b;
    public CQueue() {
        a = new LinkedList<>();
        b = new LinkedList<>();
    }

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

    public int deleteHead() {
        if(!b.isEmpty()) return b.removeLast();
        if(a.isEmpty()) return -1;
        //利用栈的特性，后进先出放入B中，即是倒叙
        while(!a.isEmpty()){
            b.addLast(a.removeLast());
        }

        return b.removeLast();
    }
}

0 赞同 0 条回复

Ruby🗽 普通 2022年10月25日下午11:53

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;
    }
}

0 赞同 0 条回复

宁永久会员 2022年10月25日下午11:40

只有控制出队的栈为空的时候才能从入队的栈填充元素进来

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

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

0 赞同 0 条回复

Haoyun 普通 2022年10月25日下午11:39

var CQueue = function() {
   this.pushStack = [];
   this.popStack = [];
};
CQueue.prototype.appendTail = function(value) {
   this.pushStack.push(value)
};

CQueue.prototype.deleteHead = function() {
  if(!this.popStack.length && !this.pushStack.length) {
      return -1;
  }
  if(!this.popStack.length) {
      while(this.pushStack.length) {
          this.popStack.push(this.pushStack.pop())
      }
  }
  return this.popStack.pop();
};

一个存一个取

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月25日下午11:28

class CQueue {
    /*
    如果使用stack会造成速度较慢，原因是stack继承vector接口，底层是object数组，需要考虑空间扩容和移位
    可以使用LinkedList来做Stack的容器，因为LinkedList实现了Deque接口，所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。
    */
    private LinkedList<Integer> stack1;
    private LinkedList<Integer> stack2;
    public CQueue() {
         stack1 = new LinkedList<Integer>();
        stack2 = new LinkedList<Integer>();
    }
    //stack1来维持添加
    public void appendTail(int value) {
        stack1.add(value);
    }
    //stack2中为顺序
    public int deleteHead() {
        if(!stack2.isEmpty()){
            return stack2.pop();
        }
        if(!stack1.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.add(stack1.pop());
            }
            return stack2.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();
 */

0 赞同 0 条回复

Gg 普通 2022年10月25日下午11:15

class CQueue {

    private Stack<Integer> front;
    private Stack<Integer> end;

    public CQueue() {
        // 分为前栈后栈，前栈负债弹出，后栈负责压入
        front = new Stack<>();
        end = new Stack<>();
    }

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

    public int deleteHead() {
        // 前栈空了，从后栈中取
        if(front.isEmpty()){
            while(!end.isEmpty()){
                front.push(end.pop());
            }
        }
        return front.isEmpty() ? -1:front.pop();
    }
}

0 赞同 0 条回复

yanshuojune 普通 2022年10月25日下午11:06

解题思路：使用栈A用于appendTail函数，deleteHead时，先从A出栈，入栈B后弹出最后一个入栈得value，注意判断B有元素，A为空的特殊情况。
时间复杂度：O（1）
空间复杂度：O（n）

class CQueue:

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


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

    def deleteHead(self) -> int:
        # 若B不为空
        if self.B:
            return self.B.pop()

        # 若A为空
        if not self.A:
            return -1

        # 若A不为空，B为空
        while self.A:
            self.B.append(self.A.pop())
        return self.B.pop()

0 赞同 0 条回复

青木普通 2022年10月25日下午10:43

// 思路很简单，就是一个存，一个取，当取的栈空了把存的栈的所有元素压进去在弹就可以了
// 题解用的Deque，查了下说建议使用Deque代替Stack
// 空间复杂度O(n)
// 时间复杂度O(1)
class CQueue {

    Stack<Integer> s1;
    Stack<Integer> 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();
        }
        while(!s1.empty()){
            s2.push(s1.pop());
        }
        if(s2.empty()){
            return -1;
        }
        return s2.pop();
    }
}

0 赞同 0 条回复

优秀市民普通 2022年10月25日下午10:35

class CQueue:

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

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

    def deleteHead(self) -> int:
        print("stack1:", self.stack1)
        if (self.stack2):
            return self.stack2.pop()
        if (not self.stack1):
            return -1
        while (self.stack1):
            outQueue = self.stack1.pop()
            self.stack2.append(outQueue)
        print("stack2:", self.stack2)
        return self.stack2.pop()

一个栈用作入队，另一个栈用来出队，将入栈的值反转后出栈就是出队

0 赞同 0 条回复

天然普通 2022年10月25日下午10:23

python建立栈和队列太耍赖皮了

class CQueue(object):


    def __init__(self):
        self.lst1,self.lst2 = [],[]

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


    def deleteHead(self):
        """
        :rtype: int
        """
        if self.lst2:
            return self.lst2.pop()
        if not self.lst1:
            return -1
        while self.lst1:
            self.lst2.append(self.lst1.pop())
        return self.lst2.pop()

0 赞同 0 条回复

狗蛋儿普通 2022年10月25日下午10:17

利用标准库栈的特性

开两个栈，一个进，一个出，push到进，pop管出

class MyQueue {
public:
    //首先是创建
    stack<int> stIn;
    stack<int> stOut;
    MyQueue() {

    }

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

    int pop() {
        if(stOut.empty()){
            //从stIn里面导入数据直到为空
            while(!stIn.empty()){
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int res = stOut.top();
        stOut.pop();
        return res;
    }

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

    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

0 赞同 0 条回复

感到自己好渺小普通 2022年10月25日下午10:16

1.思路
用两个栈实现队列
一个栈(stack1)用来模拟在队尾增加元素，一个栈(stack2)用来模拟在队头删除元素
在stack1只用增加元素(压入元素)，删除元素时，首先判断stack2中是否有元素，如果有，那么弹出，如果为空，将stack1中所有元素压入stack2里。
class CQueue {
    private Stack<Integer> stack1;  //注意整数的英文是Integer，而不是Interger 
    private Stack<Integer> stack2;
    public CQueue() {
            this.stack1 = new Stack<>();  //初始化两个栈，利用两个栈实现队列
            this.stack2 = new Stack<>();
    }
    //在stack1中压入(在队尾增加整数)  增加栈
    //在stack2中删除(在队头删除整数)  删除栈
    public void appendTail(int value) {
            stack1.push(value);   //
    }
    public int deleteHead() {
               if(stack2.isEmpty())   //判断删除栈是否为空，如果为空，将stack1中的所有元素压入stack2中
               {                      //如果不为空，进行下一步操作
                   while(!stack1.isEmpty())  //将stack1中所有元素压入stack2中
                   {
                       stack2.push(stack1.pop());
                   }
               }
               if(stack2.isEmpty())  //如果stack2依旧为空，表示队列中没有元素，返回-1
               {
                   return -1;
               }
               else  //如果依旧不为空，在stack2弹出
               {
                   return stack2.pop();
               }
    }
}

/*
    appendTail(int value)  在队列的尾部插入一个整数
    deleteHead()  删除队列头部的元素，并返回删除的元素，如果队列中没有元素的话，返回-1
*/

0 赞同 0 条回复

Error 普通 2022年10月25日下午10:03

class CQueue:

    def __init__(self):
        self.stack = []


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


    def deleteHead(self) -> int:
        if not self.stack:
            return -1
        return self.stack.pop(0)

时间复杂度

0 赞同 0 条回复

鸿渐普通 2022年10月25日下午9:59

class CQueue {
    private Deque<Integer> stack1;
    private Deque<Integer> stack2;
    public CQueue() {
        this.stack1 = new ArrayDeque<>();
        this.stack2 = new ArrayDeque<>();
    }

    public void appendTail(int value) {
        //给栈添加一个元素
        stack1.push(value);
    }

    public int deleteHead() {
        //根据栈的特性，再次放到一个新的栈当中，再把栈顶pop就可以达到效果

        //当队列中的元素都没有的情况下
        if (stack1.isEmpty() && stack2.isEmpty()) {
            return -1;
        }
        //当栈1有元素，但是栈2是空的情况下
        if (stack2.isEmpty()) {
            //将栈1所有的元素加入到栈2 然后输出栈2的顶部
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            //然后返回栈2的顶部
            return stack2.pop();
        } else {
            //当栈2 还有元素的情况下，直接返回栈2的顶部
            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();
 */

0 赞同 0 条回复

T 普通 2022年10月25日下午9:58

下面代码

class CQueue {
    // 定义两个栈
    private LinkedList<Integer> A, B;
    public CQueue() {
        this.A = new LinkedList<>();
        this.B = new LinkedList<>();
    }

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

    // 如果B队列不为空直接弹出，如果A，B同时为空则返回-1。
    // 如果B为空，A不为空。将A全部放进B，再弹出。
    public int deleteHead() {
        if(!B.isEmpty())
            return B.pop();
        if(A.isEmpty())
            return -1;
        while(!A.isEmpty()) {
            B.push(A.pop());
        }
        return B.pop();
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年10月25日下午9:36

栈1用来添加节点，如果需要删除发现栈2为空，把栈1的所有节点出栈入栈到栈2，然后出栈栈2栈顶，如果栈2有元素则出栈栈2栈顶，如果栈1栈2都没有元素返回-1.

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;
    }
}

0 赞同 0 条回复

单个酒窝儿普通 2022年10月25日下午9:29

1、声明两个栈，栈底对栈底放置，在队列尾部添加元素，直接添加到A栈中
2、执行删除队列首部元素，先判断B栈中是否有元素，如果有则弹出B栈的栈顶元素
3、如果B栈中无元素，则在判断A中是否有元素，如果无，则返回-1
4、如果A中有元素，则执行一个循环，将A栈中元素放入B中，循环结束，再弹出B栈顶元素

class CQueue {
public:
    CQueue() {}
    void appendTail(int value) {
        A.push(value);
    }

    int deleteHead() {
        if(!B.empty()){
            int tmp = B.top();
            B.pop();
            return tmp;
        }

        if(A.empty()){
            return -1;
        }

        while(!A.empty()){
            int tmp = A.top();
            A.pop();
            B.push(tmp);
        }
        int tmp = B.top();
        B.pop();
        return tmp;
    }
private:
    stack<int> A;
    stack<int> B;
};

0 赞同 0 条回复

So 普通 2022年10月25日下午8:42

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;
    }
}

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

空间复杂度O(n)

0 赞同 0 条回复

浅夏的无奈普通 2022年10月25日下午8:32

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

class CQueue {
    Deque<Integer> s1;
    Deque<Integer> s2;

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

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

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

0 赞同 0 条回复

Whatever 永久会员 2022年10月25日下午8:01

一个栈用于存放正常顺序的数据，当需要删除队头时，将元素逐个存入另一个栈再删除栈顶；二者均为空时，说明队列为空，另一个栈不为空时，说明当前还存有队头元素。

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

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

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

0 赞同 0 条回复

易水寒永久会员 2022年10月25日下午7:58

两个队列

class CQueue {

        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();

        public CQueue() {

        }

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

        public int deleteHead() {
            transfer();
            if(s2.isEmpty()) {
                return -1;
            }
            return s2.pop();
        }

        private void transfer() {
            if(s2.isEmpty()) {
                while(!s1.isEmpty()) {
                    s2.add(s1.pop());
                }
            }
        }
    }

0 赞同 0 条回复

波波_1936 普通 2022年10月25日下午7:57

 class CQueue {

        //时间复杂度O(n)
        //空间复杂度O(1);
        private Stack<Integer> data;
        private Stack<Integer> temp;

        public CQueue() {
            data = new Stack<>();
            temp = new Stack<>();
        }

        public void appendTail(int value) {
            temp.clear();
            while (!data.isEmpty()) {
                temp.push(data.pop());
            }
            temp.push(value);
            while (!temp.isEmpty()) {
                data.push(temp.pop());
            }
        }

        public int deleteHead() {
            if (data.isEmpty()) {
                return -1;
            }
            return data.pop();

        }
    }

0 赞同 0 条回复

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

共以下 66 个回答

ab两个栈，push时加到a，pop时从b取，如果b为空，就从a取，如果a也空，就返回-1

思路：

利用标准库栈的特性

# 回答此问题取消回复

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

共以下 66 个回答

ab两个栈，push时加到a，pop时从b取，如果b为空，就从a取，如果a也空，就返回-1

思路：

利用标准库栈的特性

# 回答此问题 取消回复

# 回答此问题取消回复