【基本数据结构】剑指 Offer 09. 用两个栈实现队列-跟着帅地玩副业，开拓第二曲线PlayOffer

mpweixin用户永久会员 2023年8月11日下午5:37

class CQueue {
    private Stack s1, s2;

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

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

//每次删除队列头结点都反复移动两个栈中的元素，实现删除栈的底部元素，模仿队列
    public int deleteHead() {
        if(s1.empty()) return -1;

        while(!s1.empty()){
            s2.push(s1.pop());
        }
        int v = (int)s2.pop();
        while(!s2.empty()){
            s1.push(s2.pop());
        }
        return v;
    }
}

/**
 * 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用户普通 2023年8月5日下午12:07

class CQueue {
private:
    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 value=outStack.top();
        outStack.pop();
        return value;
    }
};

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

打

0 赞同 0 条回复

山川湖海普通 2023年8月3日下午8:11

用两个栈实现队列 C++

class CQueue {
public:
    stack<int> s1; // 入
    stack<int> s2; // 出
    CQueue() {
    }

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

    int deleteHead() {
        if (!s2.empty()) {
            int val = s2.top();
            s2.pop();
            return val;
        }
        else if (!s1.empty() && s2.empty()) {
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
            int val = s2.top();
            s2.pop();
            return val;
        }
        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 条回复

hi 普通 2023年7月23日下午10:36

删除操作时把第二个栈当作缓存栈，删除操作完成后，数回到第一个栈

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

    }

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

    int deleteHead() {
        if(stk1.empty()) return -1;

        while(!stk1.empty())
        {
            stk2.push(stk1.top()); 
            stk1.pop();  
        }
        int x = stk2.top();
        stk2.pop();


        while(!stk2.empty()) 
        {
            stk1.push(stk2.top());
            stk2.pop();
        }
        return x;
    }    

};

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

0 赞同 0 条回复

今天没时间刷题普通 2023年7月23日下午1:43

入队：时间复杂度O1
出队：时间复杂度On，空间On
class CQueue {
public:
    CQueue() {

    }

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

    int deleteHead() {
        if(delStack.empty())
        {
            if(addStack.empty())
            {
                return -1;
            }
            while(!addStack.empty())
            {
                delStack.push(addStack.top());
                addStack.pop();
            }
        }
        int value = delStack.top();
        delStack.pop();
        return value;
    }
private:
    stack<int> addStack;
    stack<int> delStack;
};

0 赞同 0 条回复

wowo 普通 2023年7月23日上午12:22

delete: 使用辅助栈，当需要删除队首元素时，将所有元素依次出栈存入辅助栈，辅助栈中的元素就是队列的倒序，pop出栈顶就删除了队列第一个元素。时间复杂度O(n)，空间复杂度O（n)
append: 直接入栈。时间复杂度O(1)

class CQueue:

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


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


    def deleteHead(self) -> int:
        if self.B: 
            return self.B.pop()
        if not self.A: 
            return -1
        if self.A:
            while self.A:
                ele = self.A.pop()
                self.B.append(ele)
            return self.B.pop()

0 赞同 0 条回复

Edenms-u 普通 2023年7月19日下午10:29

typedef struct {
    int* enq;
    int* deq;
    int eqtail;
    int dqtail;
} CQueue;


CQueue* cQueueCreate() {
    CQueue* obj = (CQueue*)malloc(sizeof(CQueue));
    obj->enq = (int*)malloc(sizeof(int) * 10000);
    obj->deq = (int*)malloc(sizeof(int) * 10000);
    obj->eqtail = 0;
    obj->dqtail = 0;
    return obj;
}

void cQueueAppendTail(CQueue* obj, int value) {
    if(!obj) return;
    obj->enq[obj->eqtail++] = value;
}

int cQueueDeleteHead(CQueue* obj) {
    if(!obj) return -1;
    if(obj->dqtail == 0) {
        if(obj->eqtail == 0) {
            return -1;
        } else {
            while(obj->eqtail != 0) {
                obj->deq[obj->dqtail++] = obj->enq[--obj->eqtail];
            }
        }
    }
    return obj->deq[--obj->dqtail];
}

void cQueueFree(CQueue* obj) {
    if(!obj) return;
    free(obj->enq);
    free(obj->deq);
    obj->enq = obj->deq = NULL;
    free(obj);
    obj = NULL;
}

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

 * int param_2 = cQueueDeleteHead(obj);

 * cQueueFree(obj);
*/

