元素入队
void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->PushST,x); }
将Push元素倒到Pop中
void PushSTTOPopsT(MyQueue* obj) { if(StackEmpty(&obj->PopST))//如果Pop栈内为空，并且Push不为空就给元素 { while(!StackEmpty(&obj->PushST))//当Push不为空 { StackPush(&obj->PopST,StackTop(&obj->PushST)); StackPop(&obj->PushST); } } }
返回头元素然后移除
int myQueuePop(MyQueue* obj) { PushSTTOPopsT(obj); int front=StackTop(&obj->PopST); StackPop(&obj->PopST); return front; }
返回头元素
int myQueuePeek(MyQueue* obj) { PushSTTOPopsT(obj); return StackTop(&obj->PopST); }
判断是否为空
bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->PopST)&&StackEmpty(&obj->PushST); }
空间的销毁
void myQueueFree(MyQueue* obj) { StackDestory(&obj->PushST); StackDestory(&obj->PopST); free(obj); }
设计循环队列
622. 设计循环队列 - 力扣（LeetCode）
这里采用数组实现（链表有缺点后面会讲到），front指向首元素，back指向最后元素的下一个空间，空间大小为4，多开辟一个空间，即总共开辟五个空间，使得back+1的位置是front
结构体的定义
typedef struct { int *a; int front; int back; int N; //用来统计空间的总个数 } MyCircularQueue;
初始化
MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a=(int *)malloc(sizeof(int)*(k+1)); //多开辟一个空间 obj->back=obj->front=0; obj->N=k+1; return obj; }
判断是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->back==obj->front; }//当back==front时，就是空
判断是否满了
元素满了之后back指向红框，back+1，back指向数组外，此时让back%N，back就会回到首元素位置
bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->back+1)%obj->N==obj->front; }//当back的下一个位置是front时候是满
在队列内插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (myCircularQueueIsFull(obj)) return false; //如果满了则退出 obj->a[obj->back]=value; obj->back=(obj->back+1)%obj->N; //插入之后，back要走到下一个位置 return true; }
删除队列内元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj->front++; obj->front=obj->front%obj->N; //跟back一样，要防止越界 return true; }
返回队首元素
int myCircularQueueFront(MyCircularQueue* obj) { if( myCircularQueueIsEmpty(obj)) return -1; else return obj->a[obj->front]; } //如果不为空，返回队首元素
获得队尾元素
int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; else return obj->a[(obj->back-1+obj->N)%obj->N]; }
小练习题：
5.现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N-1。其队内有效长度为？(假设 队头不存放数据)
A (rear - front + N) % N + 1
B (rear - front + N) % N
C ear - front) % (N + 1)
D (rear - front + N) % (N - 1)
选B，
空间释放
void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); //先释放数组空间，再释放给结构体创建的空间 free(obj); }
