【数据结构】用栈实现队列

前言：本节博客分享了用栈实现队列效果的思路以及代码，有需要借鉴即可。

1.题目及链接

LINK

2.思路分析

如果要用栈实现队列，我们直到栈是先入后出的一个效果，所以我们可以用两个栈，这样逆转两次数不就是入栈之前数组的顺序嘛。下面是一些图辅助理解：

3.代码示例

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

//用数组的方式实现栈结构
typedef int STDateType;
typedef struct Stack
{
	STDateType* arr;
	int top;
	int capacity;
}ST;

//初始化与销毁
void StackInit(ST* ps);
void StackDestroy(ST* ps);

//入栈出栈
void StackPush(ST* ps,STDateType x);
STDateType StackTop(ST* ps);
void StackPop(ST* ps);

//统计与判断
bool StackEmpty(ST* ps);
int StackSize(ST* ps);

void StackInit(ST* ps)
{
	assert(ps);

	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

void StackDestroy(ST* ps)
{
	assert(ps);

	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
	ps = NULL;
}

void StackPush(ST* ps, STDateType x)
{
	assert(ps);
	
	if (ps->capacity == ps->top)
	{
		//初始值的情况
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDateType* temp = (STDateType*)realloc(ps->arr, newcapacity * sizeof(STDateType));
		if (temp == NULL)
		{
			perror("malloc fail!");
			exit(-1);
		}
		ps->arr = temp;
		ps->capacity = newcapacity;
	}

	ps->arr[ps->top++] = x;
}

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	ps->top--;
}


STDateType StackTop(ST* ps)
{
	assert(ps);

	return ps->arr[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 pushtack;
    ST poptack;
} MyQueue;


MyQueue* myQueueCreate() {
    //首先要创建一个队列结构体
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    
    //对队列结构体中的栈做初始化调整
    StackInit(&obj->pushtack);
    StackInit(&obj->poptack);

    //返回
    return obj;
}

//将元素 x 推到队列的末尾
void myQueuePush(MyQueue* obj, int x) {
    //插入数据
    StackPush(&obj->pushtack,x);
}

//返回队列开头的元素
int myQueuePeek(MyQueue* obj) {
    //分两种情况:1.poptack为空2.poptack不为空
    if(StackEmpty(&obj->poptack))//为空需要导数据
    {
        while(!StackEmpty(&obj->pushtack))
        {
            int top = StackTop(&obj->pushtack);//取出push数据
            StackPop(&obj->pushtack);//删除pop数据
            StackPush(&obj->poptack,top);//放入push
        }
    }
    //poptack不为空
    return StackTop(&obj->poptack);
}

//从队列的开头移除并返回元素
int myQueuePop(MyQueue* obj) {
    int front = myQueuePeek(obj);//取出
    StackPop(&obj->poptack);//删除
    return front;//返回
}



//如果队列为空，返回 true ；否则，返回 false
bool myQueueEmpty(MyQueue* obj) {//两个都为空
    return StackEmpty(&obj->pushtack)&&StackEmpty(&obj->poptack);
}

//释放
void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->pushtack);
    StackDestroy(&obj->poptack);
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(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

完。