1.循环队列--队列的顺序表示和实现
#include<stdio.h>
#define MAXQSIZE 100
typedef struct {int* base;int front;int rear;
}SqQueue;int InitQueue(SqQueue& Q)
{Q.base = new int[MAXQSIZE];//为队列分配一个最大容量为MAXSIZE的数组空间if (!Q.base)return -1;Q.front = Q.rear = 0;return 1;
}int QueueLength(SqQueue Q)
{return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}void insertQueue(SqQueue& Q,int e)
{if ((Q.rear + 1) % MAXQSIZE == Q.front)//队满条件，尾指针在循环意义上加一等于头指针，表示队满return;Q.base[Q.rear] = e;Q.rear = (Q.rear + 1) % MAXQSIZE;return;
}int getTopQueue(SqQueue Q)//去队头元素
{if (Q.front != Q.rear)return Q.base[Q.front];
}
int DeQueue(SqQueue& Q)//出队(操作是将队头元素删除），队是先进先出
{if (Q.front == Q.rear)//队空return -1;int e = Q.base[Q.front];//保持队头元素Q.front = (Q.front + 1) % MAXQSIZE;//头指针加一return 1;
}void print(SqQueue Q) {for (int i = Q.front; i != Q.rear; i++){printf("%d ", Q.base[i]);}//printf("(rear)\n");
}
int main()
{SqQueue Q;InitQueue(Q);print(Q);int len=QueueLength(Q);printf("队列长为：%d\n",len);print(Q);printf("\n");printf("队元素：");insertQueue(Q,10);insertQueue(Q,20);insertQueue(Q,50);print(Q);printf("\n");int newlen = QueueLength(Q);printf("新队列长为：%d\n",newlen);int topnum=getTopQueue(Q);printf("新队头元素为：%d\n",topnum);DeQueue(Q);int newlen2 = QueueLength(Q);printf("出队后的新队列长为：%d\n", newlen2);int topnum2 = getTopQueue(Q);printf("出队后的新队列队头元素为%d\n", topnum2);print(Q);return 0;
}
1.1分析(理解/思路)：
初始化创建空队列时，令font=rear=0，每当插人新的队列尾元素时，尾指针rear 增1;每当删除队列头元素时，头指针 font减1。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。
1.2：假溢出
假设当前队列分配的最大空间为6，则当队列处于上图(d)所示的状态时不可再继续插入新的队尾元素，否则会出现溢出现象，即因数组越界而导致程序的非法操作错误。事实上，此时队列的实际可用空间并未占满，所以这种现象称为“假溢出”。这是由“队尾入队，队头出队”这种受限制的操作造成的。
1.3：假溢出问题：
怎样解决这种“假溢出”问题呢?一个较巧妙的办法是将顺序队列变为一个环状的空间，如下图 所示，称之为循环队列。
头、尾指针以及队列元素之间的关系不变，只是在循环队列中，头、尾指针“依环状增1”的操作可用“模”运算来实现。通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环”移动。
队头元素是J5，在元素J6人队之前，在Q.rear 的值为5，当元素J6人队之后，通过“模”运算，Q.rear=(Q.rear +1)%6，得到 Q.rear 的值为 0，而不会出现上图 (d)的“假溢出”状态。
1.4：队空队满如何判断：
在第二个图中，J7、J8、J9、J10相继入队，则队列空间均被占满，此时头、尾指针相同。在第三个图中，若J5和J6相继从第一个图所示的队列中出队，使队列此时呈“空”的状态，头、尾指针的值也是相同的。
由此可见,对于循环队列不能以头、尾指针的值是否相同来判别队列空间是“满”还是“空”。
在这种情况下，如何区别队满还是队空呢?
通常有以下两种处理方法。
(1)少用一个元素空间，即队列空间大小为m时，有m-1个元素就认为是队满。这样判断队空的条件不变，即当头、尾指针的值相同时，则认为队空; 而当尾指针在循环意义上加1后是等于头指针，则认为队满。因此，在循环队列中队空和队满的条件是:
队空条件：
Q.front == Q.rear;队满条件：
(Qrear+1)%MAXOSIZE==Q.font;1.5:初始化：
循环队列的初始化操作就是动态分配一个预定义大小为MAXQSIZE的数组空间。
base指向数组空间的首地址。
1.6：注意事项
出队和入队都要先判断队列是否为空！！！
2.链队--队列的顺序表示和实现
#include<stdio.h>
typedef struct QNode {int data;struct QNode* next;
}QNode,*QueuePtr;
typedef struct {QueuePtr front;//队头指针QueuePtr rear;//对尾指针
}LinkQueue;void InitQueue(LinkQueue& Q)
{Q.front = Q.rear = new QNode;Q.front->next = NULL;//头节点的指针域置空return;
}int EnQueue(LinkQueue& Q,int num)//入队
{QueuePtr p;p = new QNode;p->data = num;p->next = NULL;Q.rear->next = p;Q.rear = p;return 1;
}
int DeQueue(LinkQueue& Q, int &e)//出队
{if (Q.front == Q.rear)return -1;QueuePtr p;p = Q.front->next;//p指向队头元素e = p->data;//e保持队头元素的地址Q.front->next = p->next;if (Q.rear == p)Q.rear = Q.front;//最后一个元素被删，队尾指针指向头节点(链队出队需要注意的）//如果对尾指针也没了，因此需要队尾指针重新赋值（指向头节点）delete p;return e;
}int GetHead(LinkQueue Q)
{if (Q.front != Q.rear) {return Q.front->next->data;}return -1;
}int DeleteQueue(LinkQueue& Q, int val)//删除特定值
{QueuePtr p = Q.front;while (p->next!=NULL&&p->next->data!=val){p = p->next;}if (p->next == NULL) {return -1;}QueuePtr temp = p->next;p->next = temp->next;if (temp == Q.rear){Q.rear = p;}delete temp;return 1;
}
void ShowQueue(LinkQueue Q) {QueuePtr p = Q.front->next;while (p!=NULL){printf("%d ", p->data);p = p->next;}printf("\n");
}
int main()
{LinkQueue Q;InitQueue(Q);EnQueue(Q, 10);EnQueue(Q, 20);EnQueue(Q, 30);EnQueue(Q, 40);EnQueue(Q, 70);EnQueue(Q, 60);printf("初始链队中元素为：");ShowQueue(Q);printf("队头元素：%d\n", GetHead(Q));int e;printf("出队元素: %d ", DeQueue(Q, e));printf("\n");int head = GetHead(Q);if (head != -1) {printf("队头元素: %d\n", head); ShowQueue(Q);}else {printf("Queue is empty\n");}printf("删除队中值为30的节点后队中元素为：");DeleteQueue(Q, 30);ShowQueue(Q);}2.1分析(理解/思路)：
链队是指采用链式存储结构实现的队列。通常链队用单链表来表示，如图 3.15 所示。一个链队显然需要两个分别指示队头和队尾的指针(分别称为头指针和尾指针)才能唯一确定。这里和线性表的单链表一样，为了操作方便起见，给链队添加一个头结点，并令头指针始终指向头结点。
2.2：顺序和链式的入队和出队区别（！！！）：
入队：链队在入队前不需要判断队列是否是满的，因为是动态分配空间；
出队：链队在入队前需要判断链队是否为空。但是不同的是链队在出队后需要释放出队元素的所占空间；