【栈和队列】队列

顺序队列：

1. 入队：将新元素插入 rear 所指的位置，而后将rear加1。
2. 出队：删去front所指的元素，而后将front加1并返回被删元素。

1. front = rear 时，队列为空
2. 在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。

1.     "下溢"现象：当队列为空时，作 出队 运算产生的溢出现象。“下溢”是正常现象，经常使用做程序控制转移的条件。
2. "真上溢"现象：当队列满时，作 进队 运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
3. "假上溢"现象：因为入队和出队操做中，头尾指针只增长不减少，导致被删元素的空间永远没法从新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能因为尾指针已超越向量空间的上界而不能作入队操做。该现象称为"假上溢"现象。为了解决这个问题，咱们可使用‘循环队列’。（因此不少状况下，咱们不会使用普通的顺序表）

循环队列：

#define MaxQSize 100   //应根据具体状况定义该值
typedef char  QElemType;  //QElemType的类型依赖于具体的应用

typedef struct
{                  
	QElemType * base;	//初始化的动态分配存储空间
	int front;			//头指针，队非空时指向队头元素              
	int rear;			//尾指针，队非空时指向队尾元素的下一位置           
}CirQueue;

if(i+1 == MaxQSize) // i 表示front或rear
	i=0;
else
    i++;

i = (i+1) % MaxQSize；

1. 另设一布尔变量以区别队列的空和满；
2. 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
3. 使用一个计数器记录队列中元素的总数（即队列长度）。

bool InitQueue(CirQueue * Q)
{
	Q->base = (QElemType *)malloc(MaxQSize * sizeof(QElemType));
	if(!Q->base) exit(OVERFLOW);	//分配内存失败
	Q->front = Q->rear = 0;			//初始化为空栈
	return true;
}

bool QueueEmpty(CirQueue * Q)
{//由于少用一个元素，因此只有空队列才有 front = rear
	if (Q->front == Q->rear)
	{
		return true;
	}
	else 
		return false;
}

bool QueueFull(CirQueue * Q)
{//若是插入后尾指针的位置等于头指针的位置，则说明队列满了
	if ((Q->rear + 1) % MaxQSize == Q->front)
	{
		return true;
	}
	else
		return false;
}

bool EnQueue(CirQueue * Q, QElemType e)
{//插入元素e
	if (QueueFull(Q))
	{//若是队满，则返回false
		return false;
	}
	Q->base[Q->rear] = e;	//插入元素
	Q->rear = (Q->rear + 1) % MaxQSize;	//修改尾指针
	return true;
}

bool DeQueue(CirQueue * Q, QElemType * e)
{
	if (QueueEmpty(Q))
	{//若是队空，则返回false
		return false;
	}
	*e = Q->base[Q->front];	//返回元素值
	Q->front = (Q->front + 1) % MaxQSize;	//修改头指针
}

链队列 ：

typedef struct QNode
{
	QElemType data;			//数据域
	struct QNode * next;	//指针域
}QNode, *QueuePtr;

typedef struct
{
	QueuePtr front;	//队头指针
	QueuePtr rear;	//队尾指针
}LinkQueue;

bool InitQueue(LinkQueue * Q)
{
	Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));//建立头结点
	if (!Q->front) 
	{//若是内存分配失败
		exit(OVERFLOW);
	}
	Q->front->next = NULL;	//初始化空队列
	return true;
}

bool DestroyQueue(LinkQueue * Q)
{
	while(Q->front)
	{
		Q->rear = Q->front->next;//用rear暂时存储新的队头指针
		free(Q->front);	//释放内存
		Q->front = Q->rear;
	}
	return true;
}

bool EnQueue(LinkQueue * Q, QElemType e)
{
	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));//为新元素分配内存
	if (!p)
	{
		exit(OVERFLOW);
	}
	p->data = e;	//初始化新结点
	p->next = NULL;
	Q->rear->next = p;	//修改尾指针
	Q->rear = p;
	return true;
}

bool DeQueue(LinkQueue * Q, QElemType * e)
{
	if (Q->front == Q->rear)
	{//若是队空
		return false;
	}
	QueuePtr p = Q->front->next;	//保存第一个结点的位置
	*e = p->data;
	Q->front->next = p->next;	//第一个结点出队
	if (Q->rear == p)
	{//若是只有一个结点,置为空队
		Q->rear = Q->front
	}
	free(p);
	return true;
}