Deckkker 普通 2024年4月27日下午4:24

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)。

0 赞同 0 条回复

山月普通 2024年3月15日下午3:16

//用两个栈实现一个队列，in栈负责队列的push,out栈负责队列的pop(),关键在于两个点(1)判断Out栈是否为空if，若为空移动in中所有元素至out（2）In栈中的元素必须作为一个整体一起移动至out栈while，这两个关键点理解，还需要加强记忆
class CQueue {
public:
stack in;
stack out;
CQueue() {

}

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

}

int deleteHead() {

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

0 赞同 0 条回复

YOLO 普通 2024年3月13日上午10:23

/*用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，
分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -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 条回复

雨落星空普通 2024年3月11日下午8:01

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

0 赞同 0 条回复

一颗红豆普通 2024年3月10日下午4:28

时间复杂度O（n），空间复杂度O（1）
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;
};

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

0 赞同 0 条回复

e=mc² 普通 2024年3月9日下午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;
    }
}

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

0 赞同 0 条回复

零普通 2024年3月8日下午3:58

思路：直接使用队列


// 队列
class CQueue {
    Queue queue;
    public CQueue() {
        queue = new LinkedList<>();
    }


    public void appendTail(int value) {
        queue.offer(value);
   }

   public int deleteHead() {
       Integer num = queue.poll();
       return null == num ? -1 : num;
    }
}
//双栈
class CQueue {
    Stack stack1,stack2;
    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        if (stack2.empty()) {
            while(!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.empty() ? -1 : stack2.pop();
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年3月8日上午10:51

push方法时间复杂度O(1),空间复杂度O(1)
pop()方法时间复杂度O(N),空间复杂度O(1)
class CQueue {
public:
stackst1;
stackst2;
CQueue() {

}

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

int deleteHead() {
    if(st1.empty()){
        return -1;
    }
    while(!st1.empty()){
        st2.push(st1.top());
        st1.pop();
    }
    int val=st2.top();
    st2.pop();
    while(!st2.empty()){
        st1.push(st2.top());
        st2.pop();
    }
    return val;
}
void push(int value){
    st1.push(value);
}
int pop(){
    if(st1.empty()){
        return -1;
    }
    while(!st1.empty()){
        st2.push(st1.top());
        st1.pop();
    }
    int val=st2.top();
    st2.pop();
    while(!st2.empty()){
        st1.push(st1.top());
        st2.pop();
    }
    return val;
}

};

0 赞同 0 条回复

小耿普通 2024年3月8日上午10:00

“`C++
class CQueue {
public:
stack< int > stack1;
stack< int > stack2;
CQueue() {
// stack1 = new stack();
// stack2 = new stack();
}

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

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

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

    return -1;
}

};

“`C++
使用两个堆栈实现队列

0 赞同 0 条回复

Yeah~ 普通 2024年3月8日上午1:48

class CQueue {
public:
stack qIn;
stack qOut;
CQueue() {

}

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

}

int deleteHead() {
    if(!qOut.empty()){
        int ret = qOut.top();
        qOut.pop();
        return ret;
    }//重要
    while(!qIn.empty()){
        int tmp = qIn.top();
        qIn.pop();
        qOut.push(tmp); 
    }

if(!qOut.empty()){
    int ret = qOut.top();
    qOut.pop();
    return ret;
}else return -1;

}


};

出口栈若有则直接出，若没有再把入口栈搬过来

0 赞同 0 条回复

！。！普通 2024年3月8日上午12:37

”’java
class CQueue {
public:
stack stack1;
stack stack2;
CQueue() {

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

};
”’
时间复杂度O(n) 空间复杂度O(n)

0 赞同 0 条回复

墨丘俐普通 2024年3月7日下午5:04

class CQueue {
Stack stackin;
Stack stackout;

public CQueue() {
    stackin = new Stack<>();
    stackout = new Stack<>();

}

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

}

public int deleteHead() {
    if(stackout.isEmpty()){
        if(stackin.isEmpty()){
            return -1;

        }else{
            while(!stackin.isEmpty()){
            stackout.push(stackin.pop());
        }

        }


    }

    return stackout.pop();



}

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

0 赞同 0 条回复

Let it be 永久会员 2024年3月6日下午11:29

class CQueue {
Stack A;
Stack 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()){
        return -1;
    }
    while(!A.isEmpty()){
        B.push(A.pop());
    }
    return B.pop();
}

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

0 赞同 0 条回复

晚风、普通 2024年3月6日下午10:34

class CQueue:

def __init__(self):
    self.A,self.B = [],[]
    #A用来表示还书
    #B来表示借书

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

def deleteHead(self) -> int:
    if self.B:
        return self.B.pop()
    #查看B内是否有内容，如果有则直接借出去
    if not self.A: 
        return -1
    #查看A内是否是空的，如果A也是空的 

    #如果A不是空的
    while self.A:
        self.B.append(self.A.pop())
    return self.B.pop()

思路：两个列表，分别表示输入栈，和输出栈
输入栈用来还书
输出栈用来借书
借书时先看看输出栈还有书在没，如果没有将输入栈内的书全部放在输出栈内，后还的书先放进输出栈内，整体实现先还先出
时间复杂度：o(n)
空间复杂度：o(n)

0 赞同 0 条回复

30tcq 普通 2024年3月6日下午5:37

思路：借还规律符合队列，两个书架符合栈的特征，所以要用两个栈来模拟，实现队列
class CQueue {
public:
stack in;
stack out;
CQueue() {
}

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

int deleteHead() {     //把in里面除最后一个元素外的所有元素倒到out中，再倒回来
    if(in.empty()) return -1;
    while(!in.empty()){
        out.push(in.top());
        in.pop();
    }
    int val = out.top();
    out.pop();
    while(!out.empty()){
        in.push(out.top());
        out.pop();
    }
    return val;
}

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

0 赞同 0 条回复

南梁陈庆之普通 2024年3月6日下午5:09

修改为两个栈，栈A做录入，栈B做导出；
因为栈是先进后出，做两次栈保存操作后，最先进的值在第二个栈肯定先出
所以栈B中如果有值的话，直接取值就是最新录入的值。如果栈B为空，则从栈A中做次同步值。
如果栈A、栈B都空情况，此时返回-1

class CQueue {
Stack stackA, stackB;
public CQueue() {
stackA = new Stack<>();
stackB = new Stack<>();
}

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

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

湘江小水鬼普通 2024年3月6日上午10:53

typedef struct {
// 参数类似形参，只能定义，不能赋值
int stack1[500];
int top1;
int stack2[500];
int top2;
} CQueue;

CQueue* cQueueCreate() {
CQueue *obj = malloc(sizeof(CQueue));
obj->top1 = -1;
obj->top2 = -1;
return obj;
}

void cQueueAppendTail(CQueue* obj, int value) {
obj->stack1[++obj->top1] = value;
}

int cQueueDeleteHead(CQueue* obj) {
if (obj->top2 -1 && obj->top1 -1) {
return -1;
} else if (obj->top2 -1) {
while (obj->top1 > 0) { // 留stack1中最后一个元素，直接出栈，不用入栈stack2后再出栈
obj->stack2[++obj->top2] = obj->stack1[obj->top1–];
}
return obj->stack1[obj->top1–];
} else {
return obj->stack2[obj->top2–];
}
}

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

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月6日上午9:20

class CQueue {
public:
    CQueue() {

    }

    void appendTail(int value) {
        stk1.push(value);
    }
    // stk2的栈顶自下，就是队列头
    // stk1就是正常入栈
    // 当stk2出栈栈空后，就把stk1倒序入stk2，重新从stk2出栈
    int deleteHead() {
        if(!stk2.empty()) {
            int res = stk2.top(); stk2.pop();
            return res;
        }
        if(stk1.empty()) return -1;
        while(!stk1.empty()) {
            stk2.push(stk1.top()); stk1.pop();
        }
        int res = stk2.top(); stk2.pop();
        return res;
    }
private:
    stack<int> stk1;
    stack<int> stk2;
};

0 赞同 0 条回复

神经蛙普通 2024年3月5日下午11:45

class CQueue {
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;

}

private:
stack inStack, outStack;
void in2out()
{
while(!inStack.empty())
{
outStack.push(inStack.top());
inStack.pop();
}
}
};
入队的时间复杂度是O(1);出队的时间复杂度是O(n)；空间复杂度是O(n)

0 赞同 0 条回复

mpweixin用户普通 2024年3月5日下午9:32

java
class CQueue {
LinkedListA,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;
    while(!A.isEmpty())
        B.addLast(A.removeLast());
        return B.removeLast();
}

}
提交

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月5日下午8:44

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的条件
        if(!stack2.isEmpty()){
            return stack2.pop();
        }

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

            return stack2.pop();
        }

        return -1;

    }
}

0 赞同 0 条回复

普通 2024年3月5日下午8:34

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

叫不醒装睡的人普通 2024年3月5日下午8: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) （当第二个链表中包含元素时，此时为 O(1)；当第一个链表不为空第二个链表为空时，此时为 O(n)）
    // 空间复杂度为 O(n)
}

0 赞同 0 条回复

Jimmy 普通 2024年3月5日下午7:55

appendTail时间复杂度O(1)，deleteHead时间复杂度O(n)，空间复杂度O(n)

class CQueue {
public:
    CQueue() {

    }

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

    int deleteHead() {
        if(!output.empty()){
            int ans = output.top();
            output.pop();
            return ans;
        }
        if(!input.empty()){
            while(!input.empty()){
                int temp = input.top();
                input.pop();
                output.push(temp);
            }
            int ans = output.top();
            output.pop();
            return ans;
        }

        return -1;
    }
private:
    stack<int> input;// 同于入栈
    stack<int> output;// input的元素被倒序存储到output中，用于实现出栈
};

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

0 赞同 0 条回复

NULL 普通 2024年3月5日下午6:40

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() {
    dumpStackIn();
    if(stackOut.isEmpty())return -1;
    return stackOut.pop();
}

public void dumpStackIn(){
    if(!stackOut.isEmpty())return;
    while(!stackIn.isEmpty()){
        stackOut.push(stackIn.pop());
    }
    return;
}

}

0 赞同 0 条回复

持之以恒:-) 普通 2024年3月5日下午3:15

利用两个栈实现FIFO

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

解题思路：

使用两个栈stackin and stackout
in 栈负责接收数据
out栈负责输出数据
当数据输入的时候要保证数据全部在in栈里
使用while(!stackout.empty())将out栈全部转移到in栈中输入
当数据输出的时候要保证数据全部在out栈里
使用while(!stackin.empty()) 将in栈全部转移到out栈中输出

class CQueue {
    private Stack stackin = new Stack();
    private Stack stackout = new Stack();
    // 0时在输入数据  
    public CQueue() {

    }
    // 向队列中插入元素
    public void appendTail(int value) {

        // 向stackIn中插入数据
        while(!stackout.empty())
            stackin.push(stackout.pop());
        stackin.push(value);
    }

    // 向队列中删除元素
    public int deleteHead() {
        // 从out栈中删除元素
        while(!stackin.empty())
            stackout.push(stackin.pop());
        if(stackout.empty())
            return -1;
        return (Integer) stackout.pop();
    }
}

0 赞同 0 条回复

Raphtalia. 普通 2024年3月5日下午2:58

class CQueue {
public:
stack s1;
stack s2;
CQueue() {

}

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

int deleteHead() {
    if(s1.empty()) return -1;
    while(!s1.empty()) {
        s2.push(s1.top());
        s1.pop();
    }
    int ans = s2.top();
    s2.pop();
    while(!s2.empty()) {
        s1.push(s2.top());
        s2.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();
*/
时间复杂度O（n）

0 赞同 0 条回复

ChenZhangHangTime 永久会员 2024年3月5日下午2:41

用两个栈实现队列的入队出队操作
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 条回复

Jankin 普通 2024年3月5日下午2:39

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

时间复杂度：appendTail 方法为 O(1)，deleteHead 方法在最坏情况下为 O(n)
空间复杂度：O(n)

0 赞同 0 条回复

=.= 普通 2024年3月5日下午2:08

class CQueue {
Deque st1;
Deque st2;

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

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

public int deleteHead() {
    if(st1.isEmpty() && st2.isEmpty()) return -1;
    if(st2.isEmpty()){
        while(!st1.isEmpty()){
            st2.addLast(st1.removeLast());
        }
    }
    return st2.removeLast();
}

}

/**
* 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年3月5日下午2:03

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.isEmpty())
    {
       return s2.pop();
    }else{
        while (!s1.isEmpty())
        {
            s2.push(s1.pop());
        }
        return s2.isEmpty()?-1:s2.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 条回复

kfaebot 普通 2024年3月5日上午11:27

class CQueue {
public:
    //还书的栈，最晚还的书在栈顶
    stack<int>receive_stack;
    //倒书的栈，最晚还的书放到栈底
    stack<int>reverse_stack;

    CQueue() {

    }

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

    int deleteHead() {
        //倒书
        //如果装倒书的栈一开始就有书
        if(!reverse_stack.empty()){
            int tmp;
            tmp=reverse_stack.top();
            reverse_stack.pop();
            return tmp;
        }

        //如果一开始就没有新的书可以倒
        if(receive_stack.empty()){
            return -1;
        }

        //正常倒书
        while(!receive_stack.empty()){
            int tmp;
            tmp=receive_stack.top();
            reverse_stack.push(tmp);
            receive_stack.pop();
        }
        int tmp=reverse_stack.top();
        reverse_stack.pop();
        return tmp;
    }
};

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

0 赞同 0 条回复

Monou 普通 2024年3月5日上午11:20

栈实现队列
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()){
       while(!stack1.isEmpty()){
           stack2.push(stack1.pop());
       } 
    }
    return stack2.isEmpty() ? -1 : 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 条回复

神经蛙普通 2024年3月5日上午10:44

class CQueue {
    Stack<Integer> sa;
    Stack<Integer> sb;

    public CQueue() {
        sa = new Stack<>();
        sb = new Stack<>();

    }

    public void appendTail(int value) {
        sa.addLast(value);

    }

    public int deleteHead() {
        if(!sb.isEmpty()){
            return sb.pop();
        }
        // 少了一步判断
        if(sa.isEmpty()) return -1;
        while(!sa.isEmpty()){
            sb.push(sa.pop());
        }
        return sb.pop();

    }
}

0 赞同 0 条回复

紫芝普通 2024年3月5日上午10:28

思路：定义两个栈sin, sout; 插入时直接使用sin.push(x), 输出时判断：如果sin和sout都空，说明没有元素，返回-1；如果sout不空，则直接输出sout.top(), 如果sout空，则将sin的值插入到sout，然后输出sout栈顶元素。

“`c++
class CQueue {
private:
stack sIn, sOut;
public:
CQueue() {

}

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

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

};

“`

0 赞同 0 条回复

😴 普通 2024年3月5日上午10:23

class CQueue {
LinkedList A,B;
public CQueue() {
//两个链表，类似两个栈
A = new LinkedList();
B = new LinkedList();

}
//给栈A压入元素
public void appendTail(int value) {
    A.addLast(value);

}
//删除头结点元素
public int deleteHead() {
    if(!B.isEmpty()) return B.removeLast();//判断B是否为空，不为空删除最末尾的结点
    if(A.isEmpty()) return -1;//如果A为空，说明没有内容
    //如果A不为空，将栈A的元素逆序，调入栈B
    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();
*/
刚开始题目没看懂，后面看了精选回答才理解，然后java有许多自带的可以用的方法不太熟练掌握
时间复杂度O(1)
空间复杂度O(n)

0 赞同 0 条回复

mpweixin用户普通 2024年3月5日上午10:22

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;
    while(!A.isEmpty()){
        B.addLast(A.removeLast());
    }
    return B.removeLast();
}

