【数据结构初阶】详解：实现循环队列、用栈实现队列、用队列实现栈

一、循环队列

1、题目简述

与队列的区别：循环队列的空间大小是固定的，且队尾连接队头形成循环。

要实现的方法：

2、方法讲解

我们开始就说过，循环队列的数据储存的数量是固定的，为了方便讲解，我们这里设队列可储存4个数据。即 k=4。

2.1、了解tail的指向

我们将队列的数据存放在数组中，head为队头下标，tail为队尾的下一个元素的下标。

tail为队尾的下一个元素的下标 原因：
若指向队尾数据：
当对列为空时，head、tail均指向首，即head=tail=0
而当队列有一个元素时，tail指向队尾，则仍有head=tail=0
产生歧义，无法区分队列是否有元素。
故，tail必须指向队尾元素的下一个元素

2.2、了解空间是如何利用的

注：队列遵循先进先出的规则
下面来举例了解数据的循环入队列：
1、入三个数据1,2，3

2、出两次数据

3、入三个数据4，5，6

在有限空间内，保证先进先出，空间重复使用。
那么问题来了：如何判断队列是否为空？

2.3、如何判断队列是否为空（假溢出问题）？

假溢出：空、满时判断条件相同。

此时无法区分空、满。
为了解决假溢出问题，我们有两种方法

• 方法一：通过size来计录数据
  空：size = 0
  满：size = k (k:队列可储存数据个数)

• 方法二：多开一个空间
  k = 4 (最多push入4个数据)
  
  push入4个数据 1，2，3，4
  
  空一个空间出来，则满的时候 head不可能等于tail，假溢出问题就解决了。
  已经入了4个数据了，想要再入数据就要先出数据，把空间空出来。

pop 出三次

push 入 5,6，7

由上可得：

空： head == tail
满： （tail+1）% （k+1）== head

2.4、实现代码

1、初始化

2、获取队首元素

3、取尾

在取尾返回时，也可写为

//数组
typedef struct {int* a;//数组下标int head;int tail;//指向尾的下一个int k;
} MyCircularQueue;//初始化
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//开k+1个数组空间obj->a = (int*)malloc(sizeof(int) * (k + 1));obj->head = obj->tail = 0;obj->k = k;return obj;
}
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->head == obj->tail;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail + 1) % (obj->k + 1) == obj->head;
}
//入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj))return false;obj->a[obj->tail] = value;obj->tail++;obj->tail %= (obj->k + 1);return true;
}
//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return false;obj->head++;obj->head %= obj->k + 1;return true;
}
//找头
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[obj->head];
}
//取尾
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;elsereturn obj->tail==0? obj->a[obj->k] : obj->a[obj->tail-1];
}//释放
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

二、用栈实现队列

1、题目简述

注意：C语言不支持栈，我们需要先模拟栈。
模拟栈在这里就不赘述了，以下是C语言模拟的栈：

typedef int STDataType;
typedef struct Stack
{STDataType* a;//指针指向数组int top;int capacity;//数组大小
}ST;//初始化与销毁
void STInit(ST* pst)
{assert(pst);//指针不为空pst->a = NULL;//若初始化top=0；++之后，当要入栈的数据入完，top指向的是栈顶元素的下一个位置（因为top进行了++）//若初始化top=-1；++之后，当要入栈的数据入完，top指向的是栈顶元素pst->top = 0;pst->capacity = 0;
}
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}//入栈、出栈
void STPush(ST* pst, STDataType x)
{assert(pst);//扩容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity*sizeof(STDataType));//扩容是否成功if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}//入栈：给数组（栈）放入值之后，top++pst->a[pst->top] = x;//数组a中的元素为xpst->top++;//若初始化top=0；++之后，当要入栈的数据入完，top指向的是栈顶元素的下一个位置（因为top进行了++）//若初始化top=-1；++之后，当要入栈的数据入完，top指向的是栈顶元素}
void STPop(ST* pst)//出栈：删除数据
{assert(pst);assert(pst->top > 0);//栈不为空pst->top--;
}//取栈顶数据
STDataType STTop(ST* pst)
{assert(pst);return pst->a[pst->top - 1];//若初始化top=0；++之后，当要入栈的数据入完，top指向的是栈顶元素的下一个位置（因为top进行了++）//所以栈顶元素是pst->top-1
}//判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;//top为0，即为空，返回1//不为空，返回0
}//获取数据个数
int STSize(ST* pst)
{assert(pst);return pst->top;
}

2、方法讲解

• 栈：从栈顶入、从栈顶出。满足先进后出。

     一种入栈顺序，可有多种（边进边出）出栈顺序
  

• 队列：从队尾入、从队头出。满足先进先出。

  一种入队顺序，只有一种出队顺序。
  

使用两个栈，一个只入数据，一个只出数据。要用栈来实现队列的顺序特点。

2.1、讲解

1、入数据1,2，3,4

2、出数据
如果popst内的数据为空，就将pushst内的数据导入popst中，此时从popst中按栈的顺序出数据时，所出顺序即为队列的出数据顺序。

入的数据与出的数据的顺序相同，符合队列先进先出的逻辑。

2.2、实现代码