c只能用数组当做栈来操作，出队比较繁琐，注意函数的返回值类型是否匹配。
时间复杂度o1 空间复杂度为on

0 赞同 0 条回复

新禾普通 2023年7月16日下午4:49

// 时间复杂度o1 空间复杂度为on
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());
        }
    }
    return stack2.isEmpty() ? -1 : stack2.pop();
}

}

0 赞同 0 条回复

朱志刚普通 2023年7月14日下午11:11

class CQueue {
private:
    stack<int> stack1;
    stack<int> stack2;
public:

    CQueue() {


    }

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

    }

    int deleteHead() {
        if(!stack2.empty())
        {
            int temp=stack2.top();
            stack2.pop();
            return temp;
        }
        if(!stack1.empty())
        {
            while(!stack1.empty())
            {

                stack2.push(stack1.top());
                stack1.pop();
            }
            int temp=stack2.top();
            stack2.pop();
            return temp;


        }
        return -1;

    }
};

0 赞同 0 条回复

Marshan 普通 2023年7月14日上午10:32

class CQueue {
public:
    int flag = 1; //等于1表示栈顺序, 等于0表示队列顺序
    int select_stack = 0;
    stack<int> s0;
    stack<int> s1;
    CQueue() {

    }

    void appendTail(int value) {
        if(flag == 1){
            if(select_stack == 0){
                s0.push(value);
                select_stack = 0;
            }
            else{
                s1.push(value);
                select_stack = 1;
            }
            flag = 1;
        }
        else{
            if(select_stack == 0){
                while(!s0.empty()){
                    s1.push(s0.top());
                    s0.pop();
                }
                s1.push(value);
                select_stack = 1;
            }
            else{
                while(!s1.empty()){
                    s0.push(s1.top());
                    s1.pop();

                }
                s0.push(value);
                select_stack = 0;
            }
            flag = 1;
        }
    }

    int deleteHead() {
        int temp = -1;
        if(flag == 0){
            if(select_stack == 0 && !s0.empty()){
                temp = s0.top();
                s0.pop();
                select_stack = 0;
            }
            else if(select_stack == 1 && !s1.empty()){
                temp = s1.top();
                s1.pop();
                select_stack = 1;
            }
            flag = 0;
        }
        else{
            if(select_stack == 0 && !s0.empty()){
                while(!s0.empty()){
                    s1.push(s0.top());
                    s0.pop();
                }
                temp = s1.top();
                s1.pop();
                select_stack = 1;
            }
            else if(select_stack == 1 && !s1.empty()){
                while(!s1.empty()){
                    s0.push(s1.top());
                    s1.pop();
                }
                temp = s0.top();
                s0.pop();
                select_stack = 0;
            }
            flag = 0;
        }
        return temp;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月13日下午1:42

直接实现即可

class CQueue {
public:
  CQueue() {}

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

  int deleteHead() {
    int tmp;
    if (stack2.empty()) {
      if (stack1.empty()) {
        return -1;
      } else {
        while (!stack1.empty()) {
         tmp= stack1.back();
         stack1.pop_back();
         stack2.push_back(tmp);
        }
      }
    }
    tmp = stack2.back();
    stack2.pop_back();
    return tmp;
  }

private:
  vector<int> stack1, stack2;
};

0 赞同 0 条回复

Fighting boy😀 普通 2023年7月12日下午10:32

// C++
class CQueue {
public:
CQueue() {

}
// stack1数据入栈
void appendTail(int value) {
    stack1.push(value);
}

int deleteHead() {
    if (!stack2.empty()) {
        int res = stack2.top();
        stack2.pop();

        return res;
    }
// 如果stack1不空;
    if (!stack1.empty()) {
        // 如果stack2空
        while(!stack1.empty()) {
            // 将stack1中的元素从栈顶依次取出，并存入stack2
            stack2.push(stack1.top());
            stack1.pop();
        }

        int res = stack2.top();
        stack2.pop();
        return res;
    }

    return -1;
}

private:
stack stack1;
stack stack2;
};

0 赞同 0 条回复

北辰普通 2023年7月12日下午5:32

class CQueue {

    public static Stack s1;
    public static Stack s2;

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

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

    public int deleteHead() {
        //在删除之前先将栈s1的元素加入到栈s2中
        while(!s1.isEmpty()) {
            s2.add(s1.pop());
        }
        if(s2.isEmpty()) {
            return -1;
        }else {
            int res = (int) s2.pop();
            //将剩余元素从s2加入到s1
            while(!s2.isEmpty()) {
                s1.add(s2.pop());
            }
            return res;
        }
    }
}

时间复杂度：O（n）
空间复杂度：O(n)

0 赞同 0 条回复

NullPointerException 普通 2023年7月12日下午5:15

//两个栈一个只进一个只出当出栈空了，入栈全部都进入出栈
Stack in ;
Stack out ;
public CQueue() {
in =new Stack();
out =new Stack();
}

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

public int deleteHead() {
    if(in.size()==0&&out.size()==0)
    {
        return -1;
    }
    if(out.size()!=0)
  {
      return out.pop();
  }else
  {
      while(in.size()!=0)
      {
          out.push(in.pop());
      }
      return  out.pop();
  }

}

}

0 赞同 0 条回复

达浪达浪普通 2023年7月12日下午3:17

简化版本
class CQueue {
public:
    stack<int> s1;
    stack<int> s2;
    CQueue() {

    }

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

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

0 赞同 0 条回复

momo 普通 2023年7月12日下午3:17

用两个栈实现队列

class CQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

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

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

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

0 赞同 0 条回复

#00456B 普通 2023年7月12日下午2:35

class CQueue {
public:
    stack<int> stkIn,stkOut;
    CQueue() {

    }

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