思路：一个做入栈队，一个做出栈队

0 赞同 0 条回复

Yuki 永久会员 2024年3月5日上午9:34

打卡
https://leetcode.cn/problems/implement-queue-using-stacks/solutions/2668124/zhan-mo-ni-dui-lie-by-yukislab-31e6

0 赞同 0 条回复

Free 普通 2024年3月5日上午8:36

class CQueue {
public:
    CQueue() 
    {}

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

    int deleteHead() 
    {
        int n = main.size();
        if(n == 0)
            return -1;
        for(int i = 0; i < n - 1; i++)
        {
            tmp.push(main.top());
            main.pop();
        }
        int res = main.top();
        main.pop();
        while(!tmp.empty())
        {
            main.push(tmp.top());
            tmp.pop();
        }
        return res;
    }

private:
    stack<int> main;
    stack<int> tmp;
};

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

莫～慢～待普通 2024年3月4日下午11:43

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(stack1.empty()&&stack2.empty())
return -1;
if(stack2.empty())
{
    while(!stack1.empty())
    {
        int top=stack1.pop();
        stack2.push(top);
    }
}
int res=stack2.pop();
return res;
}

}
利用两个栈的先进后出，完成队列的先进先出功能

0 赞同 0 条回复

HU 普通 2024年3月4日下午11:30

