写在前面
对于我个人来说,我会把数据机构初阶分为三个台阶,今天谈的和之前谈的是一个阶段,后面的二叉树一个,排序一个.栈和队列也同样是我们后面模拟实现二叉树递归和广度遍历的基础,这个算是一个过渡的内容,在博客后面我们会谈一个循环队列的实现,这个主要会在选择题中出现.
Stack
一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则.注意 我们不知道那一端是栈顶,但是一旦我们选择一端作为栈顶,那么另一端就是栈底.
我们先看一道题目这道题考察的是栈的特性的知识点.
问题:借助于栈输入A、B、C、D四个元素(进栈和出栈可以穿插进行)，则不可能出现的输出是()
A.DCBA
B.ABCD
C.CBAD
D.CABD
我们按照栈先进后出的特性一个一个筛选选项就可以了,没有太多难的.
A选项 ＡＢＣＤ一次性全部压入栈中,后面一个一个出来就可以了
B选项 先压入 A 进入后直接出来A 再压B,直接出来B 依次类推
C选项 压入A B C,出来C,再出B,再出A,最后压入D,直接出来D
D选项 压入A B C,出来C 后面要出的话只能出来的是B,所以错误
本质
我们想一下我们该如何如何实现这个栈.我们这里底层可以用两个结构来做这个底层,数组和链表,这里我们实现数组栈的,如果你要是想实现链式栈,可以自己试试,我我们前面已经谈过链表了,这里很容易.
下面就是我们需要关注的,这里的相关细节我们就不谈了,前面的顺序表和链表已经和大家谈过两次了.
typedef int StackDataType;
typedef struct Stack
{
StackDataType* a;
int top; // 栈顶的位置
int capacity; // 容量
}Stack;
常用接口
我们看一下它们常见的接口,注意这里我们每实现一个接口,这里就不演示是否正确了,如果你看懂了我们前面的博客,这里就是小菜一碟.
StackInit()
我们和前面一样,都是先进行初始化,这里我们需要谈一下,我们在最开始的时候,top指向的是0还是-1?这涉及到我们后面的内容.这里我们选择初始化为0的方案.
- top 初始化 为 0 这是栈顶元素的下一个位置
- top 初始化 为-1 这里是指向栈顶位置
void StackInit(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
StackDestory()
这个最后把空间给释放了就可以了,
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL; // 这是一个好的习惯
ps->capacity = 0;
ps->top = 0;
}
StackPush()
这里就是入栈的操作,注意我们这里没有把扩容这个操作单独拿出来,主要的原因就是我们只有这一个函数用到扩容,没必要复用.
void StackPush(Stack* ps, StackDataType x)
{
assert(ps);
// 注意 top初始化值 也会影响扩容
if(ps->capacity == ps->top)
{
int newCapacity = ps->capacity == 0 ? 4 : 2*ps->capacity;
StackDataType* ret = (StackDataType*)realloc(ps->a, sizeof(StackDataType)*newCapacity);
assert(ret);
ps->a = ret;
ps->capacity = newCapacity;
}
ps->a[ps->top++] = x;
}
StackSize()
这里是查看栈的元素,很简单,不在赘述.
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
StackTop()
这里就是简单的查看栈顶的元素,不做删除,不过还要保障栈里面存在元素.而且查看栈顶元素收到top初始化的影响
StackDataType StackTop(Stack* ps)yuansu
{
assert(ps);
assert(ps > 0);
// 这里-1 和 0 就可以体现出来了
// -1 这里栈顶 就是 top
// 0 栈顶 top-1
return ps->a[ps->top-1];
}
StackPop()
这里就是删除栈顶的元素,我们首先要保障栈里面存在元素,注意这里判断的top收到我们初始化那里的影响.
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
StackEmpty()
这里是判断栈不是空,很简单.
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
这里我们最后统一测试一下就可以了,注意这个方法很不好,我们呢推荐写一个测一个,但是这个实在是太简单了.
void TestStack()
{
Stack s;
StackInit(&s);
StackPush(&s, 1);
StackPush(&s, 2);
StackPush(&s, 3);
StackPush(&s, 4);
StackPush(&s, 5);
while(!StackEmpty(&s))
{
printf("%d ", StackTop(&s));
StackPop(&s);
}
printf("\n");
StackDestory(&s);
}
int main()
{
TestStack();
return 0;
}
Queue
队列：只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头 .
我们先来谈一下队列的实际应用,大家应该都去银行办理过业务吧,起初我们都是自己自发排队,如果有人插队这里对其他人就很不公平,我们不能把这个依赖到人的道德水准上.现在大多银行就是排号,我们每一个人拿到一个号码,叫道谁谁就办理业务,那么这里就用到了队列的原理,谁先来谁就先办理业务.
本质
我们也和上面一样,也先来确定一下我们实现队列的底层,这里我们用数组和链表都可以.
- 数组 这里无论采用哪端作为堆头,入队和出队总有一个时间复杂度比较总有一个比较大
- 链表 这里很利于入队和出队, 我们可以使用一个指针指向尾部,把尾部当作队尾
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail; // 这个指向 尾部 ,便于尾插
}Queue;
常见接口
我们也来谈一下它们的常见接口,这里和栈差不多.我们也是先实现后面验证一下,留够足够的精力解决我们最后一个模块的内容.
QueueInit()
我们初始化一下队列,至于为何传指针我们不谈了,前面谈的太多了.
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
QueuePush()
我们需要先创建一个节点,把数据给保存下来,这里由于我们只有一个地方需要创建节点,所以这里就不把它封成函数了.还要关注的一点就是我们需要判断一下第一次插入.其他的没有要注意的了.
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//QueueNode* node = BuyQueueNode(x);
QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
assert(node);
node->data = x;
node->next = NULL;
// 第一次插入
if(pq->head == NULL
&& pq->tail == NULL)
pq->head = node;
else
pq->tail->next = node;
pq->tail = node;
}
QueueFront()
不同于stack,这个函数名叫做front,这是查看栈顶的元素,注意判断栈是不是空.
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);
return pq->head->data;
}
QueueBack()
这是查看栈尾的元素,注意判断栈是不是空.
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);
return pq->tail->data;
}
QueuePop()
这个就是出队的操作,实质上就是链表头删的操作.
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);
// 保存头节点的下一个节点
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
// 删除后没有节点了 要一起为空
if(next == NULL)
pq->tail = NULL;
}
QueueEmpty()
这里是判空操作,由于前面我们出队把head和tail都置空了,这里判断两个就可以了,当然只判断head也是可以的.
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL && pq->tail == NULL;
}
QueueSize()
计算队中元素的大小应该是我们自己模拟实现的时间复杂度最大的,需要遍历整个链表.当然我们也可以在队列中加入一个count,记录元素的个数,每次入队和出队更新count就可以了.
size_t QueueSize(Queue* pq)
{
// 这个接口是最慢了
// 如果不想遍历 可以使用 一个计数
assert(pq);
QueueNode* cur = pq->head;
size_t count = 0;
while(cur)
{
cur = cur->next;
count++;
}
return count;
}
QueueDestory()
对于链表的销毁是我们需要在稍微谈一下的,我们需要一个指针指向当前节点的下一个节点,这里是因为我们free某个节点之后,这节点就变成野指针了,我们需要保存一些写一个节点.
void QueueDestory(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while(cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = NULL;
pq->tail = NULL;
}
这里我们也测试一下就写的是否正确就可以了.
void TestQueuePush()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
while(!QueueEmpty(&q))
{
int ret = QueueFront(&q);
printf("%d ",ret);
QueuePop(&q);
}
printf("\n");
QueueDestory(&q);
}
int main()
{
TestQueuePush();
return 0;
}
循环队列
这个应该是我们今天的重点,操作系统课程讲解生产者消费者模型时就会使用循环队列.我们在选择题中也会经常碰到计算循环队列的元素.我们先来看一下循环队列是什么,这里用一道OJ题.
题目链接:设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值.
说人话,循环队列在理论上就是一个环,这个环也遵守先进先出的特性,这个环可以容纳数据的量是固定的,今天我们就要把它简单的是实现一下,就按照题目的接口来设计.
本质
前面我说了,理论上是一个环,实质上是一个数组或者链表,我们在是在实现的时候把他设计成环的特性就可以了.我们这里可以实现成数组或者链表,这里链表我们不太好找到头节点,当然你也可以设计成循环链表,但是有点麻烦.我们直接实现成数组.
好了,现在我们需要开始推理,我们谈了循环队列的大小对外人来说是固定的,但是每个人要大小的不一样,这里底层还是一个指针,我们后面提供一个函数让人指定大小就可以了.
typedef int MQDataType;
typedef struct
{
MQDataType* array;
size_t front;
size_t tail; // 指向最后一个数据的下一个位置
size_t cap;
} MyCircularQueue;
这里还有一个问题,假设我们要求是5个空间,那么我们应该开辟5个空间吗?这里我们要先从开始来谈.我们先来定一个条件,当tail 和 front相等的时候这里我们认为循环队列空了,那么如果我们要是开辟5个空间,这里判满的时候就和判空的条件出现了重复.
这里就不卖关子了,我们这里直接开辟6个空间,这样我们判满的是tail+1与front的情况,判空的条件不变.这样就解决了.
模拟实现
我们这里开始实现一下,这里就按照OJ题来实现.
myCircularQueueCreate()
这里我要说一下,对于用户而言,他要k个空间,在他们心中认为这k个空间都是可以存放元素的,但是底层我们实现的时候需要开辟k+1个空间.
MyCircularQueue* myCircularQueueCreate(int k) {
// 这里要求是 是 k 的有效元素 我们 开辟 k+1
MyCircularQueue* m = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
assert(m);
`
MQDataType*ret = (MQDataType*)malloc(sizeof(MQDataType) * (k+1)) ;
assert(ret);
m->array = ret;
m->front = 0;
m->tail = 0;
m->cap = k+1;
return m;
}myCircularQueueEnQueue()
入队列首先要做的就是判断队列是不是满了,这里我们后面实现.对于入队列我们这里要注意点一点,当tail开始的时候指向这个数组最后一个位置时,我们这里需要更新tail不再是++,而是直接指向下标 0.,记住我们是一个循环.
// 入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
assert(obj);
// 判满
if(myCircularQueueIsFull(obj))
return false;
obj->array[obj->tail] = value;
if(obj->tail == obj->cap-1)
obj->tail = 0;
else
obj->tail++;
return true;
//方法 2 这里取模
//int ret = (obj->tail+1) % (obj->cap);
//obj->tail = ret;
//return true;
}
myCircularQueueDeQueue()
先判空,和上面一样,对于普通位置,我们font直接++,这里需要判断一下特殊情况.
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
assert(obj);
// 判空
if(myCircularQueueIsEmpty(obj))
return false;
if(obj->front == obj->cap-1)
obj->front = 0;
else
obj->front++;
// 这里修改 front
//int ret = (obj->front+1)%(obj->cap);
//obj->front = ret;
return true;
}myCircularQueueFront()
查看队定元素,很简单.
// 头部
int myCircularQueueFront(MyCircularQueue* obj) {
assert(obj);
// 判空
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->array[obj->front];
}
myCircularQueueRear()
查看尾部元素,这里我们也要判断一下特殊情况,主要时tail指向当前元素的下一个位置,当我们tail等于0时,这里需要判断该数组最后的一个元素.
// 尾部
int myCircularQueueRear(MyCircularQueue* obj) {
assert(obj);
// 判空
if(myCircularQueueIsEmpty(obj))
return -1;
// 如果 tail 是 0 单拿出来
if(obj->tail == 0)
{
return obj->array[obj->cap - 1];
}
return obj->array[obj->tail - 1];
}
myCircularQueueIsEmpty()
判断空就看tail和front是不是相等就可以了.
// 空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
assert(obj);
return obj->front == obj->tail;
}
myCircularQueueIsFull()
判满是我们需要重点谈的,我们需要拿到tail这个位置的下一个位置,如果原本tail就是在数组最后一个位置,那么它的下一个位置应该是0,我们得到下一个位置之后需要和front进行判断,这样才能看循环队列是不是满的.
// 满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
assert(obj);
size_t ret = (obj->tail+1)%obj->cap;
return ret == obj->front;
}
myCircularQueueFree(()
直接释放资源就可了
// 释放空间
void myCircularQueueFree(MyCircularQueue* obj) {
assert(obj);
free(obj->array);
obj->array = NULL;
obj->front = 0;
obj->tail = 0;
free(obj);
}
这里我们在OJ上跑一下,发现可以通过,这里万事大吉.
