1012 Quiz#1: Queue with a Circular Buffer

概念上 Queue 是 FIFO 的資料結構

• Head 指的位置就是 Queue 的最前端, 也就是可以讀出資料的地方, 除非 buffer 已經空了
  
  
• Tail 指的位置就是 Queue 的尾巴的後一個位置, 也就是可以把資料寫進去的地方, 除非 buffer 已經滿了
  
  
• 移除一筆資料後把 Head 往後移一格
  新增一筆資料後把 Tail 往後移一格
  
  
• 此例中 buffer 有 8 個空間, 但是最多只能存放 7 個元素, 不能把 buffer 完全填滿, 否則分不出 buffer 是滿的還是空的
  
  
• 例如當 Head 為 0, Tail 為 7 時就是滿的, Head 和 Tail 指到相同的地方代表 buffer 裡面是空的, 例如 Head 為 5, Tail 為 5

下圖是一個運用 Circular Buffer 製作的 Queue

只要 buffer 的空間比 Queue 裡面平均資料的長度長, 就可以循環地使用 buffer

#include <iostream>
#include <cstdlib>
#include <cassert>
using namespace std;

const int BSIZE = 8;

typedef struct 
{
    int head;
    int tail;
    int *buffer; 
} QUEUE; 

void Queue_Init(QUEUE *);
void Queue_Destroy(QUEUE *);
bool Queue_Is_Empty(QUEUE *);
bool Queue_Is_Full(QUEUE *);
bool Queue_Get(QUEUE *, int *data);
bool Queue_Put(QUEUE *, int data);

int main(int argc, char* argv[])
{
    int i=0;
    int data; 
    QUEUE queue; 

    Queue_Init(&queue); 

    cout << "Fill the queue with data ...   ";

    while (Queue_Put(&queue,i))
       cout << i++ << " ";

    assert(Queue_Is_Full(&queue));

    cout << endl << "Extract data from the queue... ";

    while (Queue_Get(&queue, &data))
       cout << data << " "; 

    cout << endl;

    assert(Queue_Is_Empty(&queue));

    Queue_Destroy(&queue);

    system("pause");
    return 0;
} 

void Queue_Init(QUEUE *queue)
{
    queue->head = 0;
    queue->tail = 0;
    queue->buffer = (int *) malloc(sizeof(int)*BSIZE);
} 

void Queue_Destroy(QUEUE *queue)
{
    if (queue->buffer != 0)
    {
        free(queue->buffer);
        queue->buffer = 0;
    }
} 

bool Queue_Is_Empty(QUEUE *queue)
{
    if(queue->head == queue->tail)
        return true;
    return false; 
} 

bool Queue_Is_Full(QUEUE *queue)
{
    if((queue->tail+1)%BSIZE==queue->head)
        return true;
    return false; 
} 

bool Queue_Get(QUEUE *queue, int *data)
{
    // 如果 buffer 裡沒有東西, 請回傳 false

    // 請由 buffer 中 (queue 的最前端) 取出資料

    return true;
} 

bool Queue_Put(QUEUE *queue, int data)
{
    if(Queue_Is_Full(queue))
        return false; 

    queue->buffer[queue->tail] = data; 

    queue->tail=(queue->tail+1)%BSIZE; 

    return true;
} 

時間: 30分鐘 (09:55 上傳時間截止)

請製作一個新的方案, 讓 Visual Studio 為方案建立目錄, 設定專案名稱為 C_Version, 將上述程式拷貝進 main.cpp, 完成上面的Queue_Get 函式, 並且測試程式功能

請在方案中新增一個專案, 名稱是 CPP_Version, 製作一個 C++ 的 Queue 類別, 類別裡有三個資料成員和六個成員函式 (請注意需要重新定義類別界面方法的參數), 並且加入一個 main.cpp 內容由上述的 main.cpp 修改, 配合你定義的 Queue 類別界面, 測試後繳交