随感而发

队列学习--数组实现

今天学习了队列，队列的思路和栈差不多，他只是先进先出（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 阅读(3494) 评论(0)  编辑 收藏 引用 所属分类: 数据结构和算法