var CQueue = function() {
    // 定义两个栈元素
    this.stack1 = [];
    this.stack2 = [];
};

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

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    // 出队
    // 如果栈2有元素，先出队
    if(this.stack2.length != 0) {
        return this.stack2.pop();
    }

    // 如果栈2没有元素
    // 如果栈1有元素，把栈1元素都放进栈2
    if(this.stack1.length != 0) {
        while(this.stack1.length != 0) {
            this.stack2.push(this.stack1.pop());
        }

        return this.stack2.pop();
    }

    // 如果栈1和栈2都没有元素
    return -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 条回复

MARS 普通 2024年3月4日下午11:26

day4第一题

var CQueue = function() {
  this.in=[]
  this.out=[]
};

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

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    if(this.out.length==0){
        if(this.in.length==0){
            return -1
        }else{
            while(this.in.length!=0){
                this.out.push(this.in.pop())
            }
        }
    }
     return this.out.pop()
};

0 赞同 0 条回复

Laboratory 普通 2024年3月4日下午11:00

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() {
        // 若B不为空
        if(!stack2.isEmpty()) {
            return stack2.pop();
        }
        if(stack1.isEmpty()) {
            return -1;
        }
        while(!stack1.isEmpty()) {
            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();
 */

0 赞同 0 条回复

方铎码农普通 2024年3月4日下午10:51

出队列时时间复杂度$O(n)$

//本质上是用两个栈实现一个队列，A栈全部推入B栈就是栈的倒序
class CQueue {

    LinkedList<Integer> stack1;
    LinkedList<Integer> stack2;

    public CQueue() {
        this.stack1 = new LinkedList<Integer>();
        this.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();
    }
}

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

0 赞同 0 条回复

heathhou 普通 2024年3月4日下午10:08

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

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

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

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

        return -1;
    }
};

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

