?文章來源地址http://www.zghlxwxcb.cn/news/detail-780220.html

目錄

一.循環(huán)隊列簡單介紹

二.用靜態(tài)數(shù)組實現(xiàn)循環(huán)隊列

1.數(shù)組循環(huán)隊列結(jié)構(gòu)設(shè)計

2.數(shù)組循環(huán)隊列的堆區(qū)內(nèi)存申請接口?

3.數(shù)據(jù)出隊和入隊的接口實現(xiàn)

4.其他操作接口

5.數(shù)組循環(huán)隊列的實現(xiàn)代碼總覽?

三.靜態(tài)單向循環(huán)鏈表實現(xiàn)循環(huán)隊列?

1.鏈表循環(huán)隊列的結(jié)構(gòu)設(shè)計

2.創(chuàng)建靜態(tài)單向循環(huán)鏈表的接口

3.數(shù)據(jù)的出隊和入隊接口

4.其他隊列操作接口

5.靜態(tài)鏈表循環(huán)隊列總體代碼

問題來源:622. 設(shè)計循環(huán)隊列 - 力扣（Leetcode）

一.循環(huán)隊列簡單介紹

• 循環(huán)隊列一般是一種靜態(tài)的線性數(shù)據(jù)結(jié)構(gòu),其中的數(shù)據(jù)符合先進(jìn)先出的原則.
• 循環(huán)隊列的容器首地址和容器尾地址通過特定操作(比如指針鏈接,數(shù)組下標(biāo)取余等方式)相連通,從而實現(xiàn)了容器空間的重復(fù)利用(在一個非循環(huán)靜態(tài)隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間)

?

二.用靜態(tài)數(shù)組實現(xiàn)循環(huán)隊列

維護(hù)隊列的結(jié)構(gòu)體:

typedef struct 
{
    int * arry;  //指向堆區(qū)數(shù)組的指針
    int head;    //隊頭指針
    int tail;    //隊尾指針(指向隊尾數(shù)據(jù)的下一個位置)(不指向有效數(shù)據(jù))
    int capacity;//靜態(tài)隊列的容量
} MyCircularQueue;

1.數(shù)組循環(huán)隊列結(jié)構(gòu)設(shè)計

我們假定靜態(tài)數(shù)組的容量為k(可存儲k個數(shù)據(jù))：

• 根據(jù)隊列的基本數(shù)據(jù)結(jié)構(gòu):有兩個指針用于維護(hù)數(shù)組中的有效數(shù)據(jù)空間,分別為head指針和tail指針,head指針用于指向隊頭數(shù)據(jù),tail用于指向隊尾數(shù)據(jù)的下一個位置(即tail指針不指向有效數(shù)據(jù))
• ?如圖所示,head指針和tail指針之間就是有效數(shù)據(jù)的內(nèi)存空間

• 通過head指針和tail指針的關(guān)系來實現(xiàn)隊列的判滿(判斷隊列空間是否已被占滿)與判空(判斷隊列是否為空隊列)；為了達(dá)到這個目的,我們需要將靜態(tài)數(shù)組的容量大小設(shè)置為k+1(即多設(shè)置一個元素空間)?

1. 隊列的判空條件: tail == head;
2. 隊列的判滿條件: (tail+1)%(k+1) == head;?另外一種情形:

• 由此我們可以先設(shè)計出隊列的判滿和判空接口：

  bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判斷隊列是否為空
  {
      assert(obj);
      return (obj->tail == obj->head);
  }
  
  bool myCircularQueueIsFull(MyCircularQueue* obj)  //判斷隊列是否為滿
  {
      assert(obj);
      return ((obj->tail+1)%(obj->capacity +1) == obj->head);
  }

2.數(shù)組循環(huán)隊列的堆區(qū)內(nèi)存申請接口?

• 在堆區(qū)上創(chuàng)建MyCircularQueue結(jié)構(gòu)體,同時為隊列申請一個空間大小為(k+1)*sizeof(DataType)字節(jié)的數(shù)組：

  MyCircularQueue* myCircularQueueCreate(int k)  //k個容量大小的循環(huán)隊列的初始化接口
  {
      MyCircularQueue * tem = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
      //開辟維護(hù)循環(huán)隊列的結(jié)構(gòu)體
      if(NULL == tem)
      {
          perror("malloc failed");
          exit(-1);
      }
      tem->arry = NULL;
      tem->capacity = k;   
      //隊列的數(shù)據(jù)容量為k
      tem->arry = (int*)malloc((k+1)*sizeof(int));
      //開辟堆區(qū)數(shù)組
      if(NULL == tem->arry)
      {
          perror("malloc failed");
          exit(-1);
      }
      //將head,tail下標(biāo)初始化為0
      tem->head = 0; 
      tem->tail = 0;
      return tem;
  }

