菜鸟追梦旅行

这个屌丝很懒，什么也没留下！

热门标签

【LeetCode例232】【C语言】用栈实现队列~动画超详细解读!_c语言用栈实现队列

作者：菜鸟追梦旅行 | 2024-06-09 05:25:12

踩

c语言用栈实现队列

0 技术需求

了解并实现栈和队列,熟悉栈和队列的基本逻辑
这里挂上链接<队列> <栈>

1 题目介绍

1.1 看题

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作**（push、pop、peek、empty）**：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

这里挂上题目链接: 232.用栈实现队列

1.2 分析

这道题目其实就是让我们用栈的基本功能以及函数实现队列的基本功能及函数

myQueueCreate - 创建MyQueue
myQueuePush - MyQueue入队
myQueuePop - MyQueue出队
myQueuePeek - MyQueue取队头
myQueueEmpty - MyQueue判空
myQueueFree - myQueue释放

比较重要的一点就是我们使用C实现,所以我们需要先手搓一遍栈的函数才能写这道题(当然完全理解过栈和队列的话CV一下也不是不行(doge))

2 解题思路

2.1 基本思想

我们都知道,如果给一串数据,全部入栈之后再出栈,出栈的数据的顺序会反过来,而题目要求我们使用两个栈实现队列,我们就可以利用上进栈再出栈会逆置的特性

2.2 实现思路1(非最优解)

2.2.1 定义MyQueue

这里我们在 MyQueue 结构体里定义两个分别指向栈st1 和栈st2 的指针

st1: 用于先存放入"队列"的数据
st2: 用于逆置st1的数据

//定义MyQueue
typedef struct 
{
    ST* st1;
    ST* st2;
} MyQueue;
1
2
3
4
5
6

2.2.2 myQueue的初始化

题目要求在函数内部创建 MyQueue ,所以我们只能把内存开辟在堆区上才能把空间保留下来,如果放在栈区上,函数一结束 MyQueue 就被自动销毁了( st1 和 st2 都是指针,开辟完别忘了初始化,虽然这里用的 calloc 但还是自己再初始化一遍保险保险)

	MyQueue* pmq = (MyQueue*)calloc(1, sizeof(MyQueue));
	pmq->st1 = NULL;
	pmq->st2 = NULL;
1
2
3

既然 st1 和 st2 都是指针,所以也需要初始化一下这俩栈,直接调用现成的函数就行

    pmq->st1 = (ST*)calloc(1, sizeof(ST));
    pmq->st2 = (ST*)calloc(1, sizeof(ST));

    STInit(pmq->st1);
    STInit(pmq->st2);
1
2
3
4
5

别忘了返回创建的MyQueue

    return pmq;
1

所以 myQueueCreate 函数就长这样

