隊列學(xué)習(xí)--數(shù)組實現(xiàn)

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

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

//定義一個隊列的結(jié)構(gòu)體
struct MyQueue 
{
    int nTail;    //隊列尾
    int nHead;  //隊列頭
    int nData[10];    //隊列數(shù)據(jù)
};

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

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

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

//設(shè)置隊列為空
int SetEmpty(void)
{
    g_queue.nTail = 0;        //都設(shè)置為零
    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();            //設(shè)置隊列為空
    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 閱讀(3553) 評論(0)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結(jié)構(gòu)和算法