邏輯結(jié)構(gòu)

• FIFO
• 線性結(jié)構(gòu)：受限線性表

基本操作

• InitQueue(&Q)
• QueueEmpty(Q)
• EnQueue(&Q,x)
• DeQueue(&Q,&x)
• GetHead(Q,&x)

存儲結(jié)構(gòu)

1.順序存儲

1.1一般形式

• 數(shù)組形式
• rear、front雙指針 int類型數(shù)組下標(biāo)，front指向頭部，rear只想尾部的下一個(gè)位置
• 操作：隊(duì)不滿時(shí)，新元素添加到隊(duì)尾，隊(duì)尾指針加1；隊(duì)不空時(shí)，去除front值，front+1
• 判斷：rear=front隊(duì)為空，無法判斷隊(duì)列滿
• 存在假溢出問題，會導(dǎo)致空間的浪費(fèi)，因此設(shè)計(jì)循環(huán)隊(duì)列。

1.2循環(huán)隊(duì)列

• 使用取余運(yùn)算，使得指針可以循環(huán)的使用空間。
• 判斷：隊(duì)空rear=front，隊(duì)滿：采用犧牲一個(gè)存儲單元的方式，當(dāng)front=(rear+1)%maxsize

2.鏈?zhǔn)酱鎯?/h2>

2.1一般形式

• 帶有頭指針和尾指針的鏈隊(duì)列，rear指向最后一個(gè)元素//注意區(qū)別

//注意與堆棧數(shù)據(jù)結(jié)構(gòu)的不同，因?yàn)楹袃蓚€(gè)指針?biāo)孕枰嘁粚拥姆庋b
typedef struct
{
  ElemType data;
  struct LinkNode * next
}LinkNode;

typedef struct
{
  LinkNode *front, *rear;
}LinkQueue;

• 判斷：無頭節(jié)點(diǎn)，front與rear都為NULL時(shí)為空，有頭節(jié)點(diǎn)兩者相等為空
• 為什么加上頭節(jié)點(diǎn)：方便操作
• 優(yōu)點(diǎn)：適于數(shù)據(jù)元素變動(dòng)較大，同時(shí)不會產(chǎn)生溢出問題

2.2雙端隊(duì)列

• 兩端都可以進(jìn)行入隊(duì)與出隊(duì)的操作，分別叫前端和后端
• 輸出/輸出受限的雙端隊(duì)列：一端受到限制
• ?？碱}型：判斷序列能否輸出如何輸出