    int deleteHead() {
        //如果输出栈为空的话，就先把输入栈的元素全部放到输出栈中
        if(stkOut.empty()){
            if(stkIn.empty()){
                return -1;
            }
            else{
                while(!stkIn.empty()){
                    stkOut.push(stkIn.top());
                    stkIn.pop();
                }
            }
        }
        //此时输出栈已经不为空了，因为如果为空在上面就已经输出-1
        //记录栈顶元素，将其弹出
        int ans = stkOut.top();
        stkOut.pop();
        return ans;
    }
};

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

0 赞同 0 条回复

枫梓。普通 2023年7月12日上午11:14

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()) {
                int temp = inStack.top();
                inStack.pop();
                outStack.push(temp);
            }
        }
        int val = outStack.top();
        outStack.pop();
        return val;
    }
};

一个输入栈一个输出栈。

0 赞同 0 条回复

远行客普通 2023年7月12日上午12:12

class CQueue:
    def __init__(self):
        # 使用两个栈实现栈内元素倒叙
        self.stack_1 = []
        self.stack_2 = []

    def appendTail(self, value):
        # 用找1实现加入队尾操作
        self.stack_1.append(value)

    def deleteHead(self):
        # 删除队首元素

        # 使用栈2实现删除栈1栈底元素
        # 也就是删除队尾元素
        if self.stack_2:
            # 栈2不为空， 则直接返回栈顶元素
            return self.stack_2.pop()

        # 当栈1为空， 表示两个栈都为空， 返回-1
        if not self.stack_1:
            return -1

        while self.stack_1:
            # 将栈1元素全部倒入栈2， 实现元素倒叙
            self.stack_2.append(self.stack_1.pop())

        # 返回栈2栈顶元素
        return self.stack_2.pop()

"""
时间复杂度：O(N)
空间复杂度：O(N)
"""

0 赞同 0 条回复

周小二普通 2023年7月11日下午11:35

