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

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

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

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

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

MyQueue g_queue;        //定義全局的隊(duì)列

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

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

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

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

//出隊(duì)
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()
{
    //測(cè)試
    SetEmpty();            //設(shè)置隊(duì)列為空
    if (IsEmpty())        //判斷為空，輸出信息
    {
        printf("The queue is empty!\n");
    }

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

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

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

    for (int i = 0; i < 8; ++i)            //測(cè)試出隊(duì)和入隊(duì)
    {
        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 閱讀(3551) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): 數(shù)據(jù)結(jié)構(gòu)和算法