文章目录
1.栈
1.1 概念与结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO
(Last In First Out
)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
栈底层结构选型
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
1.2 栈的实现
Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
//定义栈的结构
typedef int STDataType;
typedef struct Stack {
STDataType* arr;
int capacity;//栈的空间大小
int top;//栈顶
}ST;
//栈的初始化
void STInit(ST* ps);
//栈的销毁
void STDestory(ST* ps);
//栈顶---入数据,出数据
//入数据
void StackPush(ST* ps, STDataType x);
//出数据
void StackPop(ST* ps);
//取栈顶元素
STDataType StackTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
//栈的初始化
void STInit(ST* ps) {
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//栈的销毁
void STDestory(ST* ps) {
assert(ps);
if (ps->arr) {
free(ps->arr);
}
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
//栈顶---入数据,出数据
//入数据
void StackPush(ST* ps, STDataType x) {
assert(ps);
//1.判断空间是否足够
if (ps->capacity == ps->top) {
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
if (tmp == NULL) {
perror("relloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
//空间足够
ps->arr[ps->top++] = x;
}
//出数据
void StackPop(ST* ps) {
assert(ps);
assert(!StackEmpty(ps));//栈为空报错
--ps->top;
}
//判断栈是否为空
bool StackEmpty(ST* ps) {
assert(ps);
return ps->top == 0;
}
//获取栈中有效元素个数
int STSize(ST* ps){
assert(ps);
return ps->top;
}
//取栈顶元素
STDataType StackTop(ST* ps) {
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top - 1];
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
void STTest() {
ST st;
STInit(&st);
//
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
printf("size: %d\n", STSize(&st));
//循环出栈,直到栈为空
while (!StackEmpty(&st)) {
STDataType data = StackTop(&st);
printf("%d ", data);
//出栈
StackPop(&st);
}
printf("size: %d\n", STSize(&st));
//
//STDestory(&st);
}
int main() {
STTest();
return 0;
}
2.队列
2.1 概念与结构
概念:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
队列底层结构选型
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。
2.2 队列的实现
Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
//定义队列结构
typedef int QDataType;
typedef struct QueueNode {
QDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue {
QueueNode* phead;//队头:删
QueueNode* ptail;//队尾:插
int size;//保存队列有效数据个数
}Queue;
//初始化队列
void QueueInit(Queue* pq);
// 入队列,队尾
void QueuePush(Queue* pq, QDataType x);
// 出队列,队头
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
//初始化队列
void QueueInit(Queue* pq) {
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
// 入队列,队尾
void QueuePush(Queue* pq, QDataType x) {
assert(pq);
//申请新结点
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL) {
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->phead == NULL) {//判断队列是否为空
pq->phead = pq->ptail = newnode;
}
else {
//队列不为空
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;//入一次,size++ 一次
}
//队列判空
bool QueueEmpty(Queue* pq) {
assert(pq);
return (pq->phead == NULL) && (pq->ptail == NULL);
}
// 出队列,队头
void QueuePop(Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));
//只有一个结点的情况,避免ptail变成野指针
if (pq->ptail == pq->phead) {
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else {
//删除队头元素
QueueNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
--pq->size;//出一次,size-- 一次
}
//取队头数据
QDataType QueueFront(Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));//判断队列不为空
return pq->phead->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));//判断队列不为空
return pq->ptail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq) {
assert(pq);
/*int size = 0;
QueueNode* pcur = pq->phead;
while (pcur) {
size++;
pcur = pcur->next;//复杂度O(n)
}*/
return pq->size;//复杂度O(1)
}
//销毁队列
void QueueDestroy(Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));//判断队列不为空,空队列不需要销毁
QueueNode* pcur = pq->phead;
while (pcur) {
QueueNode* Next = pcur->next;
free(pcur);
pcur = Next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QueueTest01() {
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
//QueuePop(&q);
printf("head:%d\n", QueueFront(&q));
printf("tail:%d\n", QueueBack(&q));
printf("size:%d\n", QueueSize(&q));
QueueDestroy(&q);
//QueuePop(&q);
//QueuePop(&q);
//QueuePop(&q);
//QueuePop(&q);
QueuePop(&q);
}
int main() {
QueueTest01();
return 0;
}
3.栈和队列算法题
3.1 有效的括号
思路:
定义一个指针
ps
遍历字符串若
ps
遍历到的字符为左括号,入栈若
ps
遍历到的字符为右括号,取栈顶元素与ps
进行比较,
栈顶元素 匹配 *ps
,出栈,ps++
栈顶元素 不匹配 *ps
,返回false
代码:
//定义栈的结构
typedef char STDataType;
typedef struct Stack {
STDataType* arr;
int capacity;//栈的空间大小
int top;//栈顶
}ST;
//栈的初始化
void STInit(ST* ps) {
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//栈的销毁
void STDestory(ST* ps) {
assert(ps);
if (ps->arr) {
free(ps->arr);
}
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
//栈顶---入数据,出数据
//入数据
void StackPush(ST* ps, STDataType x) {
assert(ps);
//1.判断空间是否足够
if (ps->capacity == ps->top) {
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
if (tmp == NULL) {
perror("relloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
//空间足够
ps->arr[ps->top++] = x;
}
//判断栈是否为空
bool StackEmpty(ST* ps) {
assert(ps);
return ps->top == 0;
}
//出数据
void StackPop(ST* ps) {
assert(ps);
assert(!StackEmpty(ps));//栈为空报错
--ps->top;
}
//获取栈中有效元素个数
int STSize(ST* ps){
assert(ps);
return ps->top;
}
//取栈顶元素
STDataType StackTop(ST* ps) {
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top - 1];
}
bool isValid(char* s) {
ST st;
//初始化
STInit(&st);
//遍历字符串s
char* ps = s;
while(*ps != '\0'){
//左括号,入栈
if(*ps == '(' || *ps == '[' || *ps == '{'){
StackPush(&st, *ps);
}
else{//右括号,和栈顶元素比较是否匹配
//栈为空,直接返回false
if(StackEmpty(&st)){
return false;
}
//栈不为空才能取栈顶元素
char ch = StackTop(&st);
if((*ps == ')' && ch == '(')
|| (*ps == ']' && ch == '[')
|| (*ps == '}' && ch == '{') ){
StackPop(&st);
}
else{
//不匹配
STDestory(&st);
return false;
}
}
ps++;
}
bool ret = StackEmpty(&st) == true;//如果为空,返回true
//销毁
STDestory(&st);
return ret;
}
3.2 用队列实现栈
思路:
出栈:找不为空的队列,将
size-1
个数据导入到另一个队列中。入栈:往不为空队列里面插入数据
取栈顶元素:
例如:
两个队列:
- Q1:
1 2 3
- Q2:
NULL
如果是栈的话:
- 插入
1 2 3
- 出栈一次
- 插入4
- 全部出栈
得到:
3 4 2 1
将
Q1
里面的1 2
出栈到Q2
,把3
取出来,此时Q1
为NULL
取出了3
往
Q2
里面插入4
,此时Q2
为1 2 4
将
Q2
里面的1 2
出栈到Q1
,此时Q2
为4
,把4
取出来,此时Q2
为NULL
取出了3 4
将
Q1
里面的1
出栈到Q2
,把2
取出来 ,此时Q1
为NULL
取出了3 4 2
将
Q2
里面的1
取出来取出了3 4 2 1
代码:
//定义队列结构
typedef int QDataType;
typedef struct QueueNode {
QDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue {
QueueNode* phead;//队头:删
QueueNode* ptail;//队尾:插
int size;//保存队列有效数据个数
}Queue;
//初始化队列
void QueueInit(Queue* pq) {
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
// 入队列,队尾
void QueuePush(Queue* pq, QDataType x) {
assert(pq);
//申请新结点
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL) {
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->phead == NULL) {//判断队列是否为空
pq->phead = pq->ptail = newnode;
}
else {
//队列不为空
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;//入一次,size++ 一次
}
//队列判空
bool QueueEmpty(Queue* pq) {
assert(pq);
return (pq->phead == NULL) && (pq->ptail == NULL);
}
// 出队列,队头
void QueuePop(Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));
//只有一个结点的情况,避免ptail变成野指针
if (pq->ptail == pq->phead) {
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else {
//删除队头元素
QueueNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
--pq->size;//出一次,size-- 一次
}
//取队头数据
QDataType QueueFront(Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));//判断队列不为空
return pq->phead->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));//判断队列不为空
return pq->ptail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq) {
assert(pq);
return pq->size;//复杂度O(1)
}
//销毁队列
void QueueDestroy(Queue* pq) {
assert(pq);
//这里允许pq为空
// assert(!QueueEmpty(pq));//判断队列不为空,空队列不需要销毁
QueueNode* pcur = pq->phead;
while (pcur) {
QueueNode* Next = pcur->next;
free(pcur);
pcur = Next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
//两个队列来实现栈
typedef struct {
Queue q1;//队列1
Queue q2;//队列2
} MyStack;
//STInit
MyStack* myStackCreate() {
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}
//Push入栈
void myStackPush(MyStack* obj, int x) {
//往不为空的队列中插入数据
if(!QueueEmpty(&obj->q1)){//如果q1不为空,执行这个
QueuePush(&obj->q1,x);//往队列q1里面插入x
}
else{//如果q2不为空,执行这个
QueuePush(&obj->q2,x);//往队列q2里面插入x
}
}
//Pop出栈
int myStackPop(MyStack* obj) {
//找不为空的队列
Queue* empQ = &obj->q1;//定义q1为空
Queue* noneQ = &obj->q2;//定义q2为非空
if(!QueueEmpty(&obj->q1)){//如果q1不为空,执行这个
noneQ = &obj->q1;//q1是非空队列
empQ = &obj->q2;//q2是空队列
}
//将不为空队列中size-1个数据导入到空队列中
while(QueueSize(noneQ) > 1){//循环结束的判断,是只剩下一个数据
int front = QueueFront(noneQ);//取队头数据
QueuePush(empQ,front);//往空队列q2里面插入队头元素
QueuePop(noneQ);//把非空队列q1里面的队头元素拿出来,这样下次循环出来的队头元素就不会重复了
}
//非空队列中只剩下一个数据------要出栈的数据
int pop = QueueFront(noneQ);//把要取出的数据存起来
QueuePop(noneQ);//将数据出队列,让q1变成空队列
return pop;//返回要取出的数据
}
//取栈顶元素:找不为空的队列,取队尾元素
//不出栈
int myStackTop(MyStack* obj) {
if(!QueueEmpty(&obj->q1)){
//q1不为空
return QueueBack(&obj->q1);//取队尾数据
}
else{
//q2不为空
return QueueBack(&obj->q2);//取队尾数据
}
}
//判断栈是否为空
//也就是判断两个队列是否为空
bool myStackEmpty(MyStack* obj) {//栈是空的,返回 true ;否则,返回 false 。
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
//栈的销毁
//也就是判断两个队列的销毁
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);//销毁q1
QueueDestroy(&obj->q2);//销毁q2
//因为MyStack* myStackCreate()里面有个指针pst,所以我们还要销毁指针obj
free(obj);//销毁指向栈的指针
obj = NULL;
}
/**
* 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);
*/
3.3 用栈实现队列
思路:
定义两个栈:
pushST
(入数据)和popST
(出数据)假设我们要在队列里放
123
,出队列123
我们先在
pushST
里面放进去1 2 3
然后把
pushST
里面的数据拿到popST
里面,依次是3 2 1
然后把
1
提取出来,把2
提取出来,把3
提取出来.
如果我们先在
pushST
里面放进去1 2 3
然后把
pushST
里面的数据拿到popST
里面,依次是3 2 1
然后在
pushST
里面放进去4
然后把
popST
里面的1
提取出来,把2
提取出来,把3
提取出来.然后把
pushST
里面的数据4
拿到popST
里面然后把
4
提取出来
入队:往
pushST
中插入数据出队:判断
popST
是否为空,不为空直接pop
,为空的话将pushST
导入到popST
中再pop
取队头:跟出队一样,但这里只取数据,不
pop
数据
代码:
//定义栈的结构
typedef char STDataType;
typedef struct Stack {
STDataType* arr;
int capacity;//栈的空间大小
int top;//栈顶
}ST;
//栈的初始化
void STInit(ST* ps) {
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//栈的销毁
void STDestory(ST* ps) {
assert(ps);
if (ps->arr) {
free(ps->arr);
}
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
//栈顶---入数据,出数据
//入数据
void StackPush(ST* ps, STDataType x) {
assert(ps);
//1.判断空间是否足够
if (ps->capacity == ps->top) {
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
if (tmp == NULL) {
perror("relloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
//空间足够
ps->arr[ps->top++] = x;
}
//判断栈是否为空
bool StackEmpty(ST* ps) {
assert(ps);
return ps->top == 0;
}
//出数据
void StackPop(ST* ps) {
assert(ps);
assert(!StackEmpty(ps));//栈为空报错
--ps->top;
}
//获取栈中有效元素个数
int STSize(ST* ps){
assert(ps);
return ps->top;
}
//取栈顶元素
STDataType StackTop(ST* ps) {
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top - 1];
}
//
typedef struct {
ST pushST;
ST popST;
} MyQueue;
//队列的初始化
MyQueue* myQueueCreate() {
MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&pst->pushST);
STInit(&pst->popST);
return pst;
}
//往pushST中插入数据
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->pushST,x);
}
//删除数据
//1.检查popST是否为空,不为空直接出,为空pushST导入到popST,再出数据
int myQueuePop(MyQueue* obj) {
if(StackEmpty(&obj->popST)){
//如果popST为空
//导数据
while(!StackEmpty(&obj->pushST)){
//如果pushST非空
StackPush(&obj->popST, StackTop(&obj->pushST));//把取到的栈顶元素导入进popST
StackPop(&obj->pushST);
}
}
//取栈顶,删除栈顶元素并返回栈顶数据
int top = StackTop(&obj->popST);//储存删除的栈顶元素
StackPop(&obj->popST);
return top;//返回删除的栈顶元素
}
//取队头元素
int myQueuePeek(MyQueue* obj) {
if(StackEmpty(&obj->popST)){
//如果popST为空
//导数据
while(!StackEmpty(&obj->pushST)){
//如果pushST非空
StackPush(&obj->popST, StackTop(&obj->pushST));//把取到的栈顶元素导入进pushST
StackPop(&obj->pushST);
}
}
//取栈顶,删除栈顶元素并返回栈顶数据
return StackTop(&obj->popST);//返回删除的栈顶元素
}
//判断队列是否为空
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
//队列的销毁
//就是两个栈的销毁
void myQueueFree(MyQueue* obj) {
STDestory(&obj->pushST);
STDestory(&obj->popST);
free(obj);
obj = NULL;
}
/**
* Your MyQueue struct will be instantiated and called as such:
* MyQueue* obj = myQueueCreate();
* myQueuePush(obj, x);
* int param_2 = myQueuePop(obj);
* int param_3 = myQueuePeek(obj);
* bool param_4 = myQueueEmpty(obj);
* myQueueFree(obj);
*/
3.4 设计循环队列
思路:
循环队列,空间固定。
这里我们可以用数组来实现循环队列。
如何判断队列是否为满?
多申请一块空间
(rear+1)%(k+1) == front
如何判断队列是否为空?
rear == front
代码:
//定义循环队列的结构
typedef struct {
int* arr;//定义数组
int front;//定义头
int rear;//定义尾
int capacity;//定义一个变量保存数组空间大小
} MyCircularQueue;
//循环队列的初始化
MyCircularQueue* myCircularQueueCreate(int k) {
//定义一个指针,动态申请一块空间,指向循环队列
MyCircularQueue* pst = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//底层数组申请k+1个整型空间
pst->arr = (int*)malloc(sizeof(int)*(k+1));
pst->front = pst->rear = 0;
pst->capacity = k;//把k保存起来
return pst;//返回指向循环队列的指针
}
//判断队列是否满了
bool myCircularQueueIsFull(MyCircularQueue* obj) {
//(rear+1)%(k+1) == front 就满了
return (obj->rear+1)%(obj->capacity+1) == obj->front;
}
//入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//队列满了就不能插入数据
if(myCircularQueueIsFull(obj)){
return false;//说明插入失败
}
//队列没满,可以插入数据
obj->arr[obj->rear++] = value;//插入一个数据rear++
obj->rear %= obj->capacity + 1;//如果rear跑到队尾了,就通过取余回到队头
return true;//说明插入成功
}
//判断队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->rear == obj->front;
}
//出队列
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//队列为空
if(myCircularQueueIsEmpty(obj)){
return false;//表示删除失败
}
//队列不为空
obj->front++;
obj->front %= obj->capacity + 1;//如果front跑到队尾了,就通过取余回到队头
return true;//表示删除成功
}
//取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {
//如果队列为空
if(myCircularQueueIsEmpty(obj)){
return -1;//如果队列为空,返回 -1
}
//如果队列不为空
return obj->arr[obj->front];
}
//取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
//如果队列为空
if(myCircularQueueIsEmpty(obj)){
return -1;//如果队列为空,返回 -1
}
//如果队列不为空
int prev = obj->rear-1;//prev是rear前一个位置
if(obj->rear == 0){
prev = obj->capacity;//如果rear是处在arr[0],那么prev在arr[k]
}
return obj->arr[prev];
}
//循环队列的销毁
//就是顺序表的销毁
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->arr);
free(obj);
obj = NULL;
}
/**
* Your MyCircularQueue struct will be instantiated and called as such:
* MyCircularQueue* obj = myCircularQueueCreate(k);
* bool param_1 = myCircularQueueEnQueue(obj, value);
* bool param_2 = myCircularQueueDeQueue(obj);
* int param_3 = myCircularQueueFront(obj);
* int param_4 = myCircularQueueRear(obj);
* bool param_5 = myCircularQueueIsEmpty(obj);
* bool param_6 = myCircularQueueIsFull(obj);
* myCircularQueueFree(obj);
*/
循环队列的概念与结构
实际中还有一种特殊的队列叫循环队列,环形队列首尾相连成环,环形队列可以使用数组实现,也可以使用循环链表实现
思考:队列满的情况下,为什么 Q.rear 不存储数据?
为了能使用
Q.rear = Q.front
来区别是队空还是队满,我们常常认为出现左图时的情况即为队满的情况此时:
rear+1=front