1、定义
从栈的学习我们知道栈是只允许在一端进行插入或删除操作的线性表。
而队列：是只允许在一端进行插入在另一端删除的线性表。在生活中比如说到饭堂排队打饭，一端进一端出，这就是队列。
2、队列顺序实现
2.1、队列的基本形式
typedef int Elemtype;//需要时可以改为自己需要的元素类型
#define MaxSize 10 //定义队列中元素的最大值
typedef struct {Elemtype data[MaxSize];//用静态数组存放列表元素int front, rear;//队头指针和队尾指针
}SqQueue;void textQueue()
{SqQueue Q;
}2.2、入队操作
typedef struct {Elemtype data[MaxSize];//用静态数组存放列表元素int front, rear;//队头指针和队尾指针
}SqQueue;bool QueueEmpty(SqQueue &Q)
{if (Q.front == Q.rear)//队空条件return false;else return true;
}
//入队
bool EnterQueue(SqQueue& Q, Elemtype x)
{if ((Q.rear+1)% MaxSize==Q.front)return false;//队满则报错Q.data[Q.rear] = x;//新元素加入队尾Q.rear = (Q.rear + 1) % MaxSize;//队尾指针加一取模return true;
}
Q.rear = (Q.rear + 1) % MaxSize;许多人看到这一条就会疑惑，为什么要加一取模？
队列并没有所规定的头或尾，如果加到data[MaxSize]，而data[0]没有元素，便能将元素加到data[0]，而不用浪费空间。这样操作便能将队列在存储空间在逻辑上变成了“环状”。
用模运算便能从最大值变为最小值：例如你现在元素存储到data[9]，（9+1）%10=0，你的下一个元素便能存储到data[0]。
2.3、出队操作
进行出队操作时要记住一件事：只能让对头元素出队！
typedef int Elemtype;//需要时可以改为自己需要的元素类型
#define MaxSize 10 //定义队列中元素的最大值
typedef struct {Elemtype data[MaxSize];//用静态数组存放列表元素int front, rear;//队头指针和队尾指针
}SqQueue;//出队(删除一个队头元素，并用x返回)
bool DeleteQueue(SqQueue &Q,Elemtype x)
{if (Q.rear == Q.front)//判断队空return false;//队空则判错x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;//队头指针后移return true;
}
注：入队还是出队都是让指针后移一位
2.4、获得队头元素
获得队头元素这个操作与出队相似，不过获得队头元素只是将队头元素通过x返回，并不改变队列里的数据。
bool GetHead(SqQueue& Q, Elemtype &x)
{if (Q.rear == Q.front)//判断队空return false;//空则判错x = Q.data[Q.front];return true;
}2.5、判断队空/队满
一般来说队空/队满很容易判断，这里给出两个方法：
（1）计算出队列中的元素个数：(rear+MaxSize-front)%MaxSize
队满条件是(Q.rear + 1) % MaxSize ==Q.front，队空条件是rear=front。
（2）设置一个长度，在入队或出队过程中进行计算：
typedef int Elemtype;//需要时可以改为自己需要的元素类型
#define MaxSize 10 //定义队列中元素的最大值
typedef struct {Elemtype data[MaxSize];//用静态数组存放列表元素int front, rear;//队头指针和队尾指针int size;
}SqQueue;
初始化为rear=front=0，size=0
队满条件是size==MaxSize，队空条件是size==0。
3、队列的链式实现
3.1、链式队列的一个结点
typedef int Elemtype;
typedef struct LinkNode {//链式队列结点Elemtype data;struct LinkNode* next;
}LinkNode;typedef struct {//链式队列LinkNode* front, *rear;//队列的队头和队尾指针
}LinkQueue;3.2、初始化（带头结点）
//初始化队列（带头结点）
void InitQueue(LinkQueue& Q)
{Q.front = Q.rear=(LinkNode*)malloc(sizeof(LinkNode));Q.front->next = NULL;
}
//判断队列是否为空
bool IsEmpty(LinkQueue& Q)
{if (Q.front == Q.rear)return true;elsereturn false;
}3.3、入队（带头结点）
//新元素入队（带头结点）
void EnQueue(LinkQueue &Q,Elemtype x)
{LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));s->data = x;s->next = NULL;Q.rear ->next= s;//新结点插入到rear后面Q.rear = s;//修改表尾指针
}3.4、入队（不带头结点）
//新元素入队（不带头结点）
void EnQueue(LinkQueue& Q, Elemtype x)
{LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));s->data = x;s->next = NULL;if (Q.front = NULL)//在空列中插入第一个元素{Q.front = s;//修改队头队尾指针Q.rear = s;}else {Q.rear->next = s;//新结点插入到rear后面Q.rear = s;//修改表尾指针}
}3.5、出队（带头结点）
//出队（带头结点）
bool DeQueue(LinkQueue& Q, Elemtype& x)
{if (Q.front == Q.rear)//空队返回return false;LinkNode* p = Q.front->next;//x = p->data;//用变量x返回队头指针Q.front->next = p->next;//修改头结点的next指针if (Q.rear = p)//此次是最后一个结点出队Q.rear = Q.front;//修改rear指针free(p);//释放结点空间return true;
}
3.6、出队（不带头结点）
//出队（不带头结点）
bool DeQueue(LinkQueue& Q, Elemtype& x)
{if (Q.front == NULL)return false;//空队LinkNode* p = Q.front;//p指向出队的头结点x = p->data;//用x返回队头元素Q.front = p->next;//修改front指针if (Q.rear == p)//此次是最后一个结点出队{Q.front = NULL;//front指向NULLQ.rear = NULL;//rear指向NULL}free(p);return true;
}