3.數(shù)據(jù)出隊和入隊的接口實現(xiàn)

數(shù)據(jù)出隊和入隊的圖解:

?

• ?根據(jù)圖解我們可以設(shè)計出數(shù)據(jù)入隊和出隊的接口:

  bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //數(shù)據(jù)入隊接口
  {
      assert(obj);
      if(myCircularQueueIsFull(obj))
      {
          return false;
      }
      //確保隊列沒滿
      obj->arry[obj->tail]=value;
      obj->tail = (obj->tail + 1)%(obj->capacity +1);
      return true;
  }

  bool myCircularQueueDeQueue(MyCircularQueue* obj)    //數(shù)據(jù)出隊接口
  {
      assert(obj);
      if(myCircularQueueIsEmpty(obj))
      {
          return false;
      }
      //確保隊列不為空
      obj->head = (obj->head +1)%(obj->capacity +1);
      return true;
  }

4.其他操作接口

返回隊頭數(shù)據(jù)的接口:

int myCircularQueueFront(MyCircularQueue* obj)   //返回隊頭數(shù)據(jù)的接口
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->arry[obj->head];
}

?返回隊尾數(shù)據(jù)的接口:

int myCircularQueueRear(MyCircularQueue* obj)   //返回隊尾數(shù)據(jù)的接口     
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    int labelret = ((obj->tail-1)>=0)? obj->tail-1 : obj->capacity;
    //注意tail如果指向數(shù)組首地址,則尾數(shù)據(jù)位于數(shù)組最后一個位置
    return obj->arry[labelret];
}

隊列的銷毀接口:

void myCircularQueueFree(MyCircularQueue* obj)     //銷毀隊列的接口
{
    assert(obj);
    free(obj->arry);
    obj->arry = NULL;
    free(obj);
    obj = NULL;
}

5.數(shù)組循環(huán)隊列的實現(xiàn)代碼總覽?

?數(shù)組循環(huán)隊列總體代碼:

typedef struct 
{
    int * arry;  //指向堆區(qū)數(shù)組的指針
    int head;    //隊頭指針
    int tail;    //隊尾指針(指向隊尾數(shù)據(jù)的下一個位置)(不指向有效數(shù)據(jù))
    int capacity;//靜態(tài)隊列容量
} MyCircularQueue;


bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
//順序編譯注意:先被使用而后被定義的函數(shù)要記得進(jìn)行聲明

MyCircularQueue* myCircularQueueCreate(int k)          //循環(huán)隊列初始化接口
{
    MyCircularQueue * tem = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    //開辟維護(hù)循環(huán)隊列的結(jié)構(gòu)體
    if(NULL == tem)
    {
        perror("malloc failed");
        exit(-1);
    }
    tem->arry = NULL;
    tem->capacity = k;   
    //隊列的數(shù)據(jù)容量為k
    tem->arry = (int*)malloc((k+1)*sizeof(int));
    //開辟堆區(qū)數(shù)組
    if(NULL == tem->arry)
    {
        perror("malloc failed");
        exit(-1);
    }
    
    tem->head = 0;
    tem->tail = 0;
    return tem;
}



bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)   //數(shù)據(jù)入隊接口
{
    assert(obj);
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //確保隊列沒滿
    obj->arry[obj->tail]=value;
    obj->tail = (obj->tail + 1)%(obj->capacity +1);
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj)           //數(shù)據(jù)出隊接口
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //確保隊列不為空
    obj->head = (obj->head +1)%(obj->capacity +1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj)               //返回隊頭數(shù)據(jù)的接口
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->arry[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj)                 //返回隊尾數(shù)據(jù)的接口     
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    int labelret = ((obj->tail-1)>=0)? obj->tail-1 : obj->capacity;
    //注意tail如果指向數(shù)組首地址,則尾數(shù)據(jù)位于數(shù)組最后一個位置
    return obj->arry[labelret];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj)              //判斷隊列是否為空
{
    assert(obj);
    return (obj->tail == obj->head);
}

bool myCircularQueueIsFull(MyCircularQueue* obj)               //判斷隊列是否為滿
{
    assert(obj);
    return ((obj->tail+1)%(obj->capacity +1) == obj->head);
}

