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

招舟子普通 2023年8月25日上午12:48

class CQueue {
Stack stack_in;
Stack stack_out;
public CQueue() {
stack_in = new Stack<>();
stack_out = new Stack<>();
}

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

public int deleteHead() {

        if (stack_out.isEmpty()){
            while (!stack_in.isEmpty()){
                stack_out.push(stack_in.pop());
                }
        }
        if (stack_out.isEmpty()){
            return -1;
        }
    return stack_out.pop();

}

}

/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/
两个栈实现，但要注意删除时必须保证出栈为空才能出栈

0 赞同 0 条回复

mpweixin用户普通 2023年7月20日下午5:44

class CQueue {

Stack<Integer> stackF; //顺序 栈顶 12345
Stack<Integer> stackL; //反序 栈顶 54321 

public CQueue() {
    this.stackF = new Stack<Integer>();
    this.stackL = new Stack<Integer>();
}

public void appendTail(int value) {
    //如果不是反序，转为反序再添加
    if(this.stackL.isEmpty()){
        while(!this.stackF.isEmpty()){
            this.stackL.push(this.stackF.pop());
        } 
    }
     this.stackL.push(value);

}

public int deleteHead() {
    //队列为空
    if(this.stackF.isEmpty() && this.stackL.isEmpty() ){
        return -1;
    }
    //如果不是正序，转为正序再删除
    if(this.stackF.isEmpty()){
        while(!this.stackL.isEmpty()){
            this.stackF.push(this.stackL.pop());
        }
    }
    return this.stackF.pop(); 
}

}

0 赞同 0 条回复

橙子陈普通 2023年7月16日上午1:21

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

0 赞同 0 条回复

ZJS 永久会员 2023年7月15日下午5:44

class CQueue {

    private Stack<Integer> s1,s2;

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

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

    public int deleteHead() {
        // 空队列
        if(s1.isEmpty() && s2.isEmpty())
            return -1;

        if(!s2.isEmpty())
            return s2.pop();

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

淡色花樱普通 2023年7月13日下午1:32

““java
class CQueue{
Stackt stack1;
Stackstack2;
publc 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 条回复

BOZ 普通 2023年7月4日下午3:57

直接用了C++ STL stack库
【时间复杂度】最好O(1)，最差O(n)
【空间复杂度】最好O(1)，最差O(n)

class CQueue {
    std::stack<int> primary;
    std::stack<int> secondary;
    bool primary_data;
public:
    CQueue() {
        primary_data = true;
    }

    void appendTail(int value) {
        if (!primary_data) {
            // move data from secondary to primary
            while(!secondary.empty()) {
                primary.push(secondary.top());
                secondary.pop();
            }
            primary_data = true;
        }
        primary.push(value);
    }

    int deleteHead() {
        if (primary_data) {
            // move data from primary to secondary
            while(!primary.empty()) {
                secondary.push(primary.top());
                primary.pop();
            }
            primary_data = false;
        }
        if (secondary.empty()) return -1;
        int result = secondary.top();
        secondary.pop();
        return result;
    }
};

0 赞同 0 条回复

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

typedef struct {
    int* stack1;
    int* stack2;
    int top1;
    int top2;
} CQueue;

CQueue* cQueueCreate() {
    CQueue* queue = (CQueue*)malloc(sizeof(CQueue));
    queue->stack1 = (int*)malloc(sizeof(int));
    queue->stack2 = (int*)malloc(sizeof(int));
    queue->top1 = -1;
    queue->top2 = -1;
    return queue;
}

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

int cQueueDeleteHead(CQueue* obj) {
    if (obj->top2 == -1) {
        if (obj->top1 == -1) {
            return -1; // 队列为空
        }
        while (obj->top1 >= 0) {
            obj->top2++;
            obj->stack2 = (int*)realloc(obj->stack2, (obj->top2 + 1) * sizeof(int));
            obj->stack2[obj->top2] = obj->stack1[obj->top1];
            obj->top1--;
        }
    }
    int value = obj->stack2[obj->top2];
    obj->top2--;
    return value;
}

bool cQueueIsEmpty(CQueue* obj) {
    return obj->top1 == -1 && obj->top2 == -1;
}

void cQueueFree(CQueue* obj) {
    free(obj->stack1);
    free(obj->stack2);
    free(obj);
}

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

0 赞同 0 条回复

3_🔥 永久会员 2023年7月3日下午8:47

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


<pre><code>}

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;

}
</code></pre>

}

