力扣225 - 用队列实现栈【C/C++实现】

一、题目描述

示例 1：

输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示

• 1 <= x <= 9
• 最多调用100 次 push、pop、top 和 empty
• 每次调用 pop 和 top 都保证栈不为空

二、思路分析

好，看完题目的描述，我们来分析一下去求解这道题目

• 我们知道，栈与队列的原理刚好相反，对于栈是【FILO】，对于队列是【FIFO】。这就需要我们灵活地去使用这两种数据结构进行解题。**对于本题，我的思路是这样的：**因为需要用队列来实现栈，首先其实可以想到的是使用两个队列，互相倒来倒去出队数据，图示如下

1、结构声明与展开剖析

• 因为我使用的是C语言去解决这道题，所以无法使用STL中的queue来解决，于是就需要自己去写一个队列模拟【文末给出（链式队）】，这就会显得很麻烦，当然C++的代码我也会给出，我们主要讲授C语言的思维
• 首先的话就是使用一个大的结构体定义两个内部队列

typedef struct {
    Qu q1;
    Qu q2;
} MyStack;
1
2
3
4

• 因为我们使用时队列去模拟的栈，因此主接口还是对于栈的创建，因此需要为其开辟出一块空间来存储这两个队列，然后的话就是使用我们自己写的队列对这两个队列进行一个初始化。可以看到，对于两个队列，我没有定义成指针类型，不然的话对它们也要去开辟空间
• 此时只需要传入定义的这两个队列的地址即可

MyStack* myStackCreate() {
    MyStack* myStack = (MyStack *)malloc(sizeof(MyStack));
    QueueInit(&(myStack->q1));
    QueueInit(&(myStack->q2));

    return myStack;
}
1
2
3
4
5
6
7

可能还是有同学对这个结构不太能想象地出来，这里给出它的结构图

• 可以看到，这其实是一个三层嵌套的结构体，外层是题目给出的【MyStack】，然后是内层我们自己定义的两个链式队【q1】【q2】，而这两个链式队呢，又指向了一个单链表，所以对于这个结构来说还是比较复杂的，大家要理清这个结构

---

• 说完了整体结构的思想，接下去我们主要来讲讲出队和入队这两个操作。它们的思想都是围绕于一个空、一个非空来进行

2、入栈【入队思想】

• 入队其实很简单：也就是当哪个栈非空时，就往它那里入数据

//只往非空的队列中入数据
if(!QueueEmpty(&obj->q1))
    QueuePush(&obj->q1,x);
else
    QueuePush(&obj->q2,x);
1
2
3
4
5

3、出栈【出队思想】

• 对于出队来说比较复杂，我们在出队前需要提前去推算出哪个队列是空的，然后我的思路将队列的前【n - 1】个元素进行出队，然后将它们入队到另外的一个空的队列中，最后获取原先的队列中还剩下的一个元素，接着将其出队，这样就实现了栈的先进先出特性
• 然后我们来看看代码，首先的话就是去寻找出空和非空的两个队列，因为当后台程序调用到这个接口的时候就会传入这个【MyStack】，接着只需要去获取我们所定义的两个队列即可。
• 这里解释一下为什么可以这么去获取，其实应该写成这样【&（obj->q1）】，只是因为【->】的优先级高于【&】，所以加不加都是可以的；使用这个MyStack所定义的指针去取到q1，接着传入q1的地址给到指针进行一个接收，使得等式两遍等价即可

Qu* EmptyQu = &obj->q1;
Qu* nonEmptyQu = &obj->q2;
if(!QueueEmpty(&obj->q1))
{       //必定是一个空，一个非空
    EmptyQu = &obj->q2;
    nonEmptyQu = &obj->q1;
}
1
2
3
4
5
6
7

• 判断出谁为空，谁不空之后，我们就可以去进行一个出队入队的操作了，最后出得只剩下一个数据即可

