隨感而發

隊列學習--數組實現

今天學習了隊列，隊列的思路和棧差不多，他只是先進先出（FIFO）的方式。他的主要操作和棧有：IsEmpty判斷空，EnQueue入隊，(棧是push，不過沒有什么大的區別)。DeQueue出隊。其核心數據也是很相似，也有一個數據區域nData,不過他是隊頭nHand和隊尾nTail。對頭定位著將要出隊的元素，隊尾對應著入隊的元素。
實現細節：也是為了能使操作簡單一些，我們開始都從0開始，nTail指向的是入隊時候數據要加的位置，也就是說他是先把該位置設置為入隊的值，然后自己再加1.nData[nTail] = shuju; nTail++;這種方式。nHead指向的就是出隊的位置，這樣的好處就是能很快的判斷隊是否為空，只要nHand == nTail隊就是空的了。(因為出隊位置處沒有數據)，這樣出隊也很方便，只需要得到nHead指向位置的數據，然后nHead加1就可以。
不過有的時候，會一邊入隊，一邊出隊，這樣nTail和nHead會一直往后走，而nhead前面的區域已經自由了，沒有用處，這樣就浪費了空間。為了能有效地利用空間，我們可以循環用數據區域，就是當nTail 到數據區域最后的時候，我們把它回到0。這樣就能很好的循環利用。不過這樣就不能簡單的用nTail >= nLen的方式判斷隊是否滿了，做了一個處理，如果nTai的下一個位置就是nHead的話，我們認為隊滿了，nTail指向的是隊末要插入的位置，如果他的下一個位置為nHead的話，則說明nHead..nTail中已經存放了數據。最多只能存放nTail位置一個數據。這里我們為什么不讓他多存一個數據，使nTail == nHead得時候，才認為隊滿呢？這樣不是更高的利用空間嗎？話雖這樣說，不過nTail == nHead是我們判斷隊是否為空的標識。如果我們把nTail == nHead也作為判斷隊滿的標識的話，就會引起歧義，所以我選擇浪費一個空間，來更方便的判斷隊空和隊滿。還有注意在入隊的時候要判斷隊是否為滿，出隊的時候，要判斷是否為空。
奉上源代碼：用數組實現的：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//定義一個隊列的結構體
struct MyQueue 
{
    int nTail;    //隊列尾
    int nHead;  //隊列頭
    int nData[10];    //隊列數據
};

//規則說明：
//nHead 直接指向了對頭的數據位置，
//nTail 直接指向了隊尾要插入的位置，
//如果nTail==nHead ，隊列為空
//nTail 比 nHead位置小一，(就是在他前面一個)，代表隊滿
//所以數組中能存放的數據要比數組的空間小1，是為了判斷隊列滿的情況。

MyQueue g_queue;        //定義全局的隊列

//判斷隊列是否為空
bool IsEmpty(void)
{
    return (g_queue.nHead == g_queue.nTail);        //如果尾等于頭，則為空
}

//設置隊列為空
int SetEmpty(void)
{
    g_queue.nTail = 0;        //都設置為零
    g_queue.nHead = 0;
    return 1;
}

//判斷隊列是否為滿
bool IsFull(void)
{
    //如果ntial 比 nHead小1，則棧滿。
    return (g_queue.nTail + 1) % 10 == g_queue.nHead;    
}

//入隊
int EnQueue(int nData)
{
    assert(!IsFull());        //assert表示斷言，斷言!IsFull成立，如果不成立，則報告程序錯誤！
    g_queue.nData[g_queue.nTail] = nData;
    g_queue.nTail = (g_queue.nTail + 1) % 10;
    return (g_queue.nTail - g_queue.nHead) % 10;
}

//出隊
int DeQueue(void)
{
    assert(!IsEmpty());
    int nData = g_queue.nData[g_queue.nHead];
    g_queue.nHead = (g_queue.nHead + 1) % 10;
    return nData;
}

int main()
{
    //測試
    SetEmpty();            //設置隊列為空
    if (IsEmpty())        //判斷為空，輸出信息
    {
        printf("The queue is empty!\n");
    }

    //
    for (int i = 0; i < 9; ++i)
    {
        EnQueue(i);
    }
    if (IsFull())                //判斷隊列滿
    {
        printf("The Queue is full\n");        //棧滿的英語是不是full啊
    }

    for (int i = 0; i < 9; ++i)                //出隊
    {
        printf("%d ", DeQueue());            
    }
    printf("\n");

    if (IsEmpty())                        
    {
        printf("The queue is empty!\n");
    }

    for (int i = 0; i < 8; ++i)            //測試出隊和入隊
    {
        EnQueue(i);
        EnQueue(i*2);
        printf("%d ", DeQueue());
    }
    printf("\n");

    while(!IsEmpty())
    {
        printf("%d ", DeQueue());
    }
    printf("\n");

    system("pause");
    return 0;
}

posted on 2009-04-29 20:56 shongbee2 閱讀(3536) 評論(0)  編輯 收藏 引用 所屬分類: 數據結構和算法