数据结构-栈、队列-相关练习
1.用队列实现栈
- 题目概述：请你仅使用两个队列实现一个后入先出（
LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop和empty）。
这里只讲大致思路，如下图：
互相倒就行了，下面讲个具体过程：
- 第一步：入队
- 第二步：倒数据
留下的那个，就是最后的一个数据。
- 第三步：出队/出栈
符合后入先出。
我写的：
队列的数据结构CV一下就行。
2.用栈实现队列
题目概述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（
push、pop、peek、empty）
总体思路：
讲个具体过程：
- 第一步：入栈
- 第二步：倒数据
倒后顺序也倒了，此时stackpop出栈时，数据满足先入先出。
- 第三步：出栈/出队
- 如果又有数据入栈
- 什么时候再倒数据？
stackpop为空的时候再倒。
我写的：
其中，栈的数据结构，同样CV过去。
3.设计循环队列
题目概述：设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
一看到循环，我首先想到了链表：
但这样并不便于实现：
在队列为空时，队首等于队尾；在队列为满时，队首还是等于队尾。
有三个解决方法：
- 加一个
size - 多一个结点，避免冲突
- 不用链表
我选第三个方法，用了数组。
而主要问题转化为，如何用下标表示循环。
先建好结构体：
typedef struct {
int* a;
int head;
int tail;
int k;
} MyCircularQueue;
在初始化时，发现，如果创建k个元素大小的数组，在队列为空时，队首等于队尾；在队列为满时，队首还是等于队尾。
与链表相同的问题，但用数组解决就简单很多了：创建k+1个元素大小的数组就行。
此时，tail为队尾的下一个元素的下标。
在后续的处理中，需要面对主要的问题：如何处理循环？
- 判满：
总数为k+1，下标最大就为k，存满了就是这样：
| 下标 | 0 | 1 | 2 | 3 | … | k |
|---|---|---|---|---|---|---|
| tail | head |
判满时，可以用tail + 1==head
或者这样：
| 下标 | 0 | 1 | 2 | 3 | … | k |
|---|---|---|---|---|---|---|
| head | tail |
对于tail，此时，再+1就越界了，根据观察，可以用(tail + 1)%(k + 1) == head来模拟循环。
- 取尾：
正常情况，tail-1就是尾部元素的下标，但下面这种情况就是不正常的：
| 下标 | 0 | 1 | 2 | 3 | … | k |
|---|---|---|---|---|---|---|
| tail | head |
此时，可以用a[ (tail + k) % (k + 1) ]来模拟循环。
我写的完整代码：
typedef struct {
int* a;
int head;
int tail;
int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* ret = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
ret->a = (int*)malloc(sizeof(int)*(k+1));
ret->head = ret->tail = 0;
ret->k = k;
return ret;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
assert(obj);
return obj->head == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
assert(obj);
return (obj->tail + 1)%(obj->k + 1) == obj->head;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
assert(obj);
if(myCircularQueueIsFull(obj))
return false;
obj->a[obj->tail++] = value;
obj->tail = obj->tail % (obj->k+1);
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))
return false;
obj->head++;
obj->head = obj->head % (obj->k+1);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))
return -1;
else
return obj->a[obj->head];
}
int myCircularQueueRear(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))
return -1;
else
return obj->a[(obj->tail+obj->k)%(obj->k+1)];
}
希望本篇文章对你有所帮助！并激发你进一步探索数据结构的兴趣！
本人仅是个C语言初学者，如果你有任何疑问或建议，欢迎随时留言讨论！让我们一起学习，共同进步！
相关文章：
数据结构-栈、队列-详解