用两个栈实现队列

0 赞同 0 条回复

憨憨永久会员 2023年7月3日上午10:47

通过栈1进行入队操作，入队前先判断栈2是否为空，不为空则将栈2元素压入栈1，再进行入队
出队时，将栈1元素全部压入栈2，因为先进后出，所以会从栈1的第一个元素出栈

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

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

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

0 赞同 0 条回复

大大普通 2023年7月1日下午4:07

//两个栈可以实现队列
栈A就是那个基准，栈B辅助实现删除最先进入的那一个

class CQueue {
public:
stack<int> A,B;
    CQueue() {

    }

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

 int deleteHead() {
     if(A.empty())
     return -1;
    // A->B
    while(!A.empty()){
     B.push(A.top());
     A.pop();
    }
    int t=B.top();
    B.pop();
    while(!B.empty()){
        A.push(B.top());
        B.pop();
    }
    return t;
    }
};

0 赞同 0 条回复

Tang 普通 2023年6月29日下午9:45

class CQueue {

    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

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

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

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

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

GGBond 普通 2023年6月29日下午8:01

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() && stack1.isEmpty()){
            return -1;
        }
        //如果出队列的栈为空，则把入队列的栈中元素全部迁移
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月29日下午3:05

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

时间复杂度o(n), 空间复杂度o(n)

0 赞同 0 条回复

名字什么的好麻烦普通 2023年6月27日下午8:33

两个栈

class CQueue {
    Deque<Integer> deque1;
    Deque<Integer> deque2;

    public CQueue() {
        deque1 = new LinkedList<>();
        deque2 = new LinkedList<>();
    }

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

    public int deleteHead() {
        if(!deque2.isEmpty())
            return deque2.removeLast();
        if(deque1.isEmpty())
            return -1;
        if(!deque1.isEmpty())
            deque2.addLast(deque1.removeLast());
        return deque2.removeLast();
    }
}

0 赞同 0 条回复

别恰冰水🧊 永久会员 2023年6月27日下午4:34

#define MAX_QUEUE_SIZE 10000
typedef struct{
    int *stackA;//这个用来进栈,入栈就是把value值复制到栈A中然后topA++;
    int *stackB;//这个用来出栈，出栈的是把A中的元素复制到B栈中然后topB--;
    int topA;
    int topB;
}CQueue;

CQueue* cQueueCreate(){
    CQueue *cq;
    cq = (CQueue*)malloc(sizeof(CQueue));
    if(cq == NULL)  return NULL;
    cq->stackA = (int*)malloc(MAX_QUEUE_SIZE*4);
    if (cq->stackA == NULL){
        free(cq);
        return NULL;
    }//创建成功了地址就不会是零
    cq->topA=-1;

    cq->stackB = (int*)malloc(MAX_QUEUE_SIZE*4);
    if(cq->stackB == NULL){
        free(cq->stackA);//先释放cq的底层指针
        free(cq);
        return NULL;
    }
    cq->topB =-1;
    return cq;
}

