數據結構之隊列

隊列

    1.定義：隊列是一種先進先出（FIFO）的線性表。它只允許在表的一端進行插入，而在另一端刪除元素。

在隊列中，允許插入的一端叫做隊尾，允許刪除的一端則稱為隊頭。

    假設對列為q=（a1,a2,a3,...,an），那麼a1就是隊頭元素，an則是隊尾元素。隊列中的元素是按照a1,a2

,...,an的順序進入的，退出隊列也只能按照這個次退出，也就是說，只有在a1,a2,...,an-1都離開隊列之後，

an才能退出隊列。那麼其數據結構為：

#define ElemType int
#define QUEUE_INIT_SIZE 8

typedef struct Queue
{
    ElemType *base;
    int       capacity;
    int       front;
    int       rear;
}Queue;

        2.因此在隊列中有以下操作：

void InitQueue(Queue *q);
void EnQueue(Queue *q, ElemType x);
void DeQueue(Queue *q);
ElemType GetTop(Queue *q);
void ShowQueue(Queue *q);
bool IsFull(Queue *q);
bool IsEmpty(Queue *q);

     以上的方法在隊列中有以下操作：（1）初始化隊列.（2）向隊列中插入元素.（3）刪除隊列中的元素.（4）

得到隊頭元素.（5）展示隊列中的內容.（6）判斷對列是否是滿狀態.（7）判斷隊列是否是空狀態.

   3.將上面聲明的方法進行實現為：

bool IsFull(Queue *q)
{
    //return (q->rear-q->front) >= q->capacity;
    //return q->rear >= q->capacity;
    return (q->rear+1)%q->capacity == q->front;
}
bool IsEmpty(Queue *q)
{
    return q->front == q->rear;
}
void InitQueue(Queue *q)
{
    q->base = (ElemType*)malloc(sizeof(ElemType)*QUEUE_INIT_SIZE);
    assert(q->base != NULL);
    q->capacity = QUEUE_INIT_SIZE;
    q->front = q->rear = 0;
}
void EnQueue(Queue *q, ElemType x)
{
    if(!IsFull(q))
    {
        q->base[q->rear] = x;
        q->rear = (q->rear+1) % q->capacity;
    }
}

void ShowQueue(Queue *q)
{
    if(!IsEmpty(q))
    {
        for(int i=q->front; i!=q->rear; i=(i+1)%q->capacity)
        {
            cout<<q->base[i]<<" ==> ";
        }
        cout<<endl;
    }
}

void DeQueue(Queue *q)
{
    if(!IsEmpty(q))
    {
        q->front++;
        q->front = q->front % q->capacity;
    }
}

ElemType GetTop(Queue *q)
{
    assert(!IsEmpty(q));
    return q->base[q->front];
}