【棧和隊列】隊列

順序隊列：

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