順序循環隊列

• 思維導圖：
• 隊列的定義：
• 隊列的特點
• 隊列的基本操作：
• 順序循環隊列基本操作的實現：
• • 情況一：rear和front指向同一位置時
  • • 隊列定義：
    • 隊列初始化：
    • 入隊：
    • 出隊：
    • 隊列判空：
    • 返回隊頭元素：
  • 情況二：rear在front后面
  • • 隊列定義：
    • 隊列初始化：
    • 入隊：
    • 出隊：
    • 隊列判空：
    • 返回隊頭元素：

思維導圖：

隊列的定義：

隊列依舊是一種特殊的線性表。但是它只允許在一端進行插入，在另一端進行刪除操作。

隊列的特點

FIFO：first in first out

隊列的基本操作：

初始化隊列：InitQueue(&Q)銷毀隊列：DestoryQueue(&L)入隊：EnQueue(&Q,x)出隊：DeQueue(&Q,&x)讀隊頭元素：GetHead(s,&x)判空棧：QueueEmpty(S)

順序循環隊列基本操作的實現：

情況一：rear和front指向同一位置時

隊列定義：

1.用犧牲一個節點為代價判斷空和滿

typedef struct{int data[MaxSize];int front,rear; }SqQueue;

2.用size標記判斷空和滿

