## 用队列实现栈 用栈实现队列 设计循环队列

news/2024/8/6 11:47:25/文章来源:https://blog.csdn.net/2301_78957570/article/details/139202683

## 用队列实现栈

使用两个队列实现栈：

### 代码（c语言）：

``````typedef int QDataType;
// 链式结构：表示队列
typedef struct QListNode
{struct QListNode* _next;QDataType _data;
}QNode;// 队列的结构
typedef struct Queue
{QNode* _front;QNode* _rear;int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q) {assert(q);q->size = 0;q->_front = NULL;q->_rear = NULL;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data) {assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("QueuePush()::malloc()");return;}newnode->_data = data;newnode->_next = NULL;//队列为NULLif (q->_front == NULL){q->_front = q->_rear = newnode;}else{q->_rear->_next = newnode;q->_rear = q->_rear->_next;}q->size++;
}
// 队头出队列
void QueuePop(Queue* q) {assert(q);assert(q->size != 0);//单个节点if (q->_front == q->_rear){free(q->_front);q->_front = q->_rear = NULL;}//多个节点else{QNode* next = q->_front->_next;free(q->_front);q->_front = next;}q->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* q) {assert(q);assert(q->_front);//队头不能为NULLreturn q->_front->_data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q) {assert(q);assert(q->_rear);//队尾不能为NULLreturn q->_rear->_data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q) {return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q) {assert(q);return q->size == 0;
}
// 销毁队列
void QueueDestroy(Queue* q) {assert(q);QNode* cur = q->_front;while (cur){QNode* next = cur->_next;free(cur);cur = next;}q->_front = q->_rear = NULL;q->size = 0;}``````

``````//使用两个队列实现栈
typedef struct {Queue q1;Queue q2;} MyStack;//初始化栈
MyStack* myStackCreate() {//创建一个栈MyStack* newStk = (MyStack*)malloc(sizeof(MyStack));//初始化栈(即初始化两个队列)QueueInit(&(newStk->q1));QueueInit(&(newStk->q2));return newStk;
}//入栈
void myStackPush(MyStack* obj, int x) {//假设法找不为NULL的队列Queue* noempty = &obj->q1;if(QueueSize(noempty) == 0){noempty = &obj->q2;}//往不为NULL队列中插入QueuePush(noempty,x);
}//出栈
int myStackPop(MyStack* obj) {//假设法判断NULL队列，非NULL队列Queue* empty = &obj->q1;Queue* noempty = &obj->q2;if(QueueSize(noempty) == 0){noempty = &obj->q1;empty = &obj->q2;}//将size - 1个数据移动到NULL队列中while(QueueSize(noempty) > 1){QueuePush(empty,QueueFront(noempty));QueuePop(noempty);}//出栈int pop = QueueBack(noempty);QueuePop(noempty);return pop;}//获取栈顶元素
int myStackTop(MyStack* obj) {Queue* noempty = &obj->q1;if(QueueSize(noempty) == 0){noempty = &obj->q2;}//获取栈顶数据，也就是队尾的数据return QueueBack(noempty);}//判NULL
bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);}//销毁栈
void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);}``````

## 用栈实现队列

### 代码（c语言）：

``````typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;// 初始化和销毁
void STInit(ST* pst)
{assert(pst);pst->a = NULL;// top指向栈顶数据的下一个位置pst->top = 0;// top指向栈顶数据//pst->top = -1;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;}pst->a[pst->top] = x;pst->top++;
}void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}// 取栈顶数据
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}// 判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}// 获取数据个数
int STSize(ST* pst)
{assert(pst);return pst->top;
}
typedef struct {ST pushst;//用来存储数据ST popst;//用来导出数据} MyQueue;``````

``````//用两个栈实现队列
MyQueue* myQueueCreate() {MyQueue* new = (MyQueue*)malloc(sizeof(MyQueue));STInit(&new->pushst);STInit(&new->popst);return new;
}//入队列
void myQueuePush(MyQueue* obj, int x) {STPush(&obj->pushst,x);//插入至数据栈（pushst）中}//查看队头元素
int myQueuePeek(MyQueue* obj) {//查看出数据栈（popst），中是否有数据，有则直接查看栈顶数据，没有就把存数据栈（pushst）导入到 出数据栈（popst）中if(STEmpty(&obj->popst)){//把pushst数据全部导入popstwhile(!STEmpty(&obj->pushst)){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}}//返回出数据栈（popst）栈顶数据return STTop(&obj->popst);}//出队列
int myQueuePop(MyQueue* obj) {//它会帮我们导数据到popst中，popst栈顶的数据就是我们要删除的数据int pop = myQueuePeek(obj);STPop(&obj->popst);return pop;
}//判空
bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->pushst) && STEmpty(&obj->popst);//两个栈为NULL则队列为NULL}//销毁队列
void myQueueFree(MyQueue* obj) {STDestroy(&obj->pushst);STDestroy(&obj->popst);free(obj);
}``````

## 设计循环队列

### 代码：

``````typedef struct {int* a;int head;int rear;//指向最后一个数据的下一个空间int k;
} MyCircularQueue;//初始化循环队列
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* new = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//多开一个空间，用来解决数据为满与空的矛盾问题，当然也可以在结构体多加个size解决new->a = (int*)malloc(sizeof(int) * (k + 1));new->head = 0;new->rear = 0;//尾数据的下一个位置new->k = k;return new;
}//插入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//判断循环队列满没有，满则不能继续插入if((obj->rear + 1) % (obj->k + 1) == obj->head)//当尾数据指针 + 1 = 头指针时，队列满return false;obj->a[obj->rear] = value;obj->rear++;obj->rear %= obj->k + 1;//循环return true;
}//返回队列头数据
}//返回队列尾数据，即找尾指针指向的上一个地方
int myCircularQueueRear(MyCircularQueue* obj) {if(obj->head == obj->rear)return -1;return obj->a[(obj->k + obj->rear) % (obj->k + 1)];//往前绕k-1去找rear之前的一个数据}//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//空return obj->head == obj->rear;
}//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear + 1) % (obj->k + 1) == obj->head;}//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}``````

### 黑白按键-第13届蓝桥杯选拔赛Python真题精选

[导读]&#xff1a;超平老师的Scratch蓝桥杯真题解读系列在推出之后&#xff0c;受到了广大老师和家长的好评&#xff0c;非常感谢各位的认可和厚爱。作为回馈&#xff0c;超平老师计划推出《Python蓝桥杯真题解析100讲》&#xff0c;这是解读系列的第67讲。 黑白按键&#xf…

### YOLOv8+PyQt5面部表情检测系统完整资源集合(yolov8模型，从图像、视频和摄像头三种路径识别检测，包含登陆页面、注册页面和检测页面)

1.资源包含可视化的面部表情检测系统&#xff0c;基于最新的YOLOv8训练的面部表情检测模型&#xff0c;和基于PyQt5制作的可视化面部表情检测系统&#xff0c;包含登陆页面、注册页面和检测页面&#xff0c;该系统可自动检测和识别图片或视频当中出现的八类面部表情&#xff1a…

### vue 引入 emoji 表情包

vue 引入 emoji 表情包 一、安装二、组件内使用 一、安装 npm install --save emoji-mart-vue二、组件内使用 import { Picker } from "emoji-mart-vue"; //引入组件<picker :include"[people,Smileys]" :showSearch"false" :showPreview&q…