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; }