typedef struct{int data[MaxSize];int front,rear;int size; //size為0則空，size為MaxSize則滿 }SqQueue;

3.用tag標記判斷空和滿

typedef struct{int data[MaxSize];int front,rear;int tag; //入隊為1，出隊為0 }SqQueue;

隊列初始化：

1.用犧牲一個節點為代價判斷空和滿

void InitQueue(SqQueue &Q){Q.rear = Q.front = 0; }

2.用size標記判斷空和滿

void InitQueue(SqQueue &Q){Q.rear = Q.front = 0;size = 0; }

3.用tag標記判斷空和滿

void InitQueue(SqQueue &Q){Q.rear = Q.front = 0;tag = 0; }

入隊：

1.用犧牲一個節點為代價判斷空和滿
ps: 計算隊列元素個數：
　　(rear+MaxSize-front) % MaxSize
eg:(2+10-3) % 10 = 9(上圖)

bool EnQueue(SqQueue &Q,int x){if((Q.rear+1) % MaxSize == Q.front)return false;Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MaxSize;return true; }

2.用size標記判斷空和滿

bool EnQueue(SqQueue &Q,int x){if(Q.size == MaxSize)return false;Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MaxSize;size ++;return true; }

3.用tag標記判斷空和滿

bool EnQueue(SqQueue &Q,int x){if(Q.front == Q.rear && tag == 1)return false;Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MaxSize;tag = 1;return true; }

出隊：

1.用犧牲一個節點為代價判斷空和滿

bool DeQueue(SqQueue &Q,int &x){if(Q.rear == Q.front)return false;x = Q.data[Q.front];Q.front = (Q.front + 1) & MaxSize;return true; }

2.用size標記判斷空和滿

bool DeQueue(SqQueue &Q,int &x){if(Q.size == 0)return false;x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;size --;return true; }

3.用tag標記判斷空和滿

//每次刪除操作成功時都令tag=0，只有刪除操作才可能導致隊空 //每次插入操作成功時都令tag=1，只有插入操作才可能導致隊滿 bool EnQueue(SqQueue &Q,int x){if(Q.front == Q.rear && tag == 0)return false;x = Q.data[Q.rear];Q.front= (Q.front+ 1) % MaxSize;tag = 0;return true; }

隊列判空：

1.用犧牲一個節點為代價判斷空和滿

bool QueueEmpty(SqQueue Q){if(Q.rear == Q.front)return true;elsereturn false; }

2.用size標記判斷空和滿

bool QueueEmpty(SqQueue Q){if(Q.size == MaxSize)return true;elsereturn false; }

3.用tag標記判斷空和滿

bool QueueEmpty(SqQueue Q){if(Q.front == Q.rear && tag == 1)return true;elsereturn false; }

返回隊頭元素：

1.用犧牲一個節點為代價判斷空和滿

bool GetHead(SqQueue &Q,int &x){if(Q.rear == Q.front)return false;x = Q.data[Q.front];return true; }

2.用size標記判斷空和滿

bool GetHead(SqQueue &Q,int &x){if(Q.size == 0)return false;x = Q.data[Q.front];return true; }

3.用tag標記判斷空和滿

bool GetHead(SqQueue &Q,int &x){if(Q.front == Q.rear && tag == 0)return false;x = Q.data[Q.front];return true; }

情況二：rear在front后面

隊列定義：

1.用犧牲一個節點為代價判斷空和滿

typedef struct{int data[MaxSize];int front,rear; }SqQueue;

2.用size標記判斷空和滿

typedef struct{int data[MaxSize];int front,rear;int size; }SqQueue;

3.用tag標記判斷空和滿

typedef struct{int data[MaxSize];int front,rear;int tag; }SqQueue;

隊列初始化：

1.用犧牲一個節點為代價判斷空和滿

void InitQueue(SqQueue &Q){Q.front = 0;Q.rear = (Q.front - 1) % MaxSize; }

2.用size標記判斷空和滿

void InitQueue(SqQueue &Q){Q.front = 0;Q.rear = (Q.front - 1) % MaxSize;int size; }

3.用tag標記判斷空和滿

void InitQueue(SqQueue &Q){Q.front = 0;Q.rear = (Q.front - 1) % MaxSize;int tag; }

入隊：

1.用犧牲一個節點為代價判斷空和滿

bool EnQueue(SqQueue &Q,int x){if((Q.rear+2) % MaxSize == Q.front)return false;Q.rear = (Q.rear + 1) % MaxSize;Q.data[Q.rear] = x;return true; }

2.用size標記判斷空和滿

bool EnQueue(SqQueue &Q,int x){if(Q.size == MaxSize)return false;Q.rear = (Q.rear + 1) % MaxSize;Q.data[Q.rear] = x;size ++;return true; }

3.用tag標記判斷空和滿

bool EnQueue(SqQueue &Q,int x){if((Q.rear+1) % MaxSize == Q.front && tag == 1)return false;Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MaxSize;tag = 1;return true; }

出隊：

1.用犧牲一個節點為代價判斷空和滿

bool DeQueue(SqQueue &Q,int &x){if((Q.rear+1) % MaxSize == Q.front)return false;Q.front = (Q.front + 1) & MaxSize;x = Q.data[Q.front];return true; }

2.用size標記判斷空和滿

bool DeQueue(SqQueue &Q,int &x){if(Q.size == 0)return false;Q.front = (Q.front + 1) % MaxSize;x = Q.data[Q.front];size --;return true; }

3.用tag標記判斷空和滿

//每次刪除操作成功時都令tag=0，只有刪除操作才可能導致隊空 //每次插入操作成功時都令tag=1，只有插入操作才可能導致隊滿 bool EnQueue(SqQueue &Q,int x){if((Q.rear+1) % MaxSize == Q.front && tag == 0)return false;Q.front= (Q.front+ 1) % MaxSize;x = Q.data[Q.rear];tag = 0;return true; }

隊列判空：

1.用犧牲一個節點為代價判斷空和滿

bool QueueEmpty(SqQueue Q){if((Q.rear+1) % MaxSize == Q.front)return true;elsereturn false; }

2.用size標記判斷空和滿

bool QueueEmpty(SqQueue Q){if(Q.size == MaxSize)return true;elsereturn false; }

3.用tag標記判斷空和滿

bool QueueEmpty(SqQueue Q){if((Q.rear+1) % MaxSize == Q.front && tag == 0 )return true;elsereturn false; }

返回隊頭元素：

1.用犧牲一個節點為代價判斷空和滿

bool GetHead(SqQueue &Q,int &x){if((Q.rear+1) % MaxSize == Q.front)return false;x = Q.data[Q.front];return true; }

2.用size標記判斷空和滿

bool GetHead(SqQueue &Q,int &x){if(Q.size == 0)return false;x = Q.data[Q.front];return true; }

3.用tag標記判斷空和滿

bool GetHead(SqQueue &Q,int &x){if((Q.rear+1) % MaxSize == Q.front && tag == 0)return false;x = Q.data[Q.front];return true; } 新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的数据结构之顺序循环队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。