void cQueueAppendTail(CQueue *obj,int value){
    if(obj->topA != MAX_QUEUE_SIZE){
        ++obj->topA;
        obj->stackA[obj->topA] =value;/* 将新入队的元素全部压入栈A */
    }
}
int cQueueDeleteHead(CQueue *obj){
    int topBEelm = 0,topAEelm =0;

    /* 先假设B不为空，将在B栈顶的元素出队 */
    if (obj->topB != -1) {
        topBEelm = obj->stackB[obj->topB--];
        return topBEelm;
    }
    //如果栈B为空，且栈A不为空时 这里是为空之后给B添加新元素，保证B不为空
    if(obj->topB==-1&&obj->topA!=-1){
        while(obj->topA!=-1){
            topAEelm = obj->stackA[obj->topA--];
            obj->stackB[++obj->topB] = topAEelm;
        }
    }
    //如果栈B不为空，将在栈B顶的元素出队
    if(obj->topB!=-1){
        topBEelm = obj->stackB[obj->topB--];
        return topBEelm;
    }

    return -1;
}
void cQueueFree(CQueue* obj) {
    if (obj != NULL) {
        if (obj->stackA != NULL) { free(obj->stackA); }
        if (obj->stackB != NULL) { free(obj->stackB); }
        free(obj);
    }
}

0 赞同 0 条回复

Dsjh 普通 2023年6月27日上午9:09

c++ 实现

class CQueue {
public:
    stack<int> q1;
    stack<int> q2;
    CQueue() {

    }

    void appendTail(int value) {
        q1.push(value);
        return;
    }

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

        int temp = q2.top();
        q2.pop();
        return temp;

    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年6月25日下午11:03

python 一个输入栈一个输出栈
时间复杂度O(n)

class CQueue:

    def __init__(self):
        self.input, self.output = [], []

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

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


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

0 赞同 0 条回复

拾陆. 普通 2023年6月25日下午10:04

class CQueue {
public:
    CQueue() {

    }

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

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

C++实现

0 赞同 0 条回复

普通 2023年6月25日上午11:28

class CQueue {

    LinkedList leftLinkedList;
    LinkedList rightLinkedList;

    public CQueue() {
        rightLinkedList = new LinkedList<>();
        leftLinkedList = new LinkedList<>();
    }

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

    public int deleteHead() {

        if(!rightLinkedList.isEmpty()){
            return rightLinkedList.pop();
        }
        if(leftLinkedList.isEmpty()){
            return -1;
        }
         while (!leftLinkedList.isEmpty()) {
            rightLinkedList.push(leftLinkedList.pop());
        }
        return rightLinkedList.pop();
    }
}

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

0 赞同 0 条回复

Jerry 普通 2023年6月24日下午9:30

class CQueue {
    LinkedList<Integer> A, B;
    // 让元素“入队”时，只要把元素压入 A 即可
    // 让元素“出队”时
    //      若 B 不为空，可以把 A 的所有元素取出再添加进 B，这时候 B 中元素就是先进先出顺序了
    //      若 B 不为空，则直接返回 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(n)
空间复杂度：O(1)

0 赞同 0 条回复

mpweixin用户普通 2023年6月24日下午8:51

逆向遍历

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null) {
            return new int[0];
        }

        ListNode tmpNode = head;
        int length = 0;
        while(tmpNode !=null) {
            length++;
            tmpNode = tmpNode.next;
        }

        int[] res = new int[length];
        int index = length-1;
        while(head !=null) {
            res[index--] = head.val;
            head = head.next;
        }
        return res;

    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月24日下午8:27

C++实现

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

}

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

int deleteHead() {
    if(s1.empty() && s2.empty()) return -1;

    if(s2.empty()){
        while(!s1.empty()){
            s2.push(s1.top());
            s1.pop();
        }
    }
    int k = 0;
    k = s2.top();
    s2.pop();

    return k;
}

stack<int> s1;
stack<int> s2;

};