//首先将非空队列中的前n-1个元素都出队
while(QueueSize(nonEmptyQu) > 1)
{
    QueuePush(EmptyQu,QueueFront(nonEmptyQu));  //每次取出非空队列的头元素
    QueuePop(nonEmptyQu);      //出队队头元素
}
1
2
3
4
5
6

• 然后获取到这个数据返回，再将这个数据再出队即可，就达成了我们的目的

//此时非空队列中还剩一个元素，取出return即可
int front = QueueFront(nonEmptyQu);
QueuePop(nonEmptyQu);       //然后将此元素出队

return front;
1
2
3
4
5

4、获取栈顶元素【队列末尾】

• 因为我们使用的是队列来模拟栈，因此队列的最后一个元素即为栈的栈顶元素，此时就可以回忆到我们在实现队列的时候写了一个Back()的接口
• 此时只需要判断一下哪个队列不为空，取出这个队列的末尾元素返回即可

//返回非空队列的末尾元素
if(!QueueEmpty(&obj->q1))
    return QueueBack(&obj->q1);
else
    return QueueBack(&obj->q2);
1
2
3
4
5

---

5、逐步算法图解

• 我们再通过步步的算法图解来分析一下，加深对代码的理解

• 出队完成后继续入队，要找非空的队列入队

• 好，我们继续执行一次出队操作
  

• 回忆一下，第一次的数据是【1237】，说明7是最后一个入队的，于是实现了第一个出队；接着有入队一个【4】，也是先出了这个元素，这就实现了先进先出的原则

三、整体代码展示

💻C语言代码实现

• 题目代码使用的是C语言实现

typedef int QDataType;
typedef struct QueueNode {
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue {
	QNode* front;
	QNode* rear;
	size_t sz;
}Qu;


/*初始化队列*/
void QueueInit(Qu* q);
/*销毁队列*/
void QueueDestroy(Qu* q);
/*入队*/
void QueuePush(Qu* q, QDataType x);
/*获取队头*/
QDataType QueueFront(Qu* q);
/*获取队尾*/
QDataType QueueBack(Qu* q);
/*出队*/
void QueuePop(Qu* q);
/*判空*/
bool QueueEmpty(Qu* q);
/*求解队列大小*/
size_t QueueSize(Qu* q);

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

typedef struct {
    Qu q1;
    Qu q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* obj = (MyStack *)malloc(sizeof(MyStack));
    QueueInit(&(obj->q1));
    QueueInit(&(obj->q2));

    return obj;
}

void myStackPush(MyStack* obj, int x) {
    //只往非空的队列中入数据
    if(!QueueEmpty(&obj->q1))
        QueuePush(&obj->q1,x);
    else
        QueuePush(&obj->q2,x);
}

int myStackPop(MyStack* obj) {
    Qu* EmptyQu = &obj->q1;
    Qu* nonEmptyQu = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {       //必定是一个空，一个非空
        EmptyQu = &obj->q2;
        nonEmptyQu = &obj->q1;
    }

    //首先将非空队列中的前n-1个元素都出队
    while(QueueSize(nonEmptyQu) > 1)
    {
        QueuePush(EmptyQu,QueueFront(nonEmptyQu));  //每次取出非空队列的头元素
        QueuePop(nonEmptyQu);      //出队队头元素
    }
    //此时非空队列中还剩一个元素，取出return即可
    int front = QueueFront(nonEmptyQu);
    QueuePop(nonEmptyQu);       //然后将此元素出队

    return front;
}

int myStackTop(MyStack* obj) {
    //返回非空队列的末尾元素
    if(!QueueEmpty(&obj->q1))
        return QueueBack(&obj->q1);
    else
        return QueueBack(&obj->q2);
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);

    free(obj);
}

//---------------------------------
/*初始化队列*/
void QueueInit(Qu* q)
{
	q->front = NULL;
	q->rear = NULL;
	q->sz = 0;
}

