题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
题目链接
用栈实现队列
思路分析
题目的意思是要用两个栈来模拟实现一个队列。仅可以用栈的基本功能实现队列的基本功能。所以需要创建两个栈。所以这两个栈st1，st2可用一个结构体包含。本质就是用两个后进先出的栈，来模拟一个先进先出的队列。
思路：
1.st2这个栈用来压栈，st1的作用：把st2的所有值压到st1中，然后经过st1出栈。这样就达到了队列先进先出的性质。
2.st2一直用来压栈。如果st1为空则将st2里面的值全都转移到st1，如果st1不为空，则继续出栈，知道st1为空为止。
代码实现
|
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
|
ypedef char STDataType;typedef struct Stack{ STDataType* a; int top; int capacity;}ST;//初始化结构体void StackInit(ST* ps);//销毁结构体void StackDestroy(ST* ps);//压栈void StackPush(ST* ps, STDataType x);//出栈void StackPop(ST* ps);//得到栈顶的值STDataType StackTop(ST* ps);//判断栈是否为空bool StackEmpty(ST* ps);//得到栈的长度int StackSize(ST* ps);//初始化结构体void StackInit(ST* ps){ assert(ps); ps->a = NULL; ps->capacity = 0; ps->top = 0;}//销毁结构体void StackDestroy(ST* ps){ assert(ps); free(ps->a); ps->a = NULL; ps->capacity = 0; ps->top = 0;}//压栈void StackPush(ST* ps, STDataType x){ assert(ps); if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* new = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity); if (new == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = new; ps->capacity = newcapacity; } ps->a[ps->top] = x; ps->top++;}void StackPop(ST* ps){ assert(ps); assert(ps->top > 0); ps->top--;}STDataType StackTop(ST* ps){ assert(ps); assert(ps->top>0); return ps->a[ps->top-1];}bool StackEmpty(ST* ps){ assert(ps); return ps->top == 0;}//得到栈的长度int StackSize(ST* ps){ assert(ps); return ps->top;}//创建了两个栈typedef struct { ST st1; ST st2;} MyQueue;//对两个栈进行初始化。MyQueue* myQueueCreate() { MyQueue* newQueue = (MyQueue*)malloc(sizeof(MyQueue)); assert(newQueue); StackInit(&newQueue->st1); StackInit(&newQueue->st2); return newQueue;}void myQueuePush(MyQueue* obj, int x) { assert(obj); StackPush(&obj->st2, x);}int myQueuePop(MyQueue* obj) { assert(obj); if(StackEmpty(&obj->st1)) { while(!StackEmpty(&obj->st2)) { StackPush(&obj->st1, StackTop(&obj->st2)); StackPop(&obj->st2); } } int top = 0; if(!StackEmpty(&obj->st1)) { top = StackTop(&obj->st1); StackPop(&obj->st1); } return top;}int myQueuePeek(MyQueue* obj) { assert(obj); if(StackEmpty(&obj->st1)) { while(!StackEmpty(&obj->st2)) { StackPush(&obj->st1, StackTop(&obj->st2)); StackPop(&obj->st2); } } if(!StackEmpty(&obj->st1)) { return StackTop(&obj->st1); } return 0;}bool myQueueEmpty(MyQueue* obj){ return StackEmpty(&obj->st1) && StackEmpty(&obj->st2);}void myQueueFree(MyQueue* obj) { StackDestroy(&obj->st1); StackDestroy(&obj->st2); free(obj);} |
到此这篇关于C语言用栈模拟实现队列问题详解的文章就介绍到这了,更多相关C语言 栈实现队列内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.csdn.net/qq2466200050/article/details/123843960
