1.队列的基本概念
1.1.队列的定义
队列只允许在一端插入（队头），在另一端删除（队尾）（FIFO）
1.2.队列的基本操作
initQueue(&Q);初始化队列
destroyQueue(&Q);销毁队列
enQueue(&Q, x);入队
deQueue(&Q, x);出队
getHead(Q, &x);取出队头元素
queueEmpty(Q);判断队空
2.队列的顺序存储结构
2.1.队列的初始化
#define maxSize 10 typedef struct{ //frnot为队头指针，rear为队尾指针 int front, rear; //采用静态数组存放数据 elemtype data[maxSize]; }sqQueue; bool initQueue(sqQueue &Q){ //队头指针和队尾指针都指向0 Q.rear = 0; Q.front = 0; } void testQueue(){ sqQueue Q; initQueue(Q); //后续操作 }
2.2.判断队空
bool queueEmpty(sqQueue Q){ //队空时，队头指针和队尾指针都指向0 if (Q.front == Q.rear) return true; else return false; }
2.3.入队
因为初始化队列的时候，front和rear指针都指向0，因此，需要牺牲一个存储空间，判断队满
bool enQueue(sqQueue &Q, elemType x){ //队满 if ((Q.rear + 1) % maxSize == Q.front) return false; //在队尾插入x Q.data[Q.rear] = x; //队尾元素+1取模 Q.rear = (Q.rear + 1) % maxSize; return true; }
2.4.出队
bool deQueue(sqQueue &Q, elemType &e){ //队空 if(Q.rear == Q.front) return false; //取出元素 e = Q.data[Q.front]; //front指针前移 Q.front = ((Q.front + 1) % maxSize); return true; }
2.5.获得队头元素
bool getHead(sqQueue &Q, elemType &e){ //队空 if (Q.front == Q.rear) return false; //取出队头元素 e = Q.data[front]; return true; }
2.6.队列中元素个数
(front + maxSize - rear) % maxSize
2.7.不牺牲一个存储空间的方法
2.7.1.增加size标记位
size标记队内元素个数
队空时，rear = front && size = 0；队满时，rear = front && size = maxSize。
typedef struct{ //增加一个size，初始化时，size为0； int size; int front, rear; elemType data[maxSize]; }
2.7.2.增加tag标记位
tag标记上一次的操作是删除/插入
插入后，tag = 1；删除后，tag = 0；
typedef struct{ //增加一个tag，删除后 tag = 0；插入后 tag = 1 int tag; int front, rear; elemType data[maxSize]; }
3.队列的链式存储结构
3.1.链表的初始化
//链表 typedef struct linkNode{ elemType data; strutct linkNode *next; }linkNode; typedef struct { //头尾指针 linkNode *rear, *front; }linkQueue; bool initQueue(linkQueue &Q){ //初始化时，front和rear都指向头结点 Q.rear = Q.front = (linkNode*)malloc(sizeof(linkNode)); if(Q.rear == NULL) return false; Q.front->next = NULL; return true; } void testQueue(){ linkQueue Q; initQueue(Q); //后续操作 }
3.2.入队
//带头结点 bool enQueue(linkQueue &Q, elemType e){ linkNode *s = (linkNode*)malloc(sizeof(linkNode)); s->data = e; s->next = NULL //将s插入到rear后 Q.rear->next = s; //rear后移到s Q.rear = s; return true; } //不带头结点 bool enQueue(linkQueue &Q, elemType e){ linkNode *s = (linkNode*)malloc(sizeof(linkNode)); s->data = e; s->next = NULL; //表不为空，直接插入rear之后 if (Q.rear) { Q.rear->next = s; Q.rear = s; } //表空，作为第一个节点，front和rear都指向s else { Q.rear = s; Q.front = s; } return true; }
3.3.出队
//带头结点 bool deQueue(linkQueue &Q, elemType &e){ //队空 if (Q.rear == Q.front) return false; //p标记第一个元素，输出第一个元素的值 linkNode *p = Q.front->next; e = q->data; //将p删除队列 Q.front->next = p->next; //p是队列中最后一个元素，则将rear指针指向front if (Q.rear == p) Q.rear = Q.front; free(p); return true; } //不带头结点 bool deQueue(linkQueue &Q, elemType &e){ //队不空 if (Q.front){ //取出队头元素的值 linkNode *temp = Q.front; e = Q.front->data; //队列只有一个元素 if (Q.rear == temp) Q.front = Q.rear = NULL; //队列元素>=2 else Q.front = Q.front->next; free(temp); } //队空 else return false; }
3.4.链式存储和顺序存储的去别
顺序存储采用数组，静态分配，需要判断队满情况；
顺序存储采用链表，动态分配，不需要判断队满情况
4.双端队列
5.王道课后题
#define maxSize 10 typedef struct { int tag, front, rear; elemtype data[maxSize]; }linkQueue; //tag = 0为队空；tag = 1为队满 //front初始化为0，指向队头元素；rear初始化为0，指向队尾元素 //入栈 bool enQueue(linkQueue &Q, elemType e){ //队满 if (Q.tag && Q.front = Q.rear) return false; //存入元素，并且改变rear值 Q.data[Q.rear] = e; Q.rear = (Q.rear + 1) % maxSize; //改变rear值之后，front和rear都指向同一个地方，则队满，改变tag if (Q.front == Q.rear) Q.tag = 1; return true; } //出栈 bool deQueue(linkQueue &Q, elemType &e){ //队空 if (!Q.tag && Q.front = Q.rear) return false; //取出元素，改变rear值 e = Q.data[Q.front]; //改变front值之后，front和rear都指向同一个地方，则队空，改变tag Q.front = (Q.front + 1) % maxSize; if (Q.front == Q.rear) Q.tag = 0; return true; }
typedef struct sqQueue{ int rear, front; int data[10]; }sqQueue; //top初始值为-1 typedef struct sqStack{ int top; int data[10]; }sqStack; void reverse(sqQueue& Q, sqStack S) { //将队列元素按顺序出队，并进栈 while (Q.rear == Q.front) { S.data[++S.top] = Q.data[Q.front]; Q.front = (Q.front + 1) % maxSize; } //将栈中元素按顺序出栈，并进队列 while (S.top == -1) { Q.data[Q.rear] = S.data[S.top--]; Q.rear = (Q.rear + 1) % maxSize; } }
//1.因为空间只增不减，所以要用链式存储结构，方便增加空间 //2.采用带头结点的循环链式存储结构 //队空：rear == front //队满：rear->next == front //4. typedef struct LNode{ elemType data; struct LNode *next; }LNode; typedef struct Queue{ struct LNode *rear, *front; }Queue; bool enQueue(QueQue &Q,elemType e){ if (Q.rear->next == Q.front) { 申请新空间 } Q.data[Q.rear] = e; Q.rear = Q.rear->next; return true; } bool deQueue(Queue &Q,elemType &e){ //队空 if (Q.rear == Q.front) return false; e = Q.data[Q.front]; Q.front = Q.front->next; return true; }
