【資料結構——佇列(C描述）】
- 一、佇列的順序表示
- （一）佇列的進隊和出隊演示
- （二）存在的問題
- （三）解決辦法
- （四）回圈佇列
- 1、回圈佇列初始化
- 2、回圈佇列入隊
- 3、回圈佇列出隊
- 二、鏈隊
- （一）鏈隊的表示
- 1、佇列的鏈式存盤結構
- 2、佇列運算指標變化狀況
- （二）鏈隊的基本操作
- 1、鏈隊的初始化
- 2、鏈隊的入隊
- 3、鏈隊的出隊
一、佇列的順序表示
（一）佇列的進隊和出隊演示
（二）存在的問題
設當前佇列分配的最大空間為MAXSIZE,則：
當Q.front = 0時且Q.rear = MAXSIZE時，若再有元素入隊，會發生溢位——真溢位，
當Q.front != 0是且Q.rear = MAXSIZE時，若再有元素入隊，會發生溢位——假溢位，
回圈佇列基本思想：把佇列設想成一個環形，即：Q.base[0]接在Q.base[MAXSIZE-1]之后，若Q.rear=MAXSIZE,則令 Q.rear=0.
（三）解決辦法
將順序佇列變為一個環狀的空間
//入隊
Q.base[Q.rear] = x;
Q.rear = (Q.rear + 1) % MAXSIZE;
//隊滿判定條件
(Q.rear + 1) % MAXSIZE == Q.front(少用一存盤單元)
//出隊
x = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXSIZE;
//隊空判定條件
Q.rear == Q.front;
（四）回圈佇列
1、回圈佇列初始化
#define MAXQSIZE 100
typedef struct
{
QElemType* base;
int front;
int rear;
}SqQueue;
Status InitQueue(SqQueue& Q)
{
Q.base = new QElemType[MASQSIZE];//開辟空間
if (!Q.base) exit(OVERFLOW);//存盤分配失敗
Q.front = Q.rear = 0;
return OK;
}
2、回圈佇列入隊
Status EnQueue(SqQueue& Q, QElemType e)
{
if ((Q.rear + 1) % MAXQSIZE == Q.front)
return ERROR;//隊滿
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
return OK;
}
3、回圈佇列出隊
Status DeQueue(SqQueue& Q, QElemType& e)
{
if (Q.front == Q.rear)
return ERROR;//隊空
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}
二、鏈隊
（一）鏈隊的表示
1、佇列的鏈式存盤結構
typedef struct QNode
{
QElemType data;
struct QNode* next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;//隊頭指標
QueuePtr rear;//隊尾指標
}LinkQueue;
2、佇列運算指標變化狀況
（二）鏈隊的基本操作
1、鏈隊的初始化
Status InitQueue(LinkQueue& Q)
{
Q.front = Q.rear = new QNode;
if(!Q.front) exit(OVERFLOW);
Q.front->next = NULL;
return OK;
}
2、鏈隊的入隊
Status EnQueue(LinkQueue& Q, QElemType e)
{
p = new QNode;
if (!p) exit(OVERFLOW);//存盤分配失敗
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
3、鏈隊的出隊
Status DeQueue(LinkQueue& Q, QElemType& e)
{
if (Q.front == Q.rear)
return ERROR;//佇列為空
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 OK;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/177061.html
標籤：其他