梧葳普通 2023年9月2日下午1:41

“””
/*

使用两个栈的目的是，这种方式刚好能模拟成队列的出入栈方式

*/

#define MAX_LEN 10000

typedef struct {
int topA;
int topB;
int *stackA;
int *stackB;
} CQueue;

CQueue* cQueueCreate() {
// 申请堆区内存
CQueue cq = (CQueue)calloc(1, sizeof(CQueue));
if (cq NULL) {
return NULL;
}
// stackA申请堆区空间
cq->stackA = (int)calloc(MAX_LEN, sizeof(int));
if (cq->stackA NULL) {
free(cq);
return NULL;
}
// stackB申请堆区空间
cq->stackB = (int)calloc(MAX_LEN, sizeof(int));
if (cq->stackB NULL) {
free(cq->stackA);
free(cq);
return NULL;
}
// 定义大小
cq->topA = -1;
cq->topB = -1;

return cq;

}

void cQueueAppendTail(CQueue* obj, int value) {
// 直接stackA尾部添加
if (obj->topA < MAX_LEN) {
obj->stackA[++obj->topA] = value;
}
}

int cQueueDeleteHead(CQueue* obj) {
// 若stackB存在值则直接操作
if (obj->topB >= 0) {
return obj->stackB[obj->topB–];
}
// 否则将stackA的值放入stackB
if (obj->topA >= 0) {
while(obj->topA >= 0) {
int tmp = obj->stackA[obj->topA–];
obj->stackB[++obj->topB] = tmp;
}
return obj->stackB[obj->topB–];
}
// 均没有值返回-1
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 条回复

我一定要坚持打卡普通 2023年8月27日下午5:37

思路

解题思路

使用两个栈实现队列的两个函数，模拟在队列尾部中插入新元素，和在队列头部弹出元素的过程

解题方法

解题方法

使用两个栈去实现一个队列，一个栈用于存放新插入队列的数据，一个栈用于出队列的数据
当插入队列的时候，将数据存放到入栈中，出队列时候，先从出栈中取出元素，如果出栈为空，
则将入队列中的数据全部放入到出栈并输出栈顶元素

复杂度

时间复杂度:

时间复杂度： $O(n)$

空间复杂度:

空间复杂度： $O(n)$

Code

class CQueue {
/**
使用两个栈去实现一个队列，一个栈用于存放新插入队列的数据，一个栈用于出队列的数据
当插入队列的时候，将数据存放到入栈中，出队列时候，先从出栈中取出元素，如果出栈为空，
则将入队列中的数据全部放入到出栈并输出栈顶元素
 */

    Stack<Integer> inStack;
    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()){// 先保证入栈不为空
            while(!inStack.isEmpty()){//将入栈内的数据全部压入到出栈中
            outStack.push(inStack.pop());
            }
        return outStack.pop();
        }
        return -1; //两个栈都是空，则返回-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 条回复

漂洋过海去见你永久会员 2023年8月27日下午3:34

#python题解：
#
class CQueue(object):

def __init__(self):
    self.stack1 = [] //入队列直接压入stack1
    self.stack2 = [] //出队列使用stack2


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


def deleteHead(self):
    """
    :rtype: int
    """
    if self.stack2 == []:
        if self.stack1 == []:
            return -1
        else:
            for i in range(len(self.stack1)):
                self.stack2.append(self.stack1.pop())  //将stack1的末尾元素pop出压入stack2，那么最后stack2出队列的元素正好是stack1的开头元素

    return self.stack2.pop()

0 赞同 0 条回复

Di questa storia sempre a lie to 普通 2023年8月25日上午12:28

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
    while self.A:
        self.B.append(self.A.pop())
    return self.B.pop()

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

0 赞同 0 条回复

Miracle· 普通 2023年8月24日下午6:27

lass CQueue {
public:
CQueue() {

}

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

int deleteHead() {
    if (outStack.empty()) {
        // 判断instack中是否有元素，没元素代表此时队列中没有元素，删除返回-1
        if (inStack.empty()) return -1;
        intout(); // 否则把instack中的元素转到outstack中完成反转
    }
    int res = outStack.top();
    outStack.pop();
    return res;
}

private:
stack inStack, outStack; // 一个用于插入元素的栈，一个用于删除元素的栈

// 负责把inStack中的元素全部压入到outStack中，实现将栈中元素的位置反转
void intout() {
    while (!inStack.empty()) {
        outStack.push(inStack.top());
        inStack.pop();
    }
}

};

0 赞同 0 条回复

谁仁普通 2023年8月24日下午5:26

struct stack{
int * data;
int top;
int size;
};

struct queue{
struct stack * stack1;
struct stack * stack2;
};

void initStack(struct stack *s,int size)
{
s->data = (int *)malloc(sizeof(int) * size);
s->top = -1;
s->size = size;
}

int catEmpty(struct stack * s)
{
return (s->top -1);
}

int catFull(struct stack *s)
{
return (s->top s->size -1);
}

void push(struct stack * ,int val)
{
if(catEmpty(s))
{
return ;
}
s->data[++(s->top)] = val;//压栈
}

int pop(struct stack *s)
{
if(catEmpty(s))
{
return -1;
}
return s->data[(s->top)–];//出栈
}

void initQueue(struct queue que,int size)
{
que->stack1 = (struct queue)malloc(sizeof(struct queue));
que->stack2 = (struct queue*)malloc(sizeof(struct queue));
initStack(queue->stack1,size);
initStack(queue->stack2,size);
}

int catQueue(struct queue* que)
{
return (catEmpty(que->stack1)&&catEmpty(que->stack2));
}

void inputQue(struct queue* que,int val)
{
if(catFull(que->stack1))
{
return;
}

while(!catEmpty(que->stack2))
{
    push(que->stack1,pop(que->stack2));//入队列，将两栈一进一出形成一列
}

}

int deQue(struct queue* que)
{
if(catQueue(que)
{
return -1;
}

return pop(que->stack1);//将栈区1作为队列返回出来

}时间复杂度o（n），空间复杂度o（n）

0 赞同 0 条回复

mpweixin用户普通 2023年8月23日下午10:28

时间复杂度：O(n^2), 空间复杂度：O（n）
两个栈一个用于正向存储，一个反向存储，在正向存储的栈中直接添加整数，删除整数时先判断反向存储的栈中有没有值，有则pop反向栈，无则将正向栈中的值存储到反向栈中再pop

class CQueue {

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

mpweixin用户普通 2023年8月23日上午11:51

//根据栈的先进后出以及队列先进先出的原理，
//用第一个栈模拟队列的先进，另一个辅助栈来模拟队列的先出。
//时间复杂度为o(1);
//空间复杂度为o(n);
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();
        stack1.pop();
        stack2.push(tmp);
    }

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

}

};