0 赞同 0 条回复

机电皮怪永久会员 2024年3月4日下午9:36

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

##C++

class CQueue {
private:
    stack<int> instack, outstack;


<pre><code>//检查出栈是否为空
bool headisempty()
{
    if(outstack.empty() == true)
    {
        return true;
    }
    else
    {
        return false;
    }
}
</code></pre>

public:
    CQueue() {
    }

<pre><code>void appendTail(int value) {
    instack.push(value);
}

int deleteHead() {
    //出栈为空则将全部的入栈元素弹出并进入出栈
    if (headisempty())
    {
        if(instack.empty() == true)
        {
            return -1;
        }
        while(instack.empty() == false)
        {
            int temp = instack.top();
            outstack.push(temp);
            instack.pop();
        }
    }

    int res = outstack.top();
    outstack.pop();
    return res;
}
</code></pre>

};

0 赞同 0 条回复

　南木普通 2024年3月4日下午9:25

时间：O（n）空间O（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;
    }
}

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

0 赞同 0 条回复

helloMoon 普通 2024年3月4日下午8:56

两个栈实现队列java

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

0 赞同 0 条回复

言之命至普通 2024年3月4日下午8:55

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();//stack2有数据，直接弹出
        }

        if(!stack1.isEmpty()){//stack2没有数据，把stack1数据放进来，弹出
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }

            return stack2.pop();
        }

        return -1;//stack1、stack2都没有数据，弹出-1

    }
}

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

