C语言之数据结构之栈和队列的运用

•͈ᴗ•͈ 个人主页：御翮
•͈ᴗ•͈ 个人专栏：C语言数据结构
•͈ᴗ•͈ 欢迎大家关注和订阅!!!

1. 用队列实现栈

题目描述：

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

实现 MyStack 类：

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

注意：

• 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
[“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 都保证栈不为空

1.1 思路讲解

首先队列的特性是先入先出，而栈的特性是先入后出

题目说用两个队列实现一个栈

所以当栈为空时我们有两个空队列q1和q2

我们入数据时先默认入q2，假设这里依次入1、2、3

如果这个时候我们要出栈呢，如果按队列先入先出，我们会拿到1而不是最后入的3

此时我们可以先把1和2依次放入q1中，此时q2中就只剩3，就可以先取出3了

如果我们接着要放数据，就放入非空的队列q1，这样留一个队列q2为空，就还可以继续这样的出栈操作

当我们要继续出栈时，就把前n-1个数据放入空的队列中，再把最后一个数据取出，这样如此颠倒反复，就完成了先入后出的操作

1.2 代码实现

队列代码：

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

typedef int QDatatype;

typedef struct QNode
{
	struct QNode* next;
	QDatatype data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

void Init_Queue(Queue* ptr)
{
	assert(ptr);
	ptr->head = ptr->tail = NULL;
}
void Destroy_Queue(Queue* ptr)
{
	assert(ptr);
	QNode* cur = ptr->head;
	while (ptr->head != NULL)
	{
		cur = ptr->head;
		ptr->head = ptr->head->next;
		free(cur);
	}
	ptr->tail = NULL;
}

QNode* Buy_Node()
{
	QNode* tmp = (QNode*)malloc(sizeof(QNode));
	return tmp;
}

void Print_Queue(Queue* ptr)
{
	assert(ptr);
	QNode* cur = ptr->head;
	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

void Push_Queue(Queue* ptr, QDatatype val)
{
	assert(ptr);
	QNode* newnode = Buy_Node();
	if (newnode == NULL)
	{
		perror("Push_Queue\n");
		exit(1);
	}
	newnode->data = val;
	newnode->next = NULL;
	if (ptr->head == NULL)
	{
		ptr->head = ptr->tail = newnode;
	}
	else
	{
		ptr->tail->next = newnode;
		ptr->tail = newnode;
	}
}

int Queue_Size(Queue* ptr)
{
	assert(ptr);
	int count = 0;
	QNode* cur = ptr->head;
	while (cur != NULL)
	{
		cur = cur->next;
		count++;
	}
	return count;
}

void Pop_Queue(Queue* ptr)
{
	assert(ptr);
	if (ptr->head == NULL)
	{
		printf("队列中没有元素\n");
		return;
	}
	if (Queue_Size(ptr) == 1)
	{
		free(ptr->tail);//如果删完了但是没有将tail置为NULL，则case 5 会发生错误，显示队尾元素随机值。
		ptr->tail = NULL;
		ptr->head = NULL;
		return;
	}
	QNode* pop = ptr->head;
	ptr->head = ptr->head->next;
	free(pop);
}

QDatatype Queue_Front(Queue* ptr)
{
	assert(ptr);
	return ptr->head->data;
}

QDatatype Queue_Back(Queue* ptr)
{
	assert(ptr);
	return ptr->tail->data;
}

int Check_Empty(Queue* ptr)
{
	assert(ptr);
	if (Queue_Size(ptr))
		return 0;
	else
		return 1;
}

//以上是自己创建的队列，因为c语言没有队列
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

队列实现栈代码：

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



// 创建栈
MyStack* myStackCreate() 
{
	MyStack* tmp = (MyStack*)malloc(sizeof(MyStack));

	if (tmp == NULL) // 开辟空间可能失败，失败则终止程序
	{
		printf("Fail: myStackCreate\n");
		exit(1);
	}

	Init_Queue(&tmp->q1); // 我们的栈由两个队列组成，所以初始化要调用队列的初始化
	Init_Queue(&tmp->q2);

	return tmp;
}



// 数据入栈
void myStackPush(MyStack* obj, int x) 
{
	if (Check_Empty(&obj->q1)) // 哪个队列有元素就往哪放，两个都没有就默认放q2，保证只有一个队列有数据
	{
		Push_Queue(&obj->q2, x);
	}
	else
		Push_Queue(&obj->q1, x);
}



// 数据出栈
int myStackPop(MyStack* obj) 
{
	//题目保证每次调用pop时栈都不为空，不用考虑为空时的pop

	if (Check_Empty(&obj->q1)) // 哪个队列有数据就将n-1个数据放到另一个队列，剩下的最后一个元素就是栈顶元素，直接出栈
	{
		int sum = Queue_Size(&obj->q2); // 获取队列元素个数n

		for (int i = 0; i < sum - 1; i++) // 将前n-1个数据放到另一个空队列
		{
			Push_Queue(&obj->q1, Queue_Front(&obj->q2));
			Pop_Queue(&obj->q2);
		}

		QDatatype tmp = Queue_Front(&obj->q2); // 保存最后一个元素的值，再pop，因为要返回出栈元素的值
		Pop_Queue(&obj->q2);

		return tmp;
	}
	else
	{
		int sum = Queue_Size(&obj->q1);

		for (int j = 0; j < sum - 1; j++)
		{
			Push_Queue(&obj->q2, Queue_Front(&obj->q1));
			Pop_Queue(&obj->q1);
		}

		QDatatype tmp = Queue_Front(&obj->q1);

		Pop_Queue(&obj->q1);
		return tmp;
	}
}



// 获取栈顶元素
int myStackTop(MyStack* obj) 
{
	//题目保证每次调用top时栈都不为空，不用考虑为空时的top

	if (Check_Empty(&obj->q1)) // 因为我们前面入栈时保证了只有一个队列有数据，所以队尾元素就是栈顶元素
	{
		return Queue_Back(&obj->q2);
	}
	else
		return Queue_Back(&obj->q1);
}



// 判断栈是否为空
bool myStackEmpty(MyStack* obj) 
{
	if (Check_Empty(&obj->q1) && Check_Empty(&obj->q2)) // 栈由两个队列组成，两个队列都为空栈就为空
	{
		return true;
	}
	else
		return false;
}



// 销毁栈
void myStackFree(MyStack* obj) 
{
	Destroy_Queue(&obj->q1); // 消耗栈要销毁里面的两个队列
	Destroy_Queue(&obj->q2);
	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

2. 用栈实现队列

题目描述：

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

实现 MyQueue 类：

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

注意：

• 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 ：

输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[ [ ], [1], [2], [ ], [ ], [ ] ]
输出：
[ null, null, null, 1, 1, false ]

解释：

MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

1.1 思路讲解

首先栈的特性是先入后出，而队列的特性是先入先出

题目说用两个栈实现一个队列

所以当队列为空时我们有两个空栈

我们给这两个栈分别命名为push和pop

我们入数据只往push里放

出数据的话，如果pop为空，我们就把push栈里面的数据全放进pop栈里，再出栈，就取到了队头的元素

如果pop不为空，就直接出栈就好了

后序有数据也是直接放在push，push只进行入栈，pop只进行出栈，不像用队列实现栈一样要来回颠倒。

1.2 代码实现

栈代码：

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

typedef int STDataType;

typedef struct Stack
{
	STDataType* stack;
	int size;
	int capacity;
}Stack;

void Init_Stack(Stack* ptr)
{
	assert(ptr);
	STDataType* tmp = (STDataType*)malloc(3 * sizeof(STDataType));
	if (tmp == NULL)
	{
		perror("Init_Stack\n");
		exit(1);
	}
	ptr->stack = tmp;
	ptr->capacity = 3;
	ptr->size = 0;
}

void Destroy_Stack(Stack* ptr)
{
	assert(ptr);
	free(ptr->stack);
	ptr->stack = NULL;
}

void Check_Capacity(Stack* ptr)
{
	assert(ptr);
	if (ptr->size == ptr->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ptr->stack, 2 * ptr->capacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("Check_Capacity\n");
			exit(1);
		}
		ptr->stack = tmp;
		ptr->capacity *= 2;
	}
}

void Print_Stack(Stack* ptr)
{
	assert(ptr);
	for (int i = 0; i < ptr->size; i++)
	{
		printf("%d ", ptr->stack[i]);
	}
	printf("\n");
}

void Push_Stack(Stack* ptr, STDataType val)
{
	assert(ptr);
	Check_Capacity(ptr);
	ptr->stack[ptr->size] = val;
	ptr->size++;
}

void Pop_Stack(Stack* ptr)
{
	assert(ptr);
	ptr->size--;
}

STDataType Top_Stack(Stack* ptr)
{
	assert(ptr);
	return ptr->stack[ptr->size - 1];
}

int Size_Stack(Stack* ptr)
{
	assert(ptr);
	return ptr->size;
}

int Empty_Stack(Stack* ptr)
{
	assert(ptr);
	if (ptr->size == 0)
		return 1;
	else
		return 0;
}

typedef struct 
{
	Stack push;
	Stack pop;
} MyQueue;
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

栈实现队列代码：

// 创建队列
MyQueue* myQueueCreate() 
{
	MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));

	if (queue == NULL) // 开辟空间有可能失败，失败则终止程序
	{
		perror("myQueueCreate");
		exit(1);
	}

	Init_Stack(&queue->push); // 初始化队列要初始化里面的栈
	Init_Stack(&queue->pop);

	return queue;
}



// 数据入队列
void myQueuePush(MyQueue* obj, int x) 
{
	Push_Stack(&obj->push, x); // 数据只入push栈
}



// 数据出队列
int myQueuePop(MyQueue* obj) 
{
	if (Empty_Stack(&obj->pop)) // 如果pop栈为空，就要从push栈里面把数据拿过来
	{
		int sum = Size_Stack(&obj->push); // 获取push中的元素个数n

		for (int i = 0; i < sum; i++)
		{
			Push_Stack(&obj->pop, Top_Stack(&obj->push));
			Pop_Stack(&obj->push);
		}
	}

	int ret = Top_Stack(&obj->pop); // 先储存队头元素再出队列，因为题目要返回队头元素
	Pop_Stack(&obj->pop);

	return ret;
}



// 获取队头元素
int myQueuePeek(MyQueue* obj) 
{
	if (Empty_Stack(&obj->pop)) // 如果pop栈为空，那就把push栈里面的元素拿过来
	{
		int sum = Size_Stack(&obj->push);
		for (int i = 0; i < sum; i++)
		{
			Push_Stack(&obj->pop, Top_Stack(&obj->push));
			Pop_Stack(&obj->push);
		}
	}

	return Top_Stack(&obj->pop); // 队头元素就是pop栈中的栈顶元素，因为pop栈内的元素是push栈内的元素顺序颠倒过来
}



// 判断队列是否为空
bool myQueueEmpty(MyQueue* obj) 
{
	if (Empty_Stack(&obj->push) && Empty_Stack(&obj->pop)) // 两个栈都为空，队列就为空
	{
		return true;
	}
	else
		return false;
}



// 销毁队列
void myQueueFree(MyQueue* obj) 
{
	Destroy_Stack(&obj->push);  // 销毁队列要销毁里面的两个栈
	Destroy_Stack(&obj->pop);
	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

总结

两个队列实现栈需要来回颠倒。
两个栈实现队列要确定一个push和一个pop。