“`

0 赞同 0 条回复

* 普通 2023年6月24日下午8:20

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

}

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

int deleteHead() {
    if(!stack2.empty()){    //stack2还有元素
        int ans = stack2.top();
        stack2.pop();
        return ans;
    }
    else{   //stack2为空，判断stack1是否为空
        if(!stack1.empty()){    //stack1不为空
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
            int ans =stack2.top();
            stack2.pop();
            return ans;
        }
        else{  //stack1为空
            return -1;
        }
    }
}

};

0 赞同 0 条回复

Bello~ 普通 2023年6月24日下午8:17

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

class CQueue {

    Stack<Integer> stack1 = null;
    Stack<Integer> stack2 = null;

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

0 赞同 0 条回复

地平线真勇敢普通 2023年6月24日下午5:25

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

}
时间复杂度：o(1)
空间复杂度：o(1)

0 赞同 0 条回复

mpweixin用户普通 2023年6月24日下午2:08

C++
TC: O(1) & O(n)
SC: O(n)
根据题意

“`c++
class CQueue {
stackstk1;
stackstk2;
public:
CQueue() {

}

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

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

}

};

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

“`

0 赞同 0 条回复

CV大神普通 2023年6月24日上午7:33

“`java

public static class CQueue {
    private Stack<Integer> stackA;
    private Stack<Integer> stackB;

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

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

    public int deleteHead() {
        //说明已经有排好顺序的了，直接返回
        if (!stackB.isEmpty()) {
            return stackB.pop();
        }
        //说明上面没有排好的，没排好的也没有，所以是空队列
        if (stackA.isEmpty()) {
            return -1;
        }
        //把A全部排到B里面
        while (!stackA.isEmpty()) {
            stackB.push(stackA.pop());

        }
        return stackB.pop();

    }

}