//创建MyQueue
MyQueue* myQueueCreate() 
{
    MyQueue* pmq = (MyQueue*)calloc(1, sizeof(MyQueue));
    pmq->st1 = NULL;
    pmq->st2 = NULL;

    pmq->st1 = (ST*)calloc(1, sizeof(ST));
    pmq->st2 = (ST*)calloc(1, sizeof(ST));

    STInit(pmq->st1);
    STInit(pmq->st2);

    return pmq;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.2.3 myQueue 的入"队列"

我们说 st1 只负责接收入"队列",要出"队列"再通过 st2 逆置一下,所以我们直接把数据无脑放进 st1 就行

//MyQueue入队
void myQueuePush(MyQueue* obj, int x) 
{
    STPush(obj->st1, x);
}
1
2
3
4
5

2.2.4 myQueue 的出"队列"

我们知道出队列需要把 st1 的所有数据再入一遍栈st2 把整个数据逆序一遍才能"出队"一个数据,所以这里只要 st1 不是空,我们就不断往 st2 输出数据

    while(!STEmpty(obj->st1))
    {
        STPush(obj->st2, STTop(obj->st1));
        STPop(obj->st1);
    }
1
2
3
4
5

因为题目要求要有返回值,此时栈st2 的栈顶作为出"队列"的"队头",我们把"队头"的值暂时存到 ret 里,方便返回其值

	int ret = STTop(obj->st2);
1

然后让 st2 出栈一个值,也就是栈顶那个值,即"出队"一次

	STPop(obj->st2);
1

最后把 st2 剩余的值重新放回 st1 中暂存,并返回 ret

    while(!STEmpty(obj->st2))
    {
        STPush(obj->st1, STTop(obj->st2));
        STPop(obj->st2);
    }
    return ret;
1
2
3
4
5
6

那么这就是 MyQueue 的一次完整的"出队"了

//MyQueue出队
int myQueuePop(MyQueue* obj) 
{
    while(!STEmpty(obj->st1))
    {
        STPush(obj->st2, STTop(obj->st1));
        STPop(obj->st1);
    }
    int ret = STTop(obj->st2);
    STPop(obj->st2);
    while(!STEmpty(obj->st2))
    {
        STPush(obj->st1, STTop(obj->st2));
        STPop(obj->st2);
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.2.5 MyQueue取队头

"取队头"的步骤其实和"出队"差不多,只是中间少了一步让 st2 栈顶出栈的内容,也就导致我只是取了 st2栈顶的值而已, 取完值之后 st2 里的内容全都原封不动地还给 st1 了
一样的把 st1 的所有值入一遍 st2

    while(!STEmpty(obj->st1))
    {
        STPush(obj->st2, STTop(obj->st1));
        STPop(obj->st1);
    }
1
2
3
4
5

一样的把"队头"的值给临时变量 ret

	int ret = STTop(obj->st2);
1

最后又是一样的把 st2 的所有值还给 st1 并且返回 ret

    while(!STEmpty(obj->st2))
    {
        STPush(obj->st1, STTop(obj->st2));
        STPop(obj->st2);
    }
    return ret;
1
2
3
4
5
6

以下是MyQueue取队头的完整代码

//MyQueue取队头
int myQueuePeek(MyQueue* obj) 
{
    while(!STEmpty(obj->st1))
    {
        STPush(obj->st2, STTop(obj->st1));
        STPop(obj->st1);
    }
    int ret = STTop(obj->st2);
    while(!STEmpty(obj->st2))
    {
        STPush(obj->st1, STTop(obj->st2));
        STPop(obj->st2);
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.2.6 MyQueue判空

我们所有的数据全部存在 st1 里,除了需要逆置的时候, st2 里头一般都是没有任何内容的,所以我们只需要单纯的给 st1 判空就行了

//MyQueue判空
bool myQueueEmpty(MyQueue* obj) 
{
    return STEmpty(obj->st1);
}
1
2
3
4
5

2.2.7 MyQueue的销毁

这里我们需先把 st1 和 st2 先销毁,再销毁 MyQueue(obj) 的空间,如果先销毁 MyQueue 的话,我们就找不到 st1 和 st2 了,也就销毁不了这俩栈了

//MyQueue释放
void myQueueFree(MyQueue* obj) 
{
    STDestroy(obj->st1);
    STDestroy(obj->st2);

    obj->st1 = NULL;
    obj->st2 = NULL;

    free(obj);
}
1
2
3
4
5
6
7
8
9
10
11

2.2.8 完整动画

请添加图片描述

2.3 实现思路2(最优解)

区别于思路1,思路2不需要频繁让数据在 st1 和 st2 之间来回跳
一样的让 st1 专注"入队", st2 专注"出队",区别在于要等 st2 "出队"完才向其补充数据
其他的函数就如法炮制就行了,这里着重讲取"队头"和"出队"

2.3.1 MyQueue取队头

这里取完队头之后不把 st2 的数据挪回 st1 里,方便下次挪动或者删除

//MyQueue取队头
int myQueuePeek(MyQueue* obj) 
{
    if(STEmpty(obj->st2))//判断 st2 有没有数据,有数据就不动,没数据就把 st1 的数据挪过来
    {
        while(!STEmpty(obj->st1))
        {
            STPush(obj->st2, STTop(obj->st1));
            STPop(obj->st1);
        }
    }
    int ret = STTop(obj->st2);
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.3.2 MyQueue出队

同样的,出队之后不把 st2 的数据挪回 st1 里

注意:这里动画先执行了三次出队,然后执行了一次入队,最后执行了三次出队

请添加图片描述

//MyQueue出队
int myQueuePop(MyQueue* obj) 
{
    if(STEmpty(obj->st2))//判断 st2 有没有数据,有数据就不动,没数据就把 st1 的数据挪过来
    {
        while(!STEmpty(obj->st1))
        {
            STPush(obj->st2, STTop(obj->st1));
            STPop(obj->st1);
        }
    }
    int ret = STTop(obj->st2);
    STPop(obj->st2);
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.3.3 完整动画

请添加图片描述

3 完整实现代码

因为这里是用C写这道题,所以代码前面一定得加上栈的所有内容哦

3.1 方法1

//类型定义
typedef int DataType;

typedef struct stack
{
	DataType* pdata;
	int top;
	int capa;
}ST;


//函数定义

//栈的扩容
void CheckCapa(ST* pst);

//获取栈顶数据
DataType STTop(ST* pst);

//栈的判空
bool STEmpty(ST* pst);

//查看数据量
int STSize(ST* pst);

//栈的初始化
void STInit(ST* pst);

//栈的删除
void STDestroy(ST* pst);

//压栈
void STPush(ST* pst, DataType data);

//出栈
void STPop(ST* pst);

//函数定义

//栈的扩容
void CheckCapa(ST* pst)
{
	assert(pst);
	if (pst->top + 1 == pst->capa)
	{
		DataType* tmp = (DataType*)realloc(pst->pdata, 2 * pst->capa * sizeof(DataType));
		if (tmp == NULL)
		{
			perror("CheckCapa::realloc");
			exit(1);
		}
		else
		{
			pst->pdata = tmp;
		}
		pst->capa = 2 * pst->capa;
	}
}

//获取栈顶数据
DataType STTop(ST* pst)
{
	assert(pst);
	return pst->pdata[pst->top];
}

//栈的判空
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top + 1 == 0;
}

//查看数据量
int STSize(ST* pst)
{
	assert(pst);
	return pst->top + 1;
}

//栈的初始化
void STInit(ST* pst)
{
	assert(pst);

	pst->pdata = (DataType*)calloc(4, sizeof(DataType));
	if (pst->pdata == NULL)
	{
		perror("STInit::calloc");
		exit(1);
	}
	pst->top = -1;
	pst->capa = 4;
}

//栈的删除
void STDestroy(ST* pst)
{
	free(pst->pdata);
	pst->pdata = NULL;
	pst->capa = 0;
	pst->top = -1;
}

//压栈
void STPush(ST* pst, DataType data)
{
	CheckCapa(pst);
	(pst->top)++;
	pst->pdata[pst->top] = data;
}

//出栈
void STPop(ST* pst)
{
	if (STEmpty(pst))
	{
		return;
	}
	else
	{
		(pst->top)--;
	}
}

//----------------------------------------------------------------------------------------------------

//定义MyQueue
typedef struct 
{
    ST* st1;
    ST* st2;
} MyQueue;


//创建MyQueue
MyQueue* myQueueCreate() 
{
    MyQueue* pmq = (MyQueue*)calloc(1, sizeof(MyQueue));
    pmq->st1 = NULL;
    pmq->st2 = NULL;

    pmq->st1 = (ST*)calloc(1, sizeof(ST));
    pmq->st2 = (ST*)calloc(1, sizeof(ST));

    STInit(pmq->st1);
    STInit(pmq->st2);

    return pmq;
}

//MyQueue入队
void myQueuePush(MyQueue* obj, int x) 
{
    STPush(obj->st1, x);
}

//MyQueue出队
int myQueuePop(MyQueue* obj) 
{
    while(!STEmpty(obj->st1))
    {
        STPush(obj->st2, STTop(obj->st1));
        STPop(obj->st1);
    }
    int ret = STTop(obj->st2);
    STPop(obj->st2);
    while(!STEmpty(obj->st2))
    {
        STPush(obj->st1, STTop(obj->st2));
        STPop(obj->st2);
    }
    return ret;
}

//MyQueue取队头
int myQueuePeek(MyQueue* obj) 
{
    while(!STEmpty(obj->st1))
    {
        STPush(obj->st2, STTop(obj->st1));
        STPop(obj->st1);
    }
    int ret = STTop(obj->st2);
    while(!STEmpty(obj->st2))
    {
        STPush(obj->st1, STTop(obj->st2));
        STPop(obj->st2);
    }
    return ret;
}

//MyQueue判空
bool myQueueEmpty(MyQueue* obj) 
{
    return STEmpty(obj->st1);
}

//MyQueue释放
void myQueueFree(MyQueue* obj) 
{
    STDestroy(obj->st1);
    STDestroy(obj->st2);

    obj->st1 = NULL;
    obj->st2 = NULL;

    free(obj);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209

3.1 方法2

typedef int DataType;

typedef struct stack
{
	DataType* pdata;
	int top;
	int capa;
}ST;


//函数定义

//栈的扩容
void CheckCapa(ST* pst);

//获取栈顶数据
DataType STTop(ST* pst);

//栈的判空
bool STEmpty(ST* pst);

//查看数据量
int STSize(ST* pst);

//栈的初始化
void STInit(ST* pst);

//栈的删除
void STDestroy(ST* pst);

//压栈
void STPush(ST* pst, DataType data);

//出栈
void STPop(ST* pst);

//函数定义

//栈的扩容
void CheckCapa(ST* pst)
{
	assert(pst);
	if (pst->top + 1 == pst->capa)
	{
		DataType* tmp = (DataType*)realloc(pst->pdata, 2 * pst->capa * sizeof(DataType));
		if (tmp == NULL)
		{
			perror("CheckCapa::realloc");
			exit(1);
		}
		else
		{
			pst->pdata = tmp;
		}
		pst->capa = 2 * pst->capa;
	}
}

//获取栈顶数据
DataType STTop(ST* pst)
{
	assert(pst);
	return pst->pdata[pst->top];
}

//栈的判空
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top + 1 == 0;
}

//查看数据量
int STSize(ST* pst)
{
	assert(pst);
	return pst->top + 1;
}

//栈的初始化
void STInit(ST* pst)
{
	assert(pst);

	pst->pdata = (DataType*)calloc(4, sizeof(DataType));
	if (pst->pdata == NULL)
	{
		perror("STInit::calloc");
		exit(1);
	}
	pst->top = -1;
	pst->capa = 4;
}

//栈的删除
void STDestroy(ST* pst)
{
	free(pst->pdata);
	pst->pdata = NULL;
	pst->capa = 0;
	pst->top = -1;
}

//压栈
void STPush(ST* pst, DataType data)
{
	CheckCapa(pst);
	(pst->top)++;
	pst->pdata[pst->top] = data;
}

//出栈
void STPop(ST* pst)
{
	if (STEmpty(pst))
	{
		return;
	}
	else
	{
		(pst->top)--;
	}
}

//----------------------------------------------------------------------------------------------------

//定义MyQueue
typedef struct 
{
    ST* st1;
    ST* st2;
} MyQueue;


//创建MyQueue
MyQueue* myQueueCreate() 
{
    MyQueue* pmq = (MyQueue*)calloc(1, sizeof(MyQueue));
    pmq->st1 = NULL;
    pmq->st2 = NULL;

    pmq->st1 = (ST*)calloc(1, sizeof(ST));
    pmq->st2 = (ST*)calloc(1, sizeof(ST));

    STInit(pmq->st1);
    STInit(pmq->st2);

    return pmq;
}

//MyQueue入队
void myQueuePush(MyQueue* obj, int x) 
{
    STPush(obj->st1, x);
}

//MyQueue出队
int myQueuePop(MyQueue* obj) 
{
    if(STEmpty(obj->st2))
    {
        while(!STEmpty(obj->st1))
        {
            STPush(obj->st2, STTop(obj->st1));
            STPop(obj->st1);
        }
    }
    int ret = STTop(obj->st2);
    STPop(obj->st2);
    return ret;
}

//MyQueue取队头
int myQueuePeek(MyQueue* obj) 
{
    if(STEmpty(obj->st2))
    {
        while(!STEmpty(obj->st1))
        {
            STPush(obj->st2, STTop(obj->st1));
            STPop(obj->st1);
        }
    }
    int ret = STTop(obj->st2);
    return ret;
}

//MyQueue判空
bool myQueueEmpty(MyQueue* obj) 
{
    return (STEmpty(obj->st1) && STEmpty(obj->st2));
}

//MyQueue释放
void myQueueFree(MyQueue* obj) 
{
    STDestroy(obj->st1);
    STDestroy(obj->st2);

    obj->st1 = NULL;
    obj->st2 = NULL;

    free(obj);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204

佬!都看到这了,如果觉得有帮助的话一定要点赞啊佬 >v< !!!

放个卡密在这,感谢各位能看到这儿啦!

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/692791

【LeetCode例232】【C语言】用栈实现队列~动画超详细解读!_c语言 用栈实现队列

0 技术需求

1 题目介绍

1.1 看题

1.2 分析

2 解题思路

2.1 基本思想

2.2 实现思路1(非最优解)

2.2.1 定义MyQueue

2.2.2 myQueue的初始化

2.2.3 myQueue 的入"队列"

2.2.4 myQueue 的出"队列"

2.2.5 MyQueue取队头

2.2.6 MyQueue判空

2.2.7 MyQueue的销毁

2.2.8 完整动画

2.3 实现思路2(最优解)

2.3.1 MyQueue取队头

2.3.2 MyQueue出队

2.3.3 完整动画

3 完整实现代码

3.1 方法1

3.1 方法2

【LeetCode例232】【C语言】用栈实现队列~动画超详细解读!_c语言用栈实现队列