Leetcode232.用栈实现队列

本专栏内容为：leetcode刷题专栏，记录了leetcode热门题目以及重难点题目的详细记录

💓博主csdn个人主页：小小unicorn
⏩专栏分类：Leetcode
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

题目描述

题目来源：Leetcode232.用栈实现队列

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

实现 MyQueue 类：

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

解题思路：

使用两个栈，第一个栈只用于数据的输入，第二个栈只用于数据的输出。当需要输出数据，但第二个栈为空时，先将第一个栈中的数据一个一个导入到第二个栈，然后第二个栈再输出数据即可。

这样就能够模拟实现一个队列了，即先输入的数据先输出。

代码解决：

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include

typedef char STDataType;//栈中存储的元素类型

typedef struct Stack
{
	STDataType* a;//栈
	int top;//栈顶
	int capacity;//容量，方便增容
}Stack;

//初始化栈
void StackInit(Stack* pst)
{
	assert(pst);

	pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);//初始化栈可存储4个元素
	pst->top = 0;//初始时栈中无元素，栈顶为0
	pst->capacity = 4;//容量为4
}

//销毁栈
void StackDestroy(Stack* pst)
{
	assert(pst);

	free(pst->a);//释放栈
	pst->a = NULL;//及时置空
	pst->top = 0;//栈顶置0
	pst->capacity = 0;//容量置0
}

//入栈
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);

	if (pst->top == pst->capacity)//栈已满，需扩容
	{
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		pst->a = tmp;
		pst->capacity *= 2;//栈容量扩大为原来的两倍
	}
	pst->a[pst->top] = x;//栈顶位置存放元素x
	pst->top++;//栈顶上移
}

//检测栈是否为空
bool StackEmpty(Stack* pst)
{
	assert(pst);

	return pst->top == 0;
}

//出栈
void StackPop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));//检测栈是否为空

	pst->top--;//栈顶下移
}

//获取栈顶元素
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));//检测栈是否为空

	return pst->a[pst->top - 1];//返回栈顶元素
}

//获取栈中有效元素个数
int StackSize(Stack* pst)
{
	assert(pst);

	return pst->top;//top的值便是栈中有效元素的个数
}
/*---以上代码是栈的基本功能实现，以下代码是题解主体部分---*/

typedef struct
{
	Stack PushST;//插入数据时用的栈
	Stack PopST;//删除数据时用的栈
}MyQueue;

/** Initialize your data structure here. */
MyQueue* myQueueCreate()
{
	//申请一个队列类型
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	StackInit(&obj->PopST);//初始化PopST
	StackInit(&obj->PushST);//初始化PushST

	return obj;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x)
{
	//插入数据，向PushST插入
	StackPush(&obj->PushST,x);
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj)
{
	popST为空时，需先将pushST中数据导入popST
	if (StackEmpty(&obj->PopST))
	{
		将pushST数据全部导入popST
		while (!StackEmpty(&obj->PushST))
		{
			StackPush(&obj->PopST, StackTop(&obj->PushST));
			StackPop(&obj->PushST);
		}
	}
	//返回PopST栈顶的数据
	return StackTop(&obj->PopST);
}


/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj)
{
	int top = myQueuePeek(obj);
     //删除数据，删除PopST栈顶的元素	
	StackPop(&obj->PopST);
	return top;
}


/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj)
{
	//两个栈均为空，则队列为空
	return StackEmpty(&obj->PopST) && StackEmpty(&obj->PushST);
}

void myQueueFree(MyQueue* obj)
{
	//先释放掉两个栈
	StackDestroy(&obj->PopST);
	StackDestroy(&obj->PushST);
	//在释放掉队列的结构体类型
	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

结果与总结：

通过所有示例，问题得到解决。