void myCircularQueueFree(MyCircularQueue* obj)                 //銷毀隊列的接口
{
    assert(obj);
    free(obj->arry);
    obj->arry = NULL;
    free(obj);
    obj = NULL;
}

力扣題解測試:

三.靜態(tài)單向循環(huán)鏈表實現(xiàn)循環(huán)隊列?

鏈表節(jié)點結(jié)構(gòu)體定義:

typedef struct listnode
{
    int data;
    struct listnode * next;
}ListNode;

維護(hù)鏈表循環(huán)隊列的結(jié)構(gòu)體:

typedef struct 
{
    int capacity;     //記錄隊列容量大小
    ListNode * head;  //指向隊頭節(jié)點
    ListNode * tail;  //指向隊尾節(jié)點
} MyCircularQueue;

1.鏈表循環(huán)隊列的結(jié)構(gòu)設(shè)計

靜態(tài)單向循環(huán)鏈表的容量大小為k:

• 與數(shù)組循環(huán)隊列類似,我們同樣需要開辟一個節(jié)點個數(shù)為k+1的靜態(tài)循環(huán)鏈表
• 鏈表循環(huán)隊列的總體結(jié)構(gòu)圖示:另外一種隊列判滿的情形:

1. ?鏈表循環(huán)隊列的判滿條件(判斷隊列空間是否被占滿的關(guān)系式):tail->next == head;
2. ?鏈表循環(huán)隊列的判空條件(判斷隊列是否為空隊列的關(guān)系式):?tail == head;

鏈表循環(huán)隊列的判滿和判空的接口:

bool myCircularQueueIsEmpty(MyCircularQueue* obj)    //判斷隊列是否為空
{
    assert(obj);
    return(obj->head == obj->tail);
}

bool myCircularQueueIsFull(MyCircularQueue* obj)     //判斷隊列是否為滿
{
    assert(obj);
    return (obj->tail->next == obj->head);
}

2.創(chuàng)建靜態(tài)單向循環(huán)鏈表的接口

實現(xiàn)一個接口,創(chuàng)建一個維護(hù)鏈表循環(huán)隊列的結(jié)構(gòu)體同時創(chuàng)建容量大小為k+1的靜態(tài)單向循環(huán)鏈表:

MyCircularQueue* myCircularQueueCreate(int k)  //循環(huán)隊列初始化接口
{
    int NodeNum =k+1;                          //創(chuàng)建k+1個鏈表節(jié)點
    MyCircularQueue* object = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    assert(object);                            //申請維護(hù)循環(huán)隊列的結(jié)構(gòu)體
    object->capacity = k;

    ListNode * preNode = NULL;                 //用于記錄前一個鏈接節(jié)點的地址
    while(NodeNum)
    {
        if(NodeNum == k+1)
        {   ListNode * tem = (ListNode *)malloc(sizeof(ListNode));
            assert(tem);
            preNode = tem;
            object->tail = object->head=tem;    //讓tail和head指向同一個初始節(jié)點
        }
        else
        {
            ListNode * tem = (ListNode *)malloc(sizeof(ListNode));
            assert(tem);
            preNode->next = tem;                //鏈接鏈表節(jié)點
            preNode = tem;
        }
        NodeNum--;
    }
    preNode->next = object->head;               //將表尾與表頭相接
    return object;
}

3.數(shù)據(jù)的出隊和入隊接口

數(shù)據(jù)出入隊圖解:

根據(jù)圖解實現(xiàn)數(shù)據(jù)出入隊接口:

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)//數(shù)據(jù)入隊接口(從隊尾入隊)
{
    assert(obj);
    if(!obj || myCircularQueueIsFull(obj))  //確定隊列沒滿
    {
        return false;
    }           
    obj->tail->data = value;                //數(shù)據(jù)入隊
    obj->tail = obj->tail->next;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj)  //數(shù)據(jù)出隊接口
{
    assert(obj);
    if(!obj || myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //數(shù)據(jù)出隊
    obj->head = obj->head->next;
    return true;
}

4.其他隊列操作接口

返回隊頭數(shù)據(jù)的接口:

int myCircularQueueFront(MyCircularQueue* obj)  //返回隊頭數(shù)據(jù)的接口
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->head->data; //返回隊頭元素
}

返回隊尾數(shù)據(jù)的接口:

int myCircularQueueRear(MyCircularQueue* obj)   //返回隊尾數(shù)據(jù)的接口     
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    ListNode * tem = obj->head;
    while(tem->next != obj->tail)               //尋找隊尾元素
    {
        tem=tem->next;
    }
    return tem->data;  //返回隊尾元素
}

隊列銷毀接口:

隊列銷毀過程圖解:

void myCircularQueueFree(MyCircularQueue* obj) //銷毀隊列的接口
{
    assert(obj);
    //利用頭指針來完成鏈表節(jié)點的釋放
    ListNode * endpoint = obj->head;           //記錄一個節(jié)點釋放的終點
    obj->head = obj->head->next;
    while(obj->head!=endpoint)
    {
        ListNode * tem = obj->head->next;
        free(obj->head);
        obj->head = tem;
    }
    free(endpoint);                            //釋放掉終點節(jié)點
    free(obj);                                 //釋放掉維護(hù)環(huán)形隊列的結(jié)構(gòu)體
}

5.靜態(tài)鏈表循環(huán)隊列總體代碼

總體代碼:

typedef struct listnode
{
    int data;
    struct listnode * next;
}ListNode;

typedef struct 
{
    int capacity;
    ListNode * head;
    ListNode * tail;
    int taildata;   //單向鏈表找尾復(fù)雜度為O(N),因此我們用一個變量來記錄隊尾數(shù)據(jù)
} MyCircularQueue;


bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
//順序編譯注意:先被使用而后被定義的函數(shù)要記得進(jìn)行聲明



MyCircularQueue* myCircularQueueCreate(int k)  //循環(huán)隊列初始化接口
{
    int NodeNum =k+1;                          //創(chuàng)建k+1個鏈表節(jié)點
    MyCircularQueue* object = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    assert(object);                            //申請維護(hù)循環(huán)隊列的結(jié)構(gòu)體
    object->capacity = k;

    ListNode * preNode = NULL;                 //用于記錄前一個鏈接節(jié)點的地址
    while(NodeNum)
    {
        if(NodeNum == k+1)
        {   ListNode * tem = (ListNode *)malloc(sizeof(ListNode));
            assert(tem);
            preNode = tem;
            object->tail = object->head=tem;    //讓tail和head指向同一個初始節(jié)點
        }
        else
        {
            ListNode * tem = (ListNode *)malloc(sizeof(ListNode));
            assert(tem);
            preNode->next = tem;                //鏈接鏈表節(jié)點
            preNode = tem;
        }
        NodeNum--;
    }
    preNode->next = object->head;               //將表尾與表頭相接
    return object;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)   //數(shù)據(jù)入隊接口(從隊尾入隊)
{
    assert(obj);
    if(!obj || myCircularQueueIsFull(obj))  //確定隊列沒滿
    {
        return false;
    }           
    obj->tail->data = value;                //數(shù)據(jù)入隊
    obj->tail = obj->tail->next;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj)               //數(shù)據(jù)出隊接口
{
    assert(obj);
    if(!obj || myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->head = obj->head->next;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj)  //返回隊頭數(shù)據(jù)的接口
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->head->data;
}

int myCircularQueueRear(MyCircularQueue* obj)   //返回隊尾數(shù)據(jù)的接口     
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    ListNode * tem = obj->head;
    while(tem->next != obj->tail)               //尋找隊尾元素
    {
        tem=tem->next;
    }
    return tem->data;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj)                  //判斷隊列是否為空
{
    assert(obj);
    return(obj->head == obj->tail);
}

bool myCircularQueueIsFull(MyCircularQueue* obj)                    //判斷隊列是否為滿
{
    assert(obj);
    return (obj->tail->next == obj->head);
}



void myCircularQueueFree(MyCircularQueue* obj) //銷毀隊列的接口
{
    assert(obj);
    //利用頭指針來完成鏈表節(jié)點的釋放
    ListNode * endpoint = obj->head;           //記錄一個節(jié)點釋放的終點
    obj->head = obj->head->next;
    while(obj->head!=endpoint)
    {
        ListNode * tem = obj->head->next;
        free(obj->head);
        obj->head = tem;
    }
    free(endpoint);                            //釋放掉終點節(jié)點
    free(obj);                                 //釋放掉維護(hù)環(huán)形隊列的結(jié)構(gòu)體
}

leetcode題解測試:

?

?

?

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu):循環(huán)隊列的實現(xiàn)(leetcode622.設(shè)計循環(huán)隊列)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！