队列的实现
这里的队列我们使用链式队列，好处就是可以很方便的取出队头的元素。
使用顺序队列取出队头元素所花费的时间复杂度为O（N），把后面的元素向前移动一个下标所花费的时间。
链式队列的存储结构：
typedef int QueueDataType;
//节点类型
typedef struct QueueNode
{
QueueDataType data;
struct QueueNode* next;
}QNode;
//队列类型
typedef struct Queue
{
QNode* phead; //头指针
QNode* ptail; //尾指针 使用头指针和尾指针来实现队列的删除和插入操作。
int size;
}Que;
接口函数的实现
`
void QueueInit(Que* pq);
void QueueDestory(Que* pq);
void QueuePush(Que* pq, QueueDataType x);
void QueuePop(Que* pq);
QueueDataType QueueFront(Que* pq);
QueueDataType QueueBack(Que* pq);
int QueueSize(Que* pq);
bool QueueEmpty(Que* pq);
//实现
//初始化队列
void QueueInit(Que* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
//销毁队列，这里相当于单链表的销毁，一个节点一个节点销毁
void QueueDestory(Que* pq)
{
assert(pq);
//删除链式队列
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
}
//相当于单链表的尾插，先新建一个节点，初始化这个节点，尾插到队列中，这里考虑两种情况，队列为空和不为空的情况
void QueuePush(Que* pq, QueueDataType x)
{
assert(pq);
//新建节点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc failed!\n");
return;
}
newnode->data = x;
newnode->next = NULL;
//考虑此时的队列为空
if (pq->ptail == NULL)
{
assert(pq->phead == NULL);
pq->phead = pq->ptail = newnode;
}
else
{
//不为空时，把newnode赋值给phead->next,然后ptail = newnode
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
//相当于单链表的头删。需要考虑两种情况，队列为空就不可以删除，队列不为空只有一个节点phead和ptail都要赋值成NULL，否则会出现ptail为野指针的情况，多个节点时，相当于单链表的头删，
void QueuePop(Que* pq)
{
//相当于单链表的头删
assert(pq);
//处理队列为空的情况
assert(!QueueEmpty(pq));
//处理只有一个节点的情况
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else //考虑多个节点的情况
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
QueueDataType QueueFront(Que* pq)
{
assert(pq);
//处理队列为空的情况
assert(!QueueEmpty(pq));
return pq->phead->data;
}
//返回队列的尾部元素，这里会在用队列实现栈的时候用到
QueueDataType QueueBack(Que* pq)
{
assert(pq);
//处理队列为空的情况
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
int QueueSize(Que* pq)
{
assert(pq);
return pq->size;
}
bool QueueEmpty(Que* pq)
{
assert(pq);
return pq->phead == NULL && pq->ptail == NULL;
//return pq->size == 0;
}
用队列实现栈
leetcode做题链接
主要思想：用两个队列来实现一个栈的功能，先进后出，后进先出的功能，我们可以这样，在不为空的队列里入数据，然后再把数据前n-1个数数据倒入另一个队列中，具体的过程用图展示：
第一步：准备两个队列，开始入数据
第二步：往不为空的队列里入数据，如果两个都为空，任选一个入数据
push 四次。可得队列中的数据如下图所示：
第三步：出数据，需要先把q1中的数据1、2、3倒入q2中，然后使用QueueBack()接口获取队尾数据4。
以上就是出数据和入数据的过程。
具体代码如下：
typedef struct {
Que q1;
Que q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
if(obj == NULL)
{
perror("malloc failed!\n");
return NULL;
}
QueueInit(&obj->q1);
QueueInit(&obj->q2);
return obj;
}
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1,x); //入数据，往不为空的队列里如数据
}
else
{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj) {
//假设为空
Que* pEmptyQ = &obj->q1;
Que* pNonEmptyQ = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
pEmptyQ = &obj->q2;
pNonEmptyQ = &obj->q1;
}
//倒数据,把非空队列的数据导入空队列，剩余一个就是栈顶元素
while(QueueSize(pNonEmptyQ)>1)
{
QueuePush(pEmptyQ, QueueFront(pNonEmptyQ));
QueuePop(pNonEmptyQ);
}
int top = QueueFront(pNonEmptyQ);
QueuePop(pNonEmptyQ);
return top;
}
int myStackTop(MyStack* obj) {
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
用栈实现队列
leetcode 做题链接
基本思想
使用两个栈，一个为入数据的栈，一个为出数据的栈，把数据入到入数据的栈，然后出数据到出数据的栈，基本方法如下：入队列1 2 3 4。
第一步：初始化两个栈。
第二步：入数据push 1 2 3 4
第三步：导数据到popst中
第四步：从popst中出数据
实现代码如下：
typedef struct {
ST pushst;
ST popst;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
if(obj==NULL)
{
perror("malloc failed!\n");
return NULL;
}
STInit(&obj->pushst);
STInit(&obj->popst);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
STPush(&obj->pushst,x);
}
int myQueuePop(MyQueue* obj) {
int front = myQueuePeek(obj);
STPop(&obj->popst);
return front;
}
int myQueuePeek(MyQueue* obj) {
if(STEmpty(&obj->popst))
{
while(!STEmpty(&obj->pushst))
{
STPush(&obj->popst,STTop(&obj->pushst));
STPop(&obj->pushst);
}
}
return STTop(&obj->popst);
}
bool myQueueEmpty(MyQueue* obj) {
return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}
void myQueueFree(MyQueue* obj) {
STDestory(&obj->pushst);
STDestory(&obj->popst);
free(obj);
}
设计循环队列
leetcode做题链接
循环队列的要点：如何用一个顺序表实现一个循环队列，front为队头，rear为队尾，判满：rear + 1 == front为满，判空：rear == front 为空。
第一步，初始化一个队列，k为5，n为6
第二步：出队列 front++；再入数据 6、7。
此时的rear，跑到了front的前面，我们可以 让rear % （k+1）保持rear永远不会越界front也可以使用这个公式保证front永远不会越界
获取队尾元素的两种方法：
求元素的个数的方法： （rear - front + k+1）% （k+1）
具体的实现代码如下：文章来源：https://www.toymoban.com/news/detail-512164.html
typedef struct {
int front;
int rear;
int k;
int* a;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear+1)%(obj->k+1) == obj->front;
}
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
if(obj == NULL)
{
perror("malloc failed!\n");
return NULL;
}
obj->a = (int*)malloc(sizeof(int)*(k+1));
if(obj->a == NULL)
{
perror("malloc failed!\n");
return NULL;
}
obj->front = obj->rear = 0;
obj->k = k;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->a[obj->rear] = value;
obj->rear++;
obj->rear %= (obj->k+1);
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj->front++;
obj->front%=(obj->k+1);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
//return obj->a[(obj->rear+obj->k)%(obj->k+1)];
if(obj->rear==0)
{
return obj->a[obj->k];
}
else
{
return obj->a[obj->rear-1];
}
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
好的我们下一篇再见。文章来源地址https://www.toymoban.com/news/detail-512164.html
到了这里，关于栈和队列（二） 队列的实现，用栈实现队列，用队列实现栈，设计循环队列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