“`java
时间复杂度：appendTail O(1),空间复杂度O(1)
deleteHead O(n)
空间复杂度：O(n)

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月24日上午6:14

class CQueue:

    def __init__(self):
        self.stackA = []
        self.stackB = []

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


    def deleteHead(self) -> int:
        if self.stackB:
            return self.stackB.pop()

        # 边界情况
        if not self.stackA:
            return -1

        while self.stackA:
            self.stackB.append(self.stackA.pop())

        return self.stackB.pop()



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

0 赞同 0 条回复

彦，，# 普通 2023年6月23日下午10:41

一个栈进，一个栈出

class CQueue {
private:
    stack<int> stack1, stack2;
public:
    CQueue() {
    }
    void appendTail(int value) {
        stack1.push(value);
    }
    int deleteHead() {
        if(stack2.empty())
        {
            if(stack1.empty()) return -1;
           while(!stack1.empty())
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int value = stack2.top();
        stack2.pop();
        return value;
    }
};

0 赞同 0 条回复

哈哈哈普通 2023年6月23日下午8:19

思路：使用最简单的两个栈实现：利用栈先进后出的特点，stack1作为对头，当有元素进行插入时，将stack2的元素重新加回，再进行入栈；stack2最为队尾，删除节点时先将stack1中的元素进行添加，然后再进行元素删除；从而实现队列的先进先出的特点。
时间复杂度O（1）,空间复杂度O（1）。

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

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

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

但是运行结果后的速率有点低，而且感觉个人的思路存在问题，执行一个步骤进行数据回写的话，会造成数据的重复放置，遂找到了另一个方法：stack1进行插入数据存放，stack2进行数据删除。在不为空的情况下直接删除，在为空的情况下去stack1寻找数据，二者都为空的情况下返回-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.empty()){
           if(stack1.empty()){
               return -1;
           }
               while(!stack1.empty()){
                   stack2.push(stack1.pop());
           }
       }
        return stack2.pop();
    }
}

这个的速度就有点提升了。

0 赞同 0 条回复

张开怀普通 2023年6月23日下午7:55

class CQueue{
public:
     CQueue(){
     }

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

     int deleteHead(){
          // 栈2不为空，输出栈2的顶部元素
          if (!stack.empty()){
               int res = stack2.top();
               // 顶部元素出栈
               stack2.pop();
               return res;
          }
          // 此时栈2为空，若栈1不为空，将栈1中的元素依次出栈，放入栈2中
          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;
}

0 赞同 0 条回复

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

两个栈实现队列
class CQueue:

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

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

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


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

0 赞同 0 条回复

～普通 2023年6月23日下午4:53

c++解题思路
class CQueue {
stack s1;
stack s2;
public:
CQueue() {
stack st1;
s1 = st1;
stack st2;
s2 = st2;
}

void appendTail(int value) {
    s1.push(value);
}
int peek(){
    while(s2.empty()){
        while(!s1.empty()){
            s2.push(s1.top());
            s1.pop();
        }
    }
    return s2.top();
}
int deleteHead() {
    if(s1.empty()&&s2.empty()) return -1;
    int res = peek();
    s2.pop();
    return res;
}

};

0 赞同 0 条回复

Yodl. 普通 2023年6月23日下午1:47

打卡

class CQueue {
public:
    CQueue() {

    }

    vector<int> s1,s2;
    void appendTail(int value) {
        s1.push_back(value);
    }

    int deleteHead() {
        if(s1.empty()!=true)
        {
            while(s1.empty()!=true)
            {
                int tmp=s1.back();
                s2.push_back(tmp);
                s1.pop_back();
            }
            int ans=s2.back();
            s2.pop_back();
            while(s2.empty()!=true)
            {
                int tmp=s2.back();
                s1.push_back(tmp);
                s2.pop_back();
            }
            return ans;
        }
        return -1;
    }
};

0 赞同 0 条回复

张君雅小妹妹普通 2023年6月23日下午1:38

时间复杂度：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();
        } else {
            return -1;
        }
    }
}

0 赞同 0 条回复

花老爷普通 2023年6月23日下午1:38

使用inStack和outStack模拟队列：
1.入队时将元素push入inStack中。
2.出队时从outStack中pop出元素，若outStack没有元素：
1）inStack有元素，直接将inStack里的元素pop到outStack中。
2）inStack没有元素，此时代表整个队列没有元素，返回-1。
时间：O(1)，从inStack pop到outStack的时间被均摊。
空间：O(n)

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

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

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

    public int deleteHead() {
        // 当outStack有元素时，直接返回
        if (!outStack.isEmpty()) {
            return outStack.pop();
        } 
        // 当outStack没有元素而inStack有元素时，pop出inStack所有元素到outStack，之后返回
        if (!inStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
            return outStack.pop();
        }
        // 当两个栈都没有元素时，返回-1
        return -1;
    }
}

0 赞同 0 条回复

　　　　　　　　普通 2023年6月23日下午12:16

class CQueue {
    stack<int>a,b;
public:

    CQueue() {
    }

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

    int deleteHead() {
        if(a.empty())return -1;
        while(!a.empty()){
            b.push(a.top());
            a.pop();
        }
        int t=b.top();
        b.pop();
        while(!b.empty()){
            a.push(b.top());
            b.pop();
        }
        return t;
    }
};

【时间O(n),空间O(n)】

0 赞同 0 条回复

硬核洋葱普通 2023年6月23日上午11:19

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

    CQueue() {

    }

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

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

        int ans = stk2.top();
        stk2.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(1), 出队时间复杂度O(n)

0 赞同 0 条回复

peach 普通 2023年6月23日上午10:15

思路

使用两个栈，一个stackIn，一个stackOut模拟即可
栈是先入后出，队列是先入先出

代码

class CQueue {

    private Deque<Integer> stackIn; //第一个栈，用来加入元素
    private Deque<Integer> stackOut; //第二个栈，用来弹出元素

    public CQueue() {
        stackIn = new ArrayDeque();
        stackOut = new ArrayDeque(); //进行初始化
    }

    public void appendTail(int value) {
        stackIn.addFirst(value); //加入元素，直接加入stackIn即可
    }

    public int deleteHead() { //删除元素
        if(stackOut.isEmpty()){
            dump(); //如果stackOut为空，先进行倾倒
        }
        return stackOut.isEmpty() ? -1 : stackOut.removeFirst(); //再在stackOut中把元素弹出
    }

    private void dump(){ //把stackIn的元素依次倒入stackOut中
        while(!stackIn.isEmpty()){
            stackOut.addFirst(stackIn.removeFirst());
        }
    }
}

0 赞同 0 条回复

断舍离永久会员 2023年6月23日上午8:56

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()){
            //说明没有元素了，返回-1
            if(stackIn.empty()){
                return -1;
            }
            //将栈(入)元素pop，push到栈(出)中
            while (!stackIn.empty()){
                stackOut.push(stackIn.pop());
            }
        }
        return stackOut.pop();
    }
}

0 赞同 0 条回复

残月冷骄阳普通 2023年6月23日上午1:09

//创建一个进栈，一个出栈，进栈只管操作进入的数字，当出的栈为空的时候，从进栈中拿数据，如果未拿到则为-1，负责就拿出数据进行pop操作
class CQueue {
    Stack<Integer> appendStack;
    Stack<Integer> deleteStack;
    public CQueue() {
    this.appendStack = new Stack<>();
    this.deleteStack = new Stack<>();
    }

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

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

0 赞同 0 条回复

大鑫啊普通 2023年6月22日下午11:50

时空复杂度：O(n)
1、理清思路，创建两个栈s1，s2
2、入队列的元素都放进s1
3、出队时，（1）如果s2不为空，则将s2中弹出（2）如果s2为空，s1不为空，则将s1中全部弹出并一次放入s2中（3）如果s1、s2都为空，则返回-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();
        }else if(!stack1.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }else{
            return -1;
        }
    }
}

0 赞同 0 条回复

怀瑾永久会员 2023年6月22日下午11:48

C++实现

#include <stack>
using namespace std;

class CQueue {
public:
    CQueue() {

    }

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

    int deleteHead() {
        if(s1.empty() && s2.empty()) return -1;
        if(s2.empty()) {
            while(!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        } 
        int res = s2.top();
        s2.pop();
        return res;
    }
private:
    stack<int> s1, s2;
};

0 赞同 0 条回复

Vow the vow。普通 2023年6月22日下午11:45

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

private Stack<Integer> stack;
    private Stack<Integer> tempStack;

    public CQueue() {
        stack = new Stack();
        tempStack = new Stack();
    }

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

    public int deleteHead() {
        if(stack.isEmpty()) return -1;
        tempStack.clear();
        while(!stack.isEmpty()){
            tempStack.push(stack.pop());
        }
        int res = tempStack.pop();
        while(!tempStack.isEmpty()){
            stack.push(tempStack.pop());
        }
        return res;
    }

0 赞同 0 条回复

江畅普通 2023年6月22日下午10:14

#include <iostream>
#include <stack>
using namespace std;

// 两个栈实现队列
// 时间复杂度：O(1)
// 空间复杂度：O(N)
class CQueue {
private:
    stack<int> st_in;
    stack<int> st_out;

public:
    CQueue() {}

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

    int deleteHead() {

        // 用于出队的栈非空，可直接出队
        if (!st_out.empty()) {
            int res = st_out.top();
            st_out.pop();
            return res;
        }

        // 用于出队的栈空、用于入队的栈空
        // 即队列无元素，无法出队
        if (st_in.empty()) {
            return -1;
        }

        // 用于出队的栈空，则需将用于进队的栈元素转移到用于出队的栈
        while (!st_in.empty()) {
            int& value = st_in.top();
            st_out.push(value);
            st_in.pop();
        }

        int head = st_out.top();
        st_out.pop();
        return head;
    }
};

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

    CQueue* obj = new CQueue();
    obj->appendTail(1);
    obj->appendTail(2);
    // que.appendTail(3);

    cout << obj->deleteHead() << endl;
    cout << obj->deleteHead() << endl;
    cout << obj->deleteHead() << endl;

    delete obj;

    return 0;
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月22日下午9:54

思路：设计两个栈，一个负责出队，一个负责入队，入队时直接尽负责入队的栈，出队时，先看负责出队的栈是否为空，不为空直接出栈，为空时，将入队栈内的数据弹出，压入出队栈，然后再出栈，当两栈都为空时，返回空。
C++代码
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()){ // 1 -> 2
        int tmp = stack1.top();
        stack1.pop();
        stack2.push(tmp);
    }
    // delete head
    int res = stack2.top();
    stack2.pop();
    while (!stack2.empty()){ // 1 <- 2
        int temp = stack2.top();
        stack2.pop();
        stack1.push(temp);
    }
    return res;
}

};

0 赞同 0 条回复

局外人普通 2023年6月22日下午8:47

思路：两个栈，一个为入队栈，一个为出队栈。有入队操作时，直接压入入队栈；有出队操作时，先看出队栈是否为空，若有元素，则直接删除出队栈栈顶元素并返回；若为空，再看入队栈，若入堆栈有元素则全部压入出队栈，再删除出队栈栈顶元素并返回，若入堆栈没有元素，则返回-1。

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()){
                    int temp=s1.top(); s1.pop();
                    s2.push(temp);
                }  
            }
        }
        int res = s2.top();s2.pop();
        return res;
    }
};

0 赞同 0 条回复

Ming 普通 2023年6月22日下午8:18

这里是Ming的打卡：
一个栈用于输入，一个栈用于输出
一个栈数据转给另一个栈的时机：输出的栈此时为空，否则直接输出

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

yxy 普通 2023年6月22日下午8:01

简单

class CQueue {
    stack<int> st1;
    stack<int> st2;
public:
    CQueue() {

    }

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

    int deleteHead() {
        if(st2.empty())
        {
            while(st1.size())
            {
                st2.push(st1.top());
                st1.pop();
            }
        }
        if(st2.empty())
            return -1;
        else
        {
            int ret = st2.top();
            st2.pop();
            return ret;
        }
    }
};

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

0 赞同 0 条回复

zll 普通 2023年6月22日下午7:57

c实现

#define MaxSize 10000
typedef struct {
    int *stackA;
    int *stackB;
    int topA;
    int topB;
} CQueue;


CQueue* cQueueCreate() {
    CQueue* cq=(CQueue*) malloc(sizeof(CQueue));
    if(!cq) 
        return NULL;

    cq->stackA=(int*) malloc(MaxSize*sizeof(int));
    if(!cq->stackA){
        free(cq);
        return NULL;
    }
    cq->topA=-1;

    cq->stackB=(int*) malloc(MaxSize*sizeof(int));
    if(!cq->stackB){
        free(cq->stackA);
        free(cq);
        return NULL;
    }
    cq->topB=-1;

    return cq;
}

void cQueueAppendTail(CQueue* obj, int value) {
    if(obj->topA!=MaxSize){
        obj->stackA[++obj->topA]=value;
    }
}

int cQueueDeleteHead(CQueue* obj) {
    if(obj->topB!=-1){
        return obj->stackB[obj->topB--];
    }

    if(obj->topA!=-1){
        while(obj->topA!=-1){
            obj->stackB[++obj->topB]=obj->stackA[obj->topA--];
        }
        return obj->stackB[obj->topB--];
    }
    return -1;
}

void cQueueFree(CQueue* obj) {
    if(obj){
        if(obj->stackA)
            free(obj->stackA);
        if(obj->stackB)
            free(obj->stackB);
        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);
*/

1 赞同 0 条回复

行动派小彩笔普通 2023年6月22日下午7:54

// 时间复杂度，最坏情况下sk1有n个元素，到给sk2，需要遍历，时间复杂度为O(n)
// 空间复杂度，最坏情况，sk1和sk2都有n个元素

class CQueue {
public:
    stack sk1;
    stack sk2;
    CQueue() {

    }

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

    int deleteHead() {  
        if(!sk2.empty()) //如果sk2还有元素就先出队
        {
            int ret = sk2.top();
            sk2.pop();
            return ret;
        }
        else if(sk1.empty()) return -1; // 都没有元素了return -1
        while(!sk1.empty()) //sk2没有元素，sk1还有元素
        {
            sk2.push(sk1.top());
            sk1.pop();
        }
        int ret = sk2.top();
        sk2.pop();
        return ret;

    }
};

// 精简版本
class CQueue {
public:
    stack sk1;
    stack sk2;
    CQueue() {

    }
    
    void appendTail(int value) {
        sk1.push(value);
    }
    
    int deleteHead() {  
        if(sk1.empty()&&sk2.empty()) return -1; // 1 2都空
        if(sk2.empty()) //2空 1不空
        {
            while(!sk1.empty())
            {
                sk2.push(sk1.top());
                sk1.pop();
            }
        }
        // 1空，2不空
        int ret = sk2.top();
        sk2.pop();
        return ret;
        
    }
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月22日下午6:56

//两个栈实现先进先出
class CQueue {

    Stack<Integer> stackA;
    Stack<Integer> stackB;

    public CQueue() {
        stackA = new Stack();
        stackB = new Stack();
    }

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

    public int deleteHead() {
        if(stackB.isEmpty() && stackA.isEmpty()){
            return -1;
        }

        if(stackB.isEmpty()){
            while(!stackA.isEmpty()){
                stackB.push(stackA.pop());
            }
        }

        return stackB.pop();
    }
}

1 赞同 0 条回复

雨落圆荷普通 2023年6月22日下午4:38

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年6月22日下午4:01

class CQueue {
//用两个栈实现队列
//队尾栈顶压入
ArrayDeque stackW;
ArrayDeque stackT;

public CQueue() {
    stackW=new ArrayDeque<Integer>();
    stackT=new ArrayDeque<Integer>();
}

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

public int deleteHead() {
    if(stackT.isEmpty()){
        while(!stackW.isEmpty()){
            stackT.push(stackW.pop());
        }
    }
    if(stackT.isEmpty() && stackW.isEmpty()){
        return -1;
    }else{
        return stackT.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年6月22日下午3:24

c++双栈实现
private:
stacks1,s2;
public:
CQueue() {

}

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

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

0 赞同 0 条回复

désire. 普通 2023年6月22日下午2:52

“`C++
class CQueue {
public:
stack stIn;
stack stOut;
CQueue() {
}
//在队列尾部插入整数
void appendTail(int value) {
stIn.push(value);
}
//在队列头部删除整数
int deleteHead()
{
if(stIn.empty() && stOut.empty())
{
return -1;
}
//stOut为空
if(stOut.empty())
{
while(!stIn.empty())
{
stOut.push(stIn.top());
stIn.pop();
}
}
int result = stOut.top();
stOut.pop();
return result;
}
};

0 赞同 0 条回复

mpweixin用户普通 2023年6月22日下午2:17

C++实现，设置两个栈，插入放到一个栈，当删除时先判断边界

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

    }

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

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

0 赞同 0 条回复

jhfuture 普通 2023年6月22日下午2:13

java实现

class CQueue {

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

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

    public int deleteHead() {
            // 如果栈2为空则把栈1的数据全部出战
            //如果我栈1为空则返回-1，如果栈1不为空则出栈数据到栈2，并返回栈2的元素
            if(stack2.isEmpty()){
                if(stack1.isEmpty()){
                    return -1;
                }else{
                    while(!stack1.isEmpty()){
                        int value= stack1.pop();
                        stack2.push(value);
                    }
                    //放完后再返回
                    return stack2.pop();
                }
            }else{
                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 条回复

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

共以下 58 个回答

思路

代码

# 回答此问题取消回复

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

共以下 58 个回答

思路

代码

# 回答此问题 取消回复

# 回答此问题取消回复