0 赞同 0 条回复

小火普通 2023年8月23日上午10:42

一个栈用作入，一个栈用作出；pop队列时如果出栈为空，则从入栈中取出一个放到出栈
时间复杂度：o(n)
空间复杂度：o(1)

class CQueue {
private:
    stack<int> inst, outst;
    //连接
    void in2out() {
        while(!inst.empty()) {
            outst.push(inst.top());
            inst.pop();
        }
    }

public:
    CQueue() { } // 构造函数

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

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

    }
};

0 赞同 0 条回复

sc_Yang 普通 2023年8月21日下午9:41

class CQueue {
    private:
        stack<int> inStack, outStack;
        // stack中的pop()返回值为void
        void in2out(){
            while(!inStack.empty()){
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
public:
    CQueue() {}

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

    int deleteHead() {
        // // 每次outStack吐干净之后再重新从inStack引进
        // if(outStack.empty()){
        //     if(inStack.empty()){
        //         return -1;
        //     }
        //     in2out(); // 此处必加
        // }
        // int value = outStack.top(); // stack.top()返回值为栈顶元素
        // outStack.pop(); // stack.pop()返回值为void
        // return value;

        if(outStack.empty()){
            if(inStack.empty()){
                return -1;
            }
            else{
                in2out();
                int value = outStack.top(); // stack.top()返回值为栈顶元素
                outStack.pop(); // stack.pop()返回值为void
                return value;
            }
        }else{
            int value = outStack.top(); // stack.top()返回值为栈顶元素
            outStack.pop(); // stack.pop()返回值为void
            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 条回复

mpweixin用户普通 2023年8月21日下午8:14

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

    }

    void appendTail(int value) {
        //入队的时候 把元素放入栈1
        s1.push(value);
    }

    int deleteHead() {
        //如果栈2非空，直接出栈2
        if(!s2.empty()){
            int re = s2.top();
            s2.pop();
            return re;
        }
        //如果栈2为空栈1不为空，将栈1所有元素放入栈2，然后出栈2一个元素
        if(!s1.empty()){
            while(!s1.empty()){
                int re = s1.top();
                s1.pop();
                s2.push(re);
            }
            int a = s2.top();
            s2.pop();
            return a;
        }
        //否则的话 也就是栈1 栈2均为空
        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 条回复

小肸永久会员 2023年8月21日下午2:13

class CQueue {
    //添加元素时向栈2入栈，取出元素时向栈1出栈。
    //如果栈1为空，将栈2的元素一次出栈然后入栈到栈1中。从而让最先添加的元素位于栈顶，达到先进先出的顺序
    Deque<Integer> stack1;
    Deque<Integer> stack2;
    public CQueue() {
        stack1 = new ArrayDeque<>();
        stack2 = new ArrayDeque<>();        
    }
    public void appendTail(int value) {
        stack2.push(value);
    }
    public int deleteHead() {
        if (!stack1.isEmpty()) {
            return stack1.pop();
        }
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        return stack1.isEmpty() ? -1 : stack1.pop();
    }
}

0 赞同 0 条回复

💮黧大王.exe 普通 2023年8月20日下午6:02

时间复杂度：O(n)，空间复杂度：O(n)
class CQueue {
public:
stack stack1;
stack stack2;
CQueue() {

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

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

};

0 赞同 0 条回复

QQiing 普通 2023年8月19日下午5:23


class CQueue {
public:  
    stack  stack1;
    stack  stack2;  
    CQueue() {

    }
    
    void appendTail(int value) {
        stack1.push(value);
    }
    
    int deleteHead() {
        if(!(stack2.empty()))
        {
            int result = stack2.top();
            stack2.pop();
            return result;
        }
        if(!stack1.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
            int result = stack2.top();
            stack2.pop();
            return result;
        }
        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年8月19日下午3:36

class CQueue {

    Stack<Integer> A;
    Stack<Integer> B;

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

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

    public int deleteHead() {
        if(!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 条回复

Marc 普通 2023年8月17日下午11:57

class CQueue:

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

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

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

空间On 插入O1 弹出On

0 赞同 0 条回复

海浪漂哇漂普通 2023年8月17日下午10:55

打卡

class CQueue {

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

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

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

        if(!s2.isEmpty()){
            return s2.pop();
        }else{
            return -1;
        }
    }
}

0 赞同 0 条回复

Sheng 永久会员 2023年8月17日下午9:00

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

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

public int deleteHead()
{
    if(stack2.size() > 0)
        return stack2.pop();

    //在栈的元素有变化的时候，不要使用size，直接使用empty()即可
    if(!stack1.empty()) {
        while(!stack1.empty()) {
            int element = stack1.pop();
            stack2.push(element);
        }
        return stack2.pop();
    }

    return -1;
}

}

0 赞同 0 条回复

一个人的风海吹了两遍普通 2023年8月17日下午4:36

用链表实现栈，用栈实现队列

class CQueue {

    LinkedList<Integer> A,B;

    public CQueue() {
        A = new LinkedList<>();
        B = new LinkedList<>();
    }

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

    public int deleteHead() {
        if(!B.isEmpty()) return B.removeLast();
        else if(A.isEmpty()) return -1;
        else{
            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();
 */

0 赞同 0 条回复

sincere 普通 2023年8月17日上午10:48

思路：s1 存数据，删除时按把 s1 数据存到 s2，则 s2 的数据从栈顶到栈底就是和队列一致的，删除栈顶即为最早的，导数据前先判断 s2 栈内有没有数据，有的话直接删即可
复杂度：空间复杂度O(n)，时间复杂度添加O(1)、删除O(n)

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

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

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

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

0 赞同 0 条回复

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

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 val = outStack.top();
    outStack.pop();
    return val;
}

};

0 赞同 0 条回复

Joel 普通 2023年8月16日下午4:29

时间O（n）空间O（n）

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

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

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

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

0 赞同 0 条回复

欢⁶ 普通 2023年8月16日上午9:33

class CQueue:

def __init__(self):
    # 设定两个栈，一个负责入，一个负责出
    self.in_stack = []
    self.out_stack = []

def appendTail(self, value: int) -> None:
    # in_stack只负责模拟进入队列操作
    self.in_stack.append(value)



def deleteHead(self) -> int:
    # out_stack 负责模拟出队列的操作

        # 若out_stack为空
        # 如果in_stack也为空，说明队列为空，按题意直接返回-1
        # out_stack空，in_stack不空，说明队列列还有元素存在，就先将in_stack中的导入out_stack中，再弹出out_stack中最后一个
        if not self.out_stack:
            if not self.in_stack:
                return -1
            else:
                while self.in_stack :
                    self.out_stack.append(self.in_stack.pop())

                return self.out_stack.pop()
        else:
             return self.out_stack.pop()

0 赞同 0 条回复

别扒拉我普通 2023年8月15日下午11:33

1、简答题，两个stack之间的push和pop

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

0 赞同 0 条回复

Jou Siankwa 普通 2023年8月15日下午11:09

class CQueue {

    Stack<Integer> in;
    Stack<Integer> out;
    public CQueue() {
        in = new Stack<>();
        out = new Stack<>();
    }

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

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

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

一个栈用来压入数据，一个栈用来弹出数据，有弹出数据时第二个栈中内容

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月15日下午9:45

用两个栈来模拟

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

0 赞同 0 条回复

木子有点甜🍒 普通 2023年8月15日下午8:26

“`python
还是比较好想的。
class CQueue:

def __init__(self):
    self.inq = []
    self.outq = []


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


def deleteHead(self) -> int:
    if self.outq:
        return self.outq.pop()
    if not self.inq:#这里用self.inq==None会报错
        return -1

    while self.inq:
        self.outq.append(self.inq.pop())
    return self.outq.pop()

Your CQueue object will be instantiated and called as such:

obj = CQueue()

obj.appendTail(value)

param_2 = obj.deleteHead()

“`python

0 赞同 0 条回复

木木普通 2023年8月15日下午4:44

时间复杂度: 入队: O(1) 出队: O(n)
使用两个stack 一个用来储存准备弹出的value 一个用来压入新进来的元素, 当弹出的stack不为空时则不用考虑压入的stack, 直接弹出就行,因为队列本来就是FIFO, 而如果弹出的stack为空则需要判断压入的stack是否为空, 如果不是的话需要先将元素从压入的stack 全部弹出并依序压入另一个stack后再弹出最上面的那个元素


class CQueue {
    
public:
  stack s1, s2;
  CQueue() {}
  
  void appendTail(int value) {
    s1.push(value);
  }
  
  int deleteHead() {  
    if (!s2.empty()) {
      int res = s2.top();
      s2.pop();
      return res;
    }
    if (s1.empty()) {
      return -1;
    }
    while (!s1.empty()) {
      s2.push(s1.top());
      s1.pop();
    }
    int res = s2.top();
    s2.pop();
    return res;
  }
};

0 赞同 0 条回复

hhhhh 普通 2023年8月15日下午4:28

两个栈一个负责压入，一个负责弹出，弹出栈如果不为空，则不需要考虑压入栈，可直接弹出，因为弹出栈的元素一定是比压入栈先弹出。

“`cpp
class CQueue {
public:
stack st1;
stack st2;
CQueue() {

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

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

};

0 赞同 0 条回复

逸兴遄飞普通 2023年8月15日下午4:16

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

class CQueue {
    // 初始化两个栈
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void appendTail(int value) {
        // 入队，stack1填数
        stack1.push(value);
    }

    public int deleteHead() {
        // stack2不为空则进行出栈操作
        if(!stack2.isEmpty()){
            return stack2.pop();
        }
        // stack1不为空则将其内的数据压入stack2中
        if(!stack1.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
        // 若两栈均为空，则返回-1
        return -1;
    }
}

0 赞同 0 条回复

辰北、普通 2023年8月15日下午3:36

思路，俩栈，俩栈顶一个代表rear，一个front；添加data[++q.rear]=value,jiandehua1 循环while(obj->rear >= 0){obj->stack2[++(obj->front)] = obj->stack1[(obj->rear)–];int value = obj->stack2[(obj->front)–];//二栈等于一栈逆序但st1的倒数第二等于st2的top，实现了队列删除一个的元素

‘’javatypedef struct {
int* stack1;
int* stack2;
int rear;
int front;

} CQueue;

CQueue* cQueueCreate() {
CQueue* obj = (CQueue)malloc(sizeof(CQueue));
obj->stack1 = (int)malloc(1000sizeof(int));
obj->stack2 = (int)malloc(1000*sizeof(int));
obj->rear = -1;
obj->front = -1;
return obj;

}

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

int cQueueDeleteHead(CQueue* obj) {
if(obj->front -1){
if(obj->rear -1){
return -1;//表示两个栈都为空
}
while(obj->rear >= 0){
obj->stack2[++(obj->front)] = obj->stack1[(obj->rear)–];
}
}
int value = obj->stack2[(obj->front)–];
return value;
}

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

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

int param_2 = cQueueDeleteHead(obj);
cQueueFree(obj);
*/
‘’

0 赞同 0 条回复

c 普通 2023年8月15日下午3:28

模拟队列

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

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

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

0 赞同 0 条回复

JustRtn 普通 2023年8月15日下午3:07

// 模拟队列
class CQueue {
public:
CQueue() {

}

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

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

private:
std::stack s1;
std::stack s2;
};

0 赞同 0 条回复

行动派小彩笔普通 2023年8月15日下午2:31

// 两个栈模拟队列的先进先出
class CQueue {
        stack<int> stack1;
        stack<int> stack2;
    public:
        CQueue() {

        }

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

        int deleteHead() {
            int val=-1;
            if(!stack2.empty())
            {
                val = stack2.top();
                stack2.pop();

            }
            else if(!stack1.empty())
            {

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

0 赞同 0 条回复

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

共以下 34 个回答

使用两个栈的目的是，这种方式刚好能模拟成队列的出入栈方式

思路

解题方法

复杂度

时间复杂度:

空间复杂度:

Code

Your CQueue object will be instantiated and called as such:

obj = CQueue()

obj.appendTail(value)

param_2 = obj.deleteHead()

# 回答此问题取消回复

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

共以下 34 个回答

使用两个栈的目的是，这种方式刚好能模拟成队列的出入栈方式

思路

解题方法

复杂度

时间复杂度:

空间复杂度:

Code

Your CQueue object will be instantiated and called as such:

obj = CQueue()

obj.appendTail(value)

param_2 = obj.deleteHead()

# 回答此问题 取消回复

# 回答此问题取消回复