麦克算法|4指针与队列队列|c++|指针

文章目录

指针
- 例一
- 例二
线性队列
- 队列手动实现
- stl队列
循环队列
- 定义
- 代码实现
- 真题
优先队列

指针

文章图片

例一

文章图片

输出：102030200
说明：

文章图片

例二

文章图片
输出：65 A
线性队列队列手动实现

文章图片

文章图片

stl队列 【麦克算法|4指针与队列】

文章图片

循环队列定义

文章图片

代码实现

#include #include #define MAXSIZE 100 //最大队列长度 #define OK 1 #define ERROR 0 typedef int ElemType; typedef int Status; typedef struct { ElemType *base; //队列空间 int front; //队头指针 int rear; //队尾指针，若队尾不为空，则指向队尾元素的下一个位置 } SqQueue; //初始化循环队列 Status initQueue(SqQueue &Q) { Q.base = (ElemType *) malloc(MAXSIZE * sizeof(ElemType)); //申请空间 Q.front = Q.rear = 0; //队空 return OK; } //入队 Status enQueue(SqQueue &Q, ElemType e) { if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR; //队满，无法添加 Q.base[Q.rear] = e; //插入元素 Q.rear = (Q.rear + 1) % MAXSIZE; //队尾指针+1 return OK; } //出队 Status deQueue(SqQueue &Q, ElemType &e) { if (Q.front == Q.rear) return ERROR; //队空，无法删除 e = Q.base[Q.front]; Q.front = (Q.front + 1) % MAXSIZE; //队头指针+1 return OK; } //返回队列长度 Status length(SqQueue &Q) { return (Q.rear - Q.front + MAXSIZE) % MAXSIZE; }

真题

文章图片

typedef struct { ElemType *elem; //队列空间 int front; //队头指针 int rear; //队尾指针，若队尾不为空，则指向队尾元素的下一个位置 } CTagQueue; //判满 bool Full(CTagQueue Q) { if(Q.tag==1 && Q.front==Q.rear) return true; return false; } //判空 bool Empty(CTagQueue Q) { if(Q.tag==0 && Q.front==Q.rear) return true; return false; } //插入元素 x status EnCQueue(CTagQueue &Q,ElemType x) { if(Full(Q)) { return ERROR; } Q.elem[Q.rear] = x; Q.rear=(Q.rear+1)%Q.maxSize; if(Q.rear == Q.front) Q.tag=1; return OK; } //出队 Status DeCQueue(CTagQueue &Q,ElemType &x) { If(Empty(Q)) return ERROR; x=Q.elem[Q.front]; Q.front=(Q.front+1)%Q.maxSize; if(Q.front==Q.rear) Q.tag=0; return OK; }

优先队列

//大顶堆 = 最大优先队列 -> 最大元素优先出队 // 这里一定要有空格，不然成了右移运算符↓↓ priority_queue , less > q; priority_queue q; //默认大顶堆，故可以这样简写//小顶堆 = 最小优先队列 -> 最小元素优先出队 // 这里一定要有空格，不然成了右移运算符↓↓ priority_queue , greater > q;

#include #include using namespace std; int main() { //对于基础类型默认是大顶堆 priority_queue a; //等同于 priority_queue, less > a; // 这里一定要有空格，不然成了右移运算符↓↓ priority_queue, greater > c; //这样就是小顶堆 priority_queue> b; for (int i = 0; i < 5; i++) { a.push(i); c.push(i); } while (!a.empty()) { cout << a.top() << ' '; a.pop(); } cout << endl; while (!c.empty()) { cout << c.top() << ' '; c.pop(); } cout << endl; b.push("abc"); b.push("abcd"); b.push("cbd"); while (!b.empty()) { cout << b.top() << ' '; b.pop(); } cout << endl; return 0; }

具体的内容后续会讲到…