🌟 前言

Wassup guys！我是Edison 😎

今天是 LeetCode 上的 leetcode 225. 用队列实现栈

Let’s get it！

---

---

1. 题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

示例：

输入：
["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
2
3
4
5
6
7
8
9
10
11
12
13

2. 思路解析

首先我们知道，队列是先进先出，栈是后进先出。

那么我们可以使用两个队列，始终保持一个队列为空。

当我们需要进行 压栈 操作时，将数据压入 不为空的队列中（若两个都为空，则随便压入一个队列）。如图所示👇

当需要进行 出栈 操作时，将 不为空的队列 中的数据导入 空队列 中，仅留下一个数据，这时将这个数据返回并且删除即可。

判断栈是否为空，即判断两个队列是否同时为空。

流程如图所示👇

3. 代码实现

队列的实现

typedef int QDataType;

// 链式结构：表示队列（记录每个结点）
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

// 队列的结构 （找到队列的头和尾的）
typedef struct Queue
{
	QNode* head; // 队列的头指针
	QNode* tail; // 队列的尾指针
}Queue;


// 初始化队列 
void QueueInit(Queue* q);

// 队尾入队列 
void QueuePush(Queue* q, QDataType x);

// 队头出队列 
void QueuePop(Queue* q);

// 获取队列头部元素 
QDataType QueueFront(Queue* q);

// 获取队列队尾元素 
QDataType QueueBack(Queue* q);

// 获取队列中有效元素个数 
int QueueSize(Queue* q);

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);

// 销毁队列 
void QueueDestroy(Queue* q);

//——————————————————————————————————————————————————————————————————————————

// 初始化队列 
void QueueInit(Queue* q) {
	assert(q); //队列可以为空，但是管理队列的头指针和尾指针不能为空
	q->head = NULL;
	q->tail = NULL;
}

// 队尾入队列（尾插）
void QueuePush(Queue* q, QDataType x) {
	assert(q);

	/*开辟一个新结点*/
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL) {
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x; //把x赋给newnode的数据域
	newnode->next = NULL; //因为是尾插，所以尾部的结点的next要指向NULL

	/*如果头、尾都为空，那么说明队列还是空的，还没有结点*/
	if (q->head == NULL && q->tail == NULL) {
		assert(q);
		q->head = q->tail = newnode;
	}
	else { //说明队列已经有结点了，直接到插入到尾部即可
		q->tail->next = newnode; //把newnode链接到tail的next
		q->tail = newnode; //然后让tail指向newnode
	}
}

// 队头出队列 
void QueuePop(Queue* q) {
	assert(q);
	assert(q->head && q->tail); //队列的head和tail不能为空,不然怎么头删呢？

	//如果head的next为空，那么说明只有一个结点
	if (q->head->next == NULL) {
		free(q->head); //直接释放掉head
		q->head = q->tail = NULL; //然后把head和tail 置为空
	}
	else {
		QNode* next = q->head->next; //保存头结点的下一个结点地址
		free(q->head); //释放掉head
		q->head = next;
	}
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q) {
	assert(q);
	assert(q->head); //取队头的数据，那么head肯定不能为空

	return q->head->data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q) {
	assert(q);
	assert(q->tail); //取队尾的数据，那么tail肯定不能为空

	return q->tail->data;
}

// 获取队列中有效元素个数 
// 这个函数是队列里面最慢的函数，时间复杂度为O(N)
int QueueSize(Queue* q) {
	assert(q);
	QNode* cur = q->head; //使用cur遍历整个队列
	int count = 0; //统计队列元素个数
	while (cur) { //当cur不为空，就进入循环
		count++;
		cur = cur->next;
	}
	return count;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q) {
	assert(q);

	//如果head或者tail等于空，说队列为空
	return q->head == NULL && q->tail == NULL;
}

// 销毁队列 
void QueueDestroy(Queue* q) {
	assert(q);
	QNode* cur = q->head; //使用cur遍历整个队列
	while (cur) { //如果cur不为空
        QNode* next = cur->next; //存储cur的下一个结点
		free(cur); //释放掉cur
		cur = next; //把cur的下一个结点赋给cur
	}
	q->head = q->tail = NULL;
}
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

接口代码

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


MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    assert(pst);

    QueueInit(&pst->q1);
    QueueInit(&pst->q2);

    return pst;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);

    /*判断q1和q2谁为空,谁为空就往谁里面去push*/
    if (!QueueEmpty(&obj->q1)) {
        QueuePush(&obj->q1, x);
    }
    else {
        QueuePush(&obj->q2, x);
    }
}

int myStackPop(MyStack* obj) {
    assert(obj);
    Queue* emptyQ = &obj->q1; //假设q1为空
    Queue* nonEmptyQ = &obj->q2; //假设q2不为空

    /*如果假设错误,那么就重新交换*/
    if (!QueueEmpty(&obj->q1)) { 
        emptyQ = &obj->q2;
        nonEmptyQ = &obj->q1;
    }    

    /*把非空队列的前N个数据，导入空队列里面去，剩下一个删掉，就实现了后进先出*/
    while (QueueSize(nonEmptyQ) > 1) {
        int front = QueueFront(nonEmptyQ);
        QueuePush(emptyQ, front); //把非空队列里面的队头的数据放到空里面去
        QueuePop(nonEmptyQ); //删除队头的元素
    }

    // 此时还剩下一个，把他删掉
    int top = QueueFront(nonEmptyQ);
    QueuePop(nonEmptyQ);
    return top;
}

int myStackTop(MyStack* obj) {
    assert(obj);

    /**/
    if (!QueueEmpty(&obj->q1)) {
        return QueueBack(&obj->q1);
    }
    else {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    assert(obj);

    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    assert(obj);

    /*先销毁q1和q2*/
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);

    free(obj);

}

/**
 * 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

提交结果