/*销毁队列*/
void QueueDestroy(Qu* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);		
		//del = NULL;		无需再将del置为空，因为其为局部变量不会被访问到
	}
	q->front = q->rear = NULL;		//头尾指针要置空
}

/*入队*/
void QueuePush(Qu* q, QDataType x)
{
	assert(q);
	/*创建结点初始化*/
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("fail malloc");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;

	/*尾插*/
	if (q->rear == NULL)
	{		//队列为空
		q->front = q->rear = newNode;
	}
	else
	{
		q->rear->next = newNode;
		q->rear = newNode;
	}
	q->sz++;		//结点个数 + 1
}

/*出队*/
void QueuePop(Qu* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	//1.只有一个结点
	if (q->front == q->rear)
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	//2.有多个结点
	else
	{
		QNode* del = q->front;
		q->front = q->front->next;
		free(del);
	}
	q->sz--;
}
/*获取队头*/
QDataType QueueFront(Qu* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	return q->front->data;
}

/*获取队尾*/
QDataType QueueBack(Qu* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	return q->rear->data;
}

/*判空*/
bool QueueEmpty(Qu* q)
{
	assert(q);
	return q->front == NULL && q->rear == NULL;
}

/*求解队列大小*/
size_t QueueSize(Qu* q)
{
	return q->sz;
}


/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(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
210
211
212

💻C++代码实现

• 这里也给出C++的代码实现
• C++的思路有所不同，无需去判断哪个队列为空，每次就第q1出队列，q2则作为暂时存放的队列，

class MyStack {
public:
    queue<int> q1;
    queue<int> q2;
    MyStack() {

    }
    
    void push(int x) {
        q1.push(x);
    }
    
    int pop() {
        int sz = q1.size();
        sz--;       //先让总长度减1，少出队一个元素
        while(sz--)
        {           //将sz - 1个元素先放入q2中暂时保存
            q2.push(q1.front());    
            q1.pop();
        }
        int ret = q1.front();      //此时q1中只剩一个元素，出队即为FILO
        q1.pop();

        //重置q1
        q1 = q2;
        while(!q2.empty())
        {       //清空q2
            q2.pop();
        }
        return ret;     //放在最后返回是因为在获取q1队首元素后要pop()掉，否则队列中会有剩余元素
    }
    
    int top() {
        return q1.back();
    }
    
    bool empty() {
        return q1.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */
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

【⭐】补充：单队列实现栈

• 后来有想到一种方法，仅仅使用一个队列就可以实现
• 整体思想是话其实差不多，只是用一个栈，首先一样也要去得出当前队列的元素个数，然后将出队的元素又重新加入到当前队列的末尾，知道剩下一个元素为止，就会需要出队的数据，一样可以实现使用队列去模拟栈

class MyStack {
public:
    queue<int> qu;
    MyStack() {

    }
    
    void push(int x) {
        qu.push(x);
    }
    
    int pop() {
        int sz = qu.size();
        sz--;
        while(sz--)
        {
            //将队头元素置为队尾元素，执行sz - 1此
            qu.push(qu.front());
            qu.pop();
        }
        //此时的出队顺序即为出栈的顺序
        int ret = qu.front();
        qu.pop();
        return ret;     //此处return 是因为最后执行时需要先将队列中元素清除再返回，否则队列不为空
    }
    
    int top() {
        return qu.back();
    }
    
    bool empty() {
        return qu.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */
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

四、总结与提炼

• 最后我们来总结一下本文所介绍的内容，本文讲解的是一道力扣中有关栈与队列相关的题目，是使用队列来实现栈，在题目的分析过程中，我们使用到了两个队列去实现，通过去判断哪个队列是空还是非空，去进行一个入队和出队的操作，继而来实现一个出栈的顺序。在文末还给出了单个队列实现的方法，作为补充了解

以上就是本文所要描述的所有内容，感谢您对本文的观看，如有疑问请于评论区留言或者私信我都可以🍀