打卡

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

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

    public int deleteHead() {
        if (!B.isEmpty()) {
            return B.pop();
        }
        if (A.isEmpty()) {
            return -1;
        }
        while (!A.isEmpty()) {
            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 条回复

今天你刷题了嘛普通 2023年7月11日下午10:57

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

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

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

    public int deleteHead() {
        if(stack2.size()!=0){
            return stack2.removeLast();
        } else{
            while(stack1.size()!=0){
                // 都移到另一个栈
                stack2.addLast(stack1.removeLast());
            }
            if(stack2.size()!=0){
                return stack2.removeLast();
            } 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();
 */

时间复杂度：O（n）
空间复杂度：O（n）

0 赞同 0 条回复

人生何处不青山普通 2023年7月11日下午10:52

估计也就我用TS写了

class CQueue {
    public stackA: number[]
    public stackB: number[]
    constructor() {
        this.stackA = [];
        this.stackB = [];
    }

    appendTail(value: number): void {
        this.stackA.push(value);
    }

    deleteHead(): number {
        if (this.stackB.length) {
            return this.stackB.pop();
        } else {
            while (this.stackA.length) {
                this.stackB.push(this.stackA.pop());
            }
        }
        return this.stackB.length ? this.stackB.pop() : -1;
    }
}

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

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月11日下午10:04

代码如下

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

艺普通 2023年7月11日下午9:50

“`c++
class CQueue {
public:
stack s1;
stack s2;
CQueue() {

}

void appendTail(int value) {

s1.push(value);
}

int deleteHead() {

int t=-1;
if(!s2.empty())
{
t=s2.top();
s2.pop();
return t;
}
if(!s1.empty())
{
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
t=s2.top();
s2.pop();
return t;
}
return -1;
}
};
//空间复杂度：O(n)
//时间复杂度：O(n)

0 赞同 0 条回复

普通 2023年7月11日下午9:01

c++ 代码
class CQueue {
private:
stack 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 value = outStack.top();
    outStack.pop();
    return value;
}

};

0 赞同 0 条回复

mpweixin用户普通 2023年7月11日下午4:02

class CQueue {
    //["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
    //[[],[3],[],[],[]]
    //输出：[null,null,3,-1,-1]
    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()) {
            return out.pop();
        } else if (out.isEmpty()&&!in.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
            return out.pop();
        } else {
            return -1;
        }
    }
}

0 赞同 0 条回复

doordie. 普通 2023年7月11日下午2:06

两个栈实现队列

第一个栈负责入
第二个栈负责出实现队列操作

public class CQueue {
    LinkedList<Integer> A;
    LinkedList<Integer> 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 条回复

坏掉的世界永久会员 2023年7月11日下午1:17

代码

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

    }

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

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

        return -1;
    }
};

0 赞同 0 条回复

小季同学普通 2023年7月11日下午1:12

用两个栈来实现队列

class CQueue {
    private static1: number[] = []
    private static2: number[] = []
    constructor(value: number) {
    }

    appendTail(value: number): void {
        this.static1.push(value)
    }

    deleteHead(): number {
        // stack1清空插入stack2，并删除stack2第一个元素
        if(this.static2.length > 0) {
            return this.static2.pop()
        }else if(this.static1.length > 0) {
            while(this.static1.length) {
                const result = this.static1.pop()
                this.static2.push(result)
            }
            return this.static2.pop()
        }else {
            return -1
        }   
    }
}

0 赞同 0 条回复

ppopp 普通 2023年7月11日上午12:18

第四天
class CQueue {
private:
stack instk, outstk;

void in2out(){
    while(!instk.empty()){
        outstk.push(instk.top());
        instk.pop();
    }
}

public:
CQueue() {

}

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

int deleteHead() {
    if (outstk.empty()) {
        if (instk.empty()) {
            return -1;
        }
        in2out();
    }
    int value = outstk.top();
    outstk.pop();
    return value;
}

};

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月10日下午11:51

Day4：下面是代码

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

Terence💧 普通 2023年7月10日下午11:19

type CQueue struct {
    inStack  []int
    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 {
            return -1
        }
        this.in2out()
    }
    val := this.outStack[len(this.outStack) - 1]
    this.outStack = this.outStack[:len(this.outStack) - 1]
    return val
}

func (this *CQueue) in2out() {
    for len(this.inStack) > 0 {
        this.outStack = append(this.outStack, this.inStack[len(this.inStack) - 1])
        this.inStack = this.inStack[:len(this.inStack) - 1]
    }
}

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

插入时间复杂度O1

0 赞同 0 条回复

神经蛙普通 2023年7月10日下午11:09

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

class CQueue {

    LinkedList<Integer> stack1, stack2;

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

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

    public int deleteHead() {
        if (!stack2.isEmpty()) {
            return stack2.removeLast();
        }

        if (stack1.isEmpty()) {
            return -1;
        }

        while(!stack1.isEmpty()) {
            stack2.addLast(stack1.removeLast());
        }

        return stack2.removeLast();

    }
}

0 赞同 0 条回复

白鹿普通 2023年7月10日下午11:03

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

}

void appendTail(int value) {
    if (left.size() == 0 && right.size() != 0) {
        while (right.size() != 0) {
            int tmp = right.top();
            right.pop();
            left.push(tmp);
        }
    }

    left.push(value);
}

int deleteHead() {
    if (left.size() == 0 && right.size() == 0) return -1;

    while (left.size() != 0) {
        int tmp = left.top();
        left.pop();
        right.push(tmp);
    }

    int tmp = right.top();
    right.pop();
    return tmp;
}

private:
std::stack left;
std::stack right;
};

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

0 赞同 0 条回复

CKX 普通 2023年7月10日下午10:53

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 {
            return -1
        }
        //将inStack元素出栈到outStack中
        for len(this.inStack) > 0 {
            this.outStack = append(this.outStack, this.inStack[len(this.inStack) - 1])
            this.inStack = this.inStack[:len(this.inStack) - 1]
        }
    }
    //outStack进行出队操作
    value := this.outStack[len(this.outStack) - 1]
    this.outStack = this.outStack[:len(this.outStack) - 1]
    return value
}


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

时间O(1)
空间O(n)

0 赞同 0 条回复

片言莫语普通 2023年7月10日下午10:15

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

    public void appendTail(int value) { //进队列
        stack1.push(value); // 将元素value压入栈stack1，实现队列的元素添加功能
    }

    public int deleteHead() {   //出队列
        if(!stack2.isEmpty()){
           return stack2.pop();
        }
       if(!stack1.isEmpty()){   //定义一个名为deleteHead的函数，用来从队列中删除并返回头部元素 if(!stack1.isEmpty())用来判断stack1是否为空，是为了防止在stack1为空的时候做无效的操作
            while(!stack1.isEmpty()){   //while(!stack1.isEmpty())则用来确保将stack1中的所有元素都转移到stack2
                stack2.push(stack1.pop()); // 则将stack1的元素取出并压入stack2，这样就可以实现后进先出的队列特性
            }
            return stack2.pop();
        }
        return -1;  // 若队列中没有元素，deleteHead 操作返回 -1
    }

}

0 赞同 0 条回复

June 普通 2023年7月10日下午9:59

class CQueue {

    public Stack<Integer> st1;
    public Stack<Integer> st2;

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

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

    public int deleteHead() {
        int ans = -1;
        while(!st1.empty())
        {
            int tmp = st1.peek();
            st2.push(tmp);
            st1.pop();
        }
        //全部弹出，逆序
        if(!st2.empty()){
            ans = st2.peek();
            st2.pop();
        }
        while(!st2.empty())
        {
            int tmp = st2.peek();
            st2.pop();
            st1.push(tmp);
        }
        return ans;
    }
}

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

0 赞同 0 条回复

H、普通 2023年7月10日下午9:49

两个栈实现队列

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() {

        if(stackOut.empty()){
            if(stackIn.isEmpty()){
                return -1;
            }
            while (!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
            }
        }

        return stackOut.pop();
    }
}

0 赞同 0 条回复

Luminous 普通 2023年7月10日下午9:39

class CQueue {

    private Deque<Integer> inStack;
    private Deque<Integer> outStack; 
    //构造函数
    public CQueue() {
        inStack=new ArrayDeque<Integer>();
        outStack=new ArrayDeque<Integer>();
    }
    //尾部插入整数
    public void appendTail(int value) {
        inStack.push(value);
    }
    //首部删除元素
    public int deleteHead() {
        //1.outStack为空
        if(outStack.isEmpty()){
        //1.1 inStack 也为空则直接返回-1
            if(inStack.isEmpty()) return -1;
        //1.2 inStack不为空则将inStack的元素全部压入outStack中
            inOut();
        //2.返回outStack中的栈顶元素
        }
       return outStack.pop();
    }
    public void inOut(){
        while(!inStack.isEmpty()){
            outStack.push(inStack.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 条回复

阿尚普通 2023年7月10日下午8:29

class CQueue {

    private Stack<Integer> stackIn;
    private Stack<Integer> stackOut;

    public CQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    //入栈
    public void appendTail(int value) {
        stackIn.push(value);
    }
    //出栈
    public int deleteHead() {
        if(stackIn.isEmpty() && stackOut.isEmpty()) return -1;
        if(stackOut.isEmpty()){
            while(!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
            }
        }

        return stackOut.pop();
    }
}

0 赞同 0 条回复

CaCO3 永久会员 2023年7月10日下午7:24

”’java
class CQueue {
LinkedList stack1;
LinkedList stack2;
public CQueue() {
stack1 = new LinkedList<>();
stack2 = new LinkedList<>();
}

public void appendTail(int value) {
    //在队列尾部添加元素
    stack1.push(value);
}

public int deleteHead() {
    //删除头部结点
    if(stack2.isEmpty()){
        if(stack1.isEmpty()){
            return -1;
        }
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }

    }
    return stack2.pop();

}

}
”’

0 赞同 0 条回复

mpweixin用户普通 2023年7月10日下午7:12

剑指 Offer 09. 用两个栈实现队列

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();
 */

1 赞同 0 条回复

Mooby 普通 2023年7月10日下午5:27

四
class CQueue {
Stack stack1;
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();
    }
    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();
*/

0 赞同 0 条回复

V2ero 普通 2023年7月10日下午4:55

先来点简单题

class Stack {
    private arr: number[]

    constructor(){
        this.arr = []
    }

    isEmpty(){
        return this.arr.length === 0;
    }

    in(val: number){
        this.arr.push(val)
    }

    out(){
        const val = this.arr.pop()
        return val;
    }
}

class CQueue {
    inStack : Stack;
    outStack : Stack

    constructor() {
        this.inStack = new Stack();
        this.outStack = new Stack();
    }

    appendTail(value: number): void {
        this.inStack.in(value)
    }

    deleteHead(): number {
        if(this.outStack.isEmpty()){
            while(!this.inStack.isEmpty()){
                this.outStack.in(this.inStack.out())
            }
        }
        return this.outStack.out()?? -1       
    }
}

0 赞同 0 条回复

波雅汉库克普通 2023年7月10日下午3:50

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

    }

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

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

append 操作：O(1)
deleteHead操作： O(n)

0 赞同 0 条回复

桎梏普通 2023年7月10日下午3:20

class CQueue {

    Stack<Integer> stakcIn;
    Stack<Integer> stakcOut;

    public CQueue() {
        stakcIn = new Stack<>();
        stakcOut = new Stack<>();
    }

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

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

出队时若出队栈不为空直接弹出否则将入队栈压入出队栈

0 赞同 0 条回复

AD钙奶普通 2023年7月10日下午3:08

class CQueue {
    // A 作为 添加队尾元素的队列， B 作为 将元素倒序的队列
    Deque<Integer> A,B;
    public CQueue() {
        A = new ArrayDeque<>();
        B = new ArrayDeque<>();
    }

    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(n)
空间复杂度:O(n)

0 赞同 0 条回复

ONE PIECE 普通 2023年7月10日下午2:21

<pre><code class="language-java line-numbers">class CQueue {
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    public CQueue() {

    }

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

    public int deleteHead() {
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        int res = stack2.isEmpty()?-1:stack2.pop();
        while(!stack2.isEmpty()){
            stack1.push(stack2.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();
 */
</code></pre>

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

0 赞同 0 条回复

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

共以下 48 个回答

两个栈实现队列

# 回答此问题取消回复

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

共以下 48 个回答

两个栈实现队列

# 回答此问题 取消回复

# 回答此问题取消回复