力扣：225. 用队列实现栈

绝地灬酷狼 2024-03-25 01:26 52阅读 0赞

**题目链接：**  
[225. 用队列实现栈][225.]  
![在这里插入图片描述][ea82d88490414b9398c8b9d2491fd821.png]  
**思路：**  
队列 是 `先进先出`，栈 是 `后进先出`，要用队列实现栈，那么就要使用`两个队列`完成后进先出的操作。

栈的结构设计就是两个队列 `q1`、`q2`。

而实现栈，我们的重点就在于 `后进先出`。

那么可以使用这样的思想：

我们需要时刻需要保持`一个队列为空`。

入数据时，往不为空的队列入数据，如果两个队列都为空，则入任意一个。

出数据时，将不为空的队列中的元素转移到空队列中直到队列中元素只剩一个，出栈原先非空队列的数据，原先非空队列变为空，出栈数据就是模拟栈的栈顶数据。

其他接口的实现相对比较简单，走读代码就可以看懂。

typedef int QDatatype;
    
    typedef struct QNode
    {
        
        struct QNode* next;
        QDatatype data;
    }QNode;
    
    typedef struct Queue
    {
        
        QNode* head;
        QNode* tail;
        int size;
    }Queue;
    
    typedef struct 
    {
        
        Queue q1;
        Queue q2;
    } MyStack;
    
    void QueueInit(Queue* pq)
    {
        
        assert(pq);
        pq->head=pq->tail=NULL;
        pq->size=0;
    }
    
    void QueueDestroy(Queue* pq)
    {
        
        assert(pq);
        QNode* cur=pq->head;
        while(cur)
        {
        
            cur=pq->head->next;
            free(pq->head);
            pq->head=cur;
        }
        pq->head=pq->tail=NULL;
        pq->size=0;
    }
    void QueuePush(Queue* pq,QDatatype x)
    {
        
        assert(pq);
        QNode* newnode=(QNode*)malloc(sizeof(QNode));
        if(newnode==NULL)
        {
        
            perror("malloc fail");
            return;
        }
        newnode->data=x;
        newnode->next=NULL;
        
        if(pq->head==NULL)
        {
        
            assert(pq->tail==NULL);
            pq->head=pq->tail=newnode;
        }
        else
        {
        
            pq->tail->next=newnode;
            pq->tail=newnode;
        }
        pq->size++;
    }
    
    void QueuePop(Queue* pq)
    {
        
        assert(pq);
        QNode* tmp=pq->head->next;
        free(pq->head);
        pq->head=tmp;
    
        if(pq->head==NULL) 
        {
        
            pq->tail=NULL;
        }
        pq->size--;
    }
    
    int QueueSize(Queue* pq)
    {
        
        assert(pq);
        return pq->size;
    }
    
    bool QueueEmpty(Queue* pq)
    {
        
        assert(pq);
        return pq->size==0;
    }
    
    QDatatype QueueFront(Queue* pq)
    {
        
        assert(pq);
        assert(!QueueEmpty(pq));
        return pq->head->data;
    }
    
    QDatatype QueueBack(Queue* pq)
    {
        
        assert(pq);
        assert(!QueueEmpty(pq));
        return pq->tail->data;
    }
    
    
    MyStack* myStackCreate() 
    {
        
        MyStack* pts=(MyStack*)malloc(sizeof(MyStack));
        if(pts==NULL)
        {
        
            perror("malloc fail");
            return NULL;
        }
        QueueInit(&pts->q1);
        QueueInit(&pts->q2);
        return pts;
    }
    
    void myStackPush(MyStack* obj,int x)
    {
        
        if(!QueueEmpty(&obj->q1))
            QueuePush(&obj->q1, x);
        else
            QueuePush(&obj->q2, x);
    }
    
    int myStackPop(MyStack* obj) 
    {
        
        Queue* empty=&obj->q1;
        Queue* nonempty=&obj->q2;
        if(!QueueEmpty(&obj->q1))
        {
        
            empty=&obj->q2;
            nonempty=&obj->q1;
        }
    
        //倒数据
        while(QueueSize(nonempty)>1)
        {
        
            QueuePush(empty,QueueFront(nonempty));
            QueuePop(nonempty);
        }
        int top=QueueFront(nonempty);
        QueuePop(nonempty);
        return top;
    }
    
    int myStackTop(MyStack* obj) 
    {
        
        if(!QueueEmpty(&obj->q1))
            return QueueBack(&obj->q1);
        else
            return QueueBack(&obj->q2);
    }
    
    bool myStackEmpty(MyStack* obj) 
    {
           
        return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
    }
    
    void myStackFree(MyStack* obj) 
    {
        
        QueueDestroy(&obj->q1);
        QueueDestroy(&obj->q2);
        free(obj);
    }
    
    /**
     * Your MyStack struct will be instantiated and called as such:
     * MyStack* obj = myStackCreate();
     * myStackPush(obj, x);
     
     * int param_2 = myStackPop(obj);
     
     * int param_3 = myStackTop(obj);
     
     * bool param_4 = myStackEmpty(obj);
     
     * myStackFree(obj);
    */

![在这里插入图片描述][6d6851c19cfd47c3ba7dbf29a6efacec.png]

[225.]: https://leetcode.cn/problems/implement-stack-using-queues/
[ea82d88490414b9398c8b9d2491fd821.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9082360c81e546da89f745cceea2497f.png
[6d6851c19cfd47c3ba7dbf29a6efacec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/80cc5aca444b45f5a3361238c129f810.png