隊列的三種實作方式

普通順序存儲結構

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
const int maxSize = 100 ;

using namespace std ;

typedef struct
{
    int data[maxSize] ;
    int front ;  //定義頭尾指針
    int rear ;
}SqQueue ;

void initQueue(SqQueue *&q)  //初始化隊列
{
    q = (SqQueue *)malloc(sizeof(SqQueue)) ;
    q->front = q->rear = -1 ;
}

void destroyQueue(SqQueue *&q)    //銷毀隊列
{
    free(q) ;
}

bool QueueEmpty(SqQueue *q)       //判斷隊列是否為空
{
    return (q->rear == q->front) ;
}

bool enQueue(SqQueue *&q,int e)  //将元素e入隊列
{
    if(q->rear == maxSize-1)   //隊列已滿 入隊失敗
        return false ;
    q->rear++ ;
    q->data[q->rear] = e ;
    return true ;

}


bool deQueue(SqQueue *&q,int &e)   //出隊列，并用傳回出隊元素
{
    if(q->rear == q->front)
        return false ;      //隊列為空 無法入隊
        q->front++ ;
    e = q->data[q->front] ;
    return true ;
}

int main()
{
    SqQueue *queue ;
    int e ;
    initQueue(queue) ;
    enQueue(queue,12) ;
    deQueue(queue,e) ;
    printf("出隊的元素是%d\n",e) ;
    if(QueueEmpty(queue))
    {
        printf("隊列為空\n") ;
    }
    else
    {
        printf("隊列不為空\n");
    }
    //enQueue(queue,1) ;
}

           

環形隊列

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
const int maxSize = 100 ;

using namespace std ;

typedef struct
{
    int data[maxSize] ;
    int front ;
    int rear ;
}SqQueue;

void initQueue(SqQueue *&q)    //初始化隊列
{
    q = (SqQueue*)malloc(sizeof(SqQueue)) ;
    q->front = q->rear = 0 ;
}

void destroyQueue(SqQueue *&q)   //銷毀隊列
{
    free(q) ;
}

bool enQueue(SqQueue *&q,int e)  //将元素e入隊q
{
    if(q->rear == maxSize-1)  //隊列已滿，入隊失敗
        return false ;
    q->rear = (q->rear+1)%maxSize ;   //通過對maxSize循環取餘解決假溢出問題
    q->data[q->rear] = e ;
    return true ;
}

bool deQueue(SqQueue *&q,int &e)  //隊頭元素出隊，用e記錄出隊元素
{
    if(q->front == q->rear)   //隊列中沒有元素，無法出隊
        return false ;
    q->front = (q->front+1)%maxSize ;
    e = q->data[q->front] ;
    return true ;
}

int main()
{
    SqQueue *queue ;
    initQueue(queue) ;
    int e ;
    enQueue(queue,3) ;
    deQueue(queue,e) ;
    printf("出隊元素是%d\n",e) ;
    return  0  ;
}
           

隊列的鍊式表示

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std ;

typedef struct QNode
{
    int data ;
    struct QNode *next ;
}QNode;

typedef struct
{
    QNode *front ;
    QNode *rear ;
}LiQueue ;

void initQueue(LiQueue *&q)   //初始化隊列
{
    q = (LiQueue *)malloc(sizeof(LiQueue)) ;
    q->front = q->rear = NULL ;
    printf("隊列建立成功\n") ;
}

void destroyQueue(LiQueue *&q)   //銷毀隊列
{
    QNode *p = q->front ,*r;
    if(p != NULL)
    {
        r = p->next ;
        while(r != NULL)
        {
            free(p) ;
            p = r ;
            r = p->next ;
        }

    }
    free(p) ;
    free(q) ;
    printf("隊列已經成功銷毀\n") ;

}


bool QueueEmpty(LiQueue *q)
{
    return (q->front == q->rear) ;
}

void enQueue(LiQueue *&q,int e)
{
    QNode *p ;
    p = (QNode *)malloc(sizeof(QNode)) ;
    p->data = e ;
    if(q->front == q->rear)  //如果目前隊列為空，則新節點既是頭指針又是尾指針
    {
        q->front = q->rear = p ;
    }
    else
    {
        q->rear->next = p ;
        q->rear = p ;
    }
    printf("%d已經成功入隊\n",e) ;
}

bool delQueue(LiQueue *&q,int &e)  //出隊，并且用儲存出隊元素
{
    if(q->rear == NULL)
        return false ;
    QNode *t = q->front ;
    e = t->data ;
    if(q->front == q->rear)
        q->front = q->rear = NULL ;
    else q->front->next = t->next ;
    free(t) ;
    printf("%d已成功出隊\n",e) ;
    return true ;
}

int main()
{
    LiQueue *queue ;
    initQueue(queue) ;
    printf("%d\n",QueueEmpty(queue)) ;
    enQueue(queue,3) ;
    int e ;
    delQueue(queue,e) ;
}