0 赞同 0 条回复

进取普通 2024年3月4日下午8:48

两个栈来进行操作，一个栈添加，一个栈删除，只需要把栈的数据转移一次就变成和队列一样顺序的了。时间复杂度O(n)，空间复杂度O(n)

0 赞同 0 条回复

Yox 普通 2024年3月4日下午8:36

class CQueue:

def __init__(self):
    self.s1 = deque()
    self.s2 = deque()

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


def deleteHead(self) -> int:
    if len(self.s2) == 0:
        if len(self.s1) == 0:
            return -1
        else:
            while self.s1:
                self.s2.append(self.s1.pop())

    return self.s2.pop()

Your CQueue object will be instantiated and called as such:

obj = CQueue()

obj.appendTail(value)

param_2 = obj.deleteHead()

时间o（n）空间o（1）

0 赞同 0 条回复

云无深雁影普通 2024年3月4日下午8:31

class CQueue {
Stack borrowCar;
Stack returnCar;

public CQueue() {
    borrowCar = new Stack<Integer>();
    returnCar = new Stack<Integer>();
}   
public void appendTail(int value) {
    if(returnCar.empty() && !borrowCar.empty()){
        while(!borrowCar.empty()){
            returnCar.push(borrowCar.peek());
            borrowCar.pop();
        }           
    }
        returnCar.push(value);
}

public int deleteHead() {
        while(!returnCar.empty()){
            borrowCar.push(returnCar.pop());
        }
        if(borrowCar.empty())
            return -1;
        int ans = borrowCar.pop();
        return ans;
}

}
//时间复杂度O(n)
//空间复杂度O(1)

0 赞同 0 条回复

王位詮釋普通 2024年3月4日下午7:49

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() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
            }
        }
        return stack2.isEmpty()?-1:stack2.pop();
    }
}
思路：队列特点是FIFO，而栈是FILO，刚好如果用两个栈来实现队列的话能够倒回来，一个栈专门用来存储数据，一个栈专门用来输出数据，但是需要注意，输出数据的时候要判断是否为空，如果为空的话就得从存储数据的栈中把数据导入输出数据的栈，然后进行输出。
最后如果两个栈都没有数据的话，就返回-1
时间复杂度：appendTail：O(1)
deleteHead：最坏：O(n)，最好：O(1)

0 赞同 0 条回复

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

共以下 53 个回答

利用两个栈实现FIFO

解题思路：

Your CQueue object will be instantiated and called as such:

obj = CQueue()

obj.appendTail(value)

param_2 = obj.deleteHead()

# 回答此问题取消回复

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

共以下 53 个回答

利用两个栈实现FIFO

解题思路：

Your CQueue object will be instantiated and called as such:

obj = CQueue()

obj.appendTail(value)

param_2 = obj.deleteHead()

# 回答此问题 取消回复

# 回答此问题取消回复