typedef int STDataType;
typedef struct Stack
{STDataType* a;//指针指向数组int top;int capacity;//数组大小
}ST;//初始化与销毁
void STInit(ST* pst)
{assert(pst);//指针不为空pst->a = NULL;//若初始化top=0；++之后，当要入栈的数据入完，top指向的是栈顶元素的下一个位置（因为top进行了++）//若初始化top=-1；++之后，当要入栈的数据入完，top指向的是栈顶元素pst->top = 0;pst->capacity = 0;
}
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}//入栈、出栈
void STPush(ST* pst, STDataType x)
{assert(pst);//扩容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity*sizeof(STDataType));//扩容是否成功if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}//入栈：给数组（栈）放入值之后，top++pst->a[pst->top] = x;//数组a中的元素为xpst->top++;//若初始化top=0；++之后，当要入栈的数据入完，top指向的是栈顶元素的下一个位置（因为top进行了++）//若初始化top=-1；++之后，当要入栈的数据入完，top指向的是栈顶元素}
void STPop(ST* pst)//出栈：删除数据
{assert(pst);assert(pst->top > 0);//栈不为空pst->top--;
}//取栈顶数据
STDataType STTop(ST* pst)
{assert(pst);return pst->a[pst->top - 1];//若初始化top=0；++之后，当要入栈的数据入完，top指向的是栈顶元素的下一个位置（因为top进行了++）//所以栈顶元素是pst->top-1
}//判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;//top为0，即为空，返回1//不为空，返回0
}//获取数据个数
int STSize(ST* pst)
{assert(pst);return pst->top;
}
//两个栈实现队列
typedef struct {ST pushst; //入数据ST popst;  //出数据
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));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) {//如果popst为空，就倒数据，倒完的popst的顺序为先进先出if(STEmpty(&obj->popst)){//倒数据while(!STEmpty(&obj->pushst)){int top = STTop(&obj->pushst);STPush(&obj->popst,top);STPop(&obj->pushst);}}return STTop(&obj->popst);
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->popst) && STEmpty(&obj->pushst);
}void myQueueFree(MyQueue* obj) {STDestroy(&obj->popst);STDestroy(&obj->pushst);free(obj);
}

三、用队列实现栈

1、题目简述

C语言模拟的队列：

typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue//可避免使用二级指针和传多个参数
{int size;//size为每个节点的编号，每增加一个，size++QNode* phead;QNode* ptail;
}Queue;
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->size = 0;pq->phead = NULL;pq->ptail = NULL;
}//销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}//队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc error");return;}newnode->next = NULL;newnode->val = x;if (pq->phead == NULL)//原队列无节点{pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}//队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);//只有一个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--;
}//找头数据
QDataType QueueFront(Queue* pq)
{assert(pq);//assert(pq->phead);return pq->phead->val;
}//找尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
//统计个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

2、方法讲解

2.1、讲解

1、入栈 1,2，3,4
判断哪一个队列为空，入到为空的队列中

2、删除栈顶数据
将不为空的队列中的队尾数据之前的所有数据导入为空的队列中，而原队列中只剩下要删除的元素。

//删除栈顶元素
int myStackPop(MyStack* obj) {//将该队列队尾之前的元素（size-1）push到空的队列中//原队列中只剩下要删除的元素Queue* empty = &obj->q1;Queue* nonEmpty = &obj->q2;if (!QueueEmpty(&obj->q1)){empty = &obj->q2;nonEmpty = &obj->q1;}while (QueueSize(nonEmpty) > 1){QueuePush(empty, QueueFront(nonEmpty));QueuePop(nonEmpty);}int top = QueueFront(nonEmpty);QueuePop(nonEmpty);return top;
}

2.2、实现代码

//两个队列实现栈（后进先出）
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue//可避免使用二级指针和传多个参数
{int size;//size为每个节点的编号，每增加一个，size++QNode* phead;QNode* ptail;
}Queue;
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->size = 0;pq->phead = NULL;pq->ptail = NULL;
}//销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}//队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc error");return;}newnode->next = NULL;newnode->val = x;if (pq->phead == NULL)//原队列无节点{pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}//队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);//只有一个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--;
}//找头数据
QDataType QueueFront(Queue* pq)
{assert(pq);//assert(pq->phead);return pq->phead->val;
}//找尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
//统计个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}typedef struct {//匿名结构体Queue q1;Queue q2; //两个队列
} MyStack;//初始化
MyStack* myStackCreate() {MyStack* obj = (MyStack*)malloc(sizeof(MyStack));//malloc开辟的空间在出函数后不会销毁QueueInit(&obj->q1);QueueInit(&obj->q2);//优先级->高于&return obj;
}
//入栈
void myStackPush(MyStack* obj, int x) {//push到不为空的队列中if (!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);}else{QueuePush(&obj->q2, x);}}
//删除栈顶元素
int myStackPop(MyStack* obj) {//将该队列队尾之前的元素（size-1）push到空的队列中//原队列中只剩下要删除的元素Queue* empty = &obj->q1;Queue* nonEmpty = &obj->q2;if (!QueueEmpty(&obj->q1)){empty = &obj->q2;nonEmpty = &obj->q1;}while (QueueSize(nonEmpty) > 1){QueuePush(empty, QueueFront(nonEmpty));QueuePop(nonEmpty);}int top = QueueFront(nonEmpty);QueuePop(nonEmpty);return top;
}
//找栈顶元素
int myStackTop(MyStack* obj) {//找不为空的队尾数据if (!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

四、谢谢观看