[链表OJ题 8] 用栈实现队列，没想到你小子的基础这么好，这么快就做对了

阳光穿透心脏的1/2处 2023-10-10 22:26 31阅读 0赞

**目录**

题目来源：

代码实现：

思路分析：

实现过程：

--------------------

## 题目来源： ##

[力扣 - 232.用栈实现队列][- 232.]

**题目描述：**

![c7e09bfe03f025ae2ab579397c2be14f.png][]

## 代码实现： ##

我们这里的栈已经写好了，如果对栈还不是很懂的可以看看这篇文章：[CSDN - \[数据结构 -- C语言\] 栈（stack）][CSDN - _ -- C_ _stack]

typedef int STDataType;
    typedef struct Stack
    {
    	STDataType* a;
    	int top;		// 栈顶
    	int capacity;  // 容量 
    }Stack;
    // 初始化栈 
    void StackInit(Stack* ps);
    // 入栈 
    void StackPush(Stack* ps, STDataType data);
    // 出栈 
    void StackPop(Stack* ps);
    // 获取栈顶元素 
    STDataType StackTop(Stack* ps);
    // 获取栈中有效元素个数 
    int StackSize(Stack* ps);
    // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
    int StackEmpty(Stack* ps);
    // 销毁栈 
    void StackDestroy(Stack* ps);
    // 初始化栈 
    void StackInit(Stack* ps)
    {
    	assert(ps);
    
    	ps->a = NULL;
    	//ps->top = -1;//top 指栈顶数据
    	ps->top = 0;//top 指栈顶数据的下一个位置
    	ps->capacity = 0;
    }
    // 入栈 
    void StackPush(Stack* ps, STDataType data)
    {
    	assert(ps);
    
    	if (ps->capacity == ps->top)
    	{
    		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
    		if (tmp == NULL)
    		{
    			perror("realloc fail:");
    			return;
    		}
    		ps->a = tmp;
    		ps->capacity = newcapacity;
    	}
    
    	ps->a[ps->top] = data;
    	ps->top++;
    }
    // 出栈 
    void StackPop(Stack* ps)
    {
    	assert(ps);
    	assert(!StackEmpty(ps));
    
    	ps->top--;
    }
    // 获取栈顶元素 
    STDataType StackTop(Stack* ps)
    {
    	assert(ps);
    	assert(!StackEmpty(ps));
    
    	return ps->a[ps->top-1];
    }
    // 获取栈中有效元素个数 
    int StackSize(Stack* ps)
    {
    	assert(ps);
    
    	return ps->top;
    }
    // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
    int StackEmpty(Stack* ps)
    {
    	assert(ps);
    
    	if (0 == ps->top)
    		return 1;
    	else
    		return 0;
    }
    // 销毁栈 
    void StackDestroy(Stack* ps)
    {
    	assert(ps);
    
    	free(ps->a);
    	ps->a = NULL;
    	ps->capacity = 0;
    	ps->top = 0;
    }
    
    typedef struct {
        Stack push;
        Stack pop;
    } MyQueue;
    
    MyQueue* myQueueCreate() {
        MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
        StackInit(&obj->push);
        StackInit(&obj->pop);
    
        return obj;
    }
    
    void myQueuePush(MyQueue* obj, int x) {
        StackPush(&obj->push, x);
    }
    
    int myQueuePop(MyQueue* obj) {
        int front = myQueuePeek(obj);
        StackPop(&obj->pop);
        return front;
    }
    
    int myQueuePeek(MyQueue* obj) {
        if(StackEmpty(&obj->pop))
        {
            while(!StackEmpty(&obj->push))
            {
                StackPush(&obj->pop, StackTop(&obj->push));
                StackPop(&obj->push);
            }
        }
        return StackTop(&obj->pop);
    }
    
    bool myQueueEmpty(MyQueue* obj) {
        return StackEmpty(&obj->push) && StackEmpty(&obj->pop);
    }
    
    void myQueueFree(MyQueue* obj) {
        StackDestroy(&obj->push);
        StackDestroy(&obj->pop);
    }

## 思路分析： ##

我们知道队列的特性：先入先出；栈的特性：先入后出。因此我们定义两个栈，一个是入元素的栈（push栈），另一个是出元素的栈（pop栈）。当我们要入队的时候就把元素直接入到 push栈中，出队的时候先把 push栈 中的元素全部放入 pop栈 中，将 pop栈 的栈顶元素出栈就能实现队列的特性。

此题的本质是以栈的特性来实现队列的特性。

![5613ef0adb1ac32b05a0c741895ddd14.png][]

### 实现过程： ###

1、我们先将栈的所有接口都写出来。然后我们创建两个栈，一个是实现入队功能的栈（push栈），另一个是实现出队功能的栈（pop栈）；

2、我们要实现入队的时候，将元素入到 push栈 中，要出队的时候先将 push栈 中的元素转到 pop栈 中，然后出pop栈 这样就可以实现出队时出的是队头元素；

3、在出队的时候我们先看 pop栈 中还有没有元素，要是有元素我们直接出 pop栈 中的栈顶元素就可以，如果没有就先将 push栈 中的元素转到 pop栈 中；入队的时候直接入到 push栈 中就可以。

对栈还不太明白的朋友可以参考**代码实现**那部分的 **栈** 的那篇文章。

![f58e645660c76c46c1364dc367335f79.png][]

\*\*\* 本篇结束 \*\*\*

[- 232.]: https://leetcode.cn/problems/implement-queue-using-stacks/
[c7e09bfe03f025ae2ab579397c2be14f.png]: https://img-blog.csdnimg.cn/img_convert/c7e09bfe03f025ae2ab579397c2be14f.png
[CSDN - _ -- C_ _stack]: https://blog.csdn.net/Ljy_cx_21_4_3/article/details/130734426?spm=1001.2014.3001.5502
[5613ef0adb1ac32b05a0c741895ddd14.png]: https://img-blog.csdnimg.cn/img_convert/5613ef0adb1ac32b05a0c741895ddd14.png
[f58e645660c76c46c1364dc367335f79.png]: https://img-blog.csdnimg.cn/img_convert/f58e645660c76c46c1364dc367335f79.png