數據結構C語言實現之隊列

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

typedef int elemType;
/************************************************************************/
/*                    以下是關於隊列鏈接存儲操作的6種算法               */
/************************************************************************/
struct sNode{
    elemType data;            /* 值域 */
    struct sNode *next;        /* 鏈接指針 */
};
struct queueLK{
    struct sNode *front;    /* 隊首指針 */
    struct sNode *rear;        /* 隊尾指針 */
};

/* 1.初始化鏈隊 */
void initQueue(struct queueLK *hq)
{
    hq->front = hq->rear = NULL;        /* 把隊首和隊尾指針置空 */
    return;
}

/* 2.向鏈隊中插入一個元素x */
void enQueue(struct queueLK *hq, elemType x)
{
    /* 得到一個由newP指針所指向的新結點 */
    struct sNode *newP;
    newP = malloc(sizeof(struct sNode));
    if(newP == NULL){
        printf("內存空間分配失敗！ ");
        exit(1);
    }
    /* 把x的值賦給新結點的值域，把新結點的指針域置空 */
    newP->data = x;
    newP->next = NULL;
    /* 若鏈隊為空，則新結點即是隊首結點又是隊尾結點 */
    if(hq->rear == NULL){
        hq->front = hq->rear = newP;
    }else{    /* 若鏈隊非空，則依次修改隊尾結點的指針域和隊尾指針，使之指向新的隊尾結點 */
        hq->rear = hq->rear->next = newP;        /* 注意賦值順序哦 */
    }
    return;
}

/* 3.從隊列中刪除一個元素 */
elemType outQueue(struct queueLK *hq)
{
    struct sNode *p;
    elemType temp;
    /* 若鏈隊為空則停止運行 */
    if(hq->front == NULL){
        printf("隊列為空，無法刪除！ ");
        exit(1);
    }
    temp = hq->front->data;        /* 暫存隊尾元素以便返回 */
    p = hq->front;                /* 暫存隊尾指針以便回收隊尾結點 */
    hq->front = p->next;        /* 使隊首指針指向下一個結點 */
    /* 若刪除後鏈隊為空，則需同時使隊尾指針為空 */
    if(hq->front == NULL){
        hq->rear = NULL;
    }
    free(p);        /* 回收原隊首結點 */
    return temp;    /* 返回被刪除的隊首元素值 */
}

/* 4.讀取隊首元素 */
elemType peekQueue(struct queueLK *hq)
{
    /* 若鏈隊為空則停止運行 */
    if(hq->front == NULL){
        printf("隊列為空，無法刪除！ ");
        exit(1);
    }
    return hq->front->data;        /* 返回隊首元素 */
}

/* 5.檢查鏈隊是否為空，若為空則返回1, 否則返回0 */
int emptyQueue(struct queueLK *hq)
{
    /* 判斷隊首或隊尾任一個指針是否為空即可 */
    if(hq->front == NULL){
        return 1;
    }else{
        return 0;
    }
}

/* 6.清除鏈隊中的所有元素 */
void clearQueue(struct queueLK *hq)
{
    struct sNode *p = hq->front;        /* 隊首指針賦給p */
    /* 依次刪除隊列中的每一個結點，最後使隊首指針為空 */
    while(p != NULL){
        hq->front = hq->front->next;
        free(p);
        p = hq->front;
    }    /* 循環結束後隊首指針已經為空 */
    hq->rear = NULL;        /* 置隊尾指針為空 */
    return;
}

/************************************************************************/
int main(int argc, char* argv[])
{
    struct queueLK q;
    int a[8] = {3, 8, 5, 17, 9, 30, 15, 22};
    int i;
    initQueue(&q);
    for(i = 0; i < 8; i++){
        enQueue(&q, a[i]);
    }
    printf("%d ", outQueue(&q));    printf("%d  ", outQueue(&q));
    enQueue(&q, 68);
    printf("%d ", peekQueue(&q));    printf("%d  ", outQueue(&q));
    while(!emptyQueue(&q)){
        printf("%d ", outQueue(&q));
    }
    printf(" ");
    clearQueue(&q);
    system("pause");
}

#include <stdio.h>
#include <stdlib.h>
typedef int elemType;

/************************************************************************/
/*                      以下是關於隊列順序存儲操作的6種算法               */
/************************************************************************/

struct queue{
    elemType *queue;        /* 指向存儲隊列的數組空間 */
    int front, rear, len;    /* 隊首指針（下標），隊尾指針（下標），隊列長度變量 */
    int maxSize;            /* queue數組長度 */
};

void againMalloc(struct queue *q)
{
    /* 空間擴展為原來的2倍，原內容被自動拷貝到p所指向的存儲空間中 */
    elemType *p;
    p = realloc(q->queue, 2 * q->maxSize * sizeof(elemType));
    /* 動態存儲空間分配，若失敗則退出運行 */
    if(!p){
        printf("空間分配失敗！ ");
        exit(1);
    }
    q->queue = p;        /* 使queue指向新的隊列空間 */
    /* 把原隊列的尾部內容後移maxSize個位置 */
    if(q->rear != q->maxSize -1){
        int i;
        for(i = 0; i <= q->rear; i++){
            q->queue[i+q->maxSize] = q->queue[i];
        }
        q->rear += q->maxSize;        /* 隊尾指針後移maxSize個位置 */
    }
    q->maxSize = 2 * q->maxSize;    /* 把隊列空間大小修改為新的長度 */
    return;
}

/* 1.初始化隊列 */
void initQueue(struct queue *q, int ms)
{
    /* 檢查ms是否有效，若無效則退出運行 */
    if(ms <= 0){
        printf("ms值非法! ");
        exit(1);
    }
    q->maxSize = ms;        /* 置隊列空間大小為ms */
    /* 動態存儲空間分配，若失敗則退出運行 */
    q->queue = malloc(ms * sizeof(elemType));
    if(!q->queue){
        printf("內存空間分配失敗！ ");
        exit(1);
    }
    q->front = q->rear = 0;        /* 初始置隊列為空 */
    return;
}

/* 2.向隊列中插入元素x */
void enQueue(struct queue *q, elemType x)
{
    /* 當隊列滿時進行動態生分配 */
    if((q->rear + 1) % q->maxSize == q->front){
        againMalloc(q);
    }
    q->rear = (q->rear + 1) % q->maxSize;        /* 求出隊尾的下一個位置 */
    q->queue[q->rear] = x;                        /* 把x的值賦給新的隊尾 */
    return;
}

/* 3.從隊列中刪除元素並返回 */
elemType outQueue(struct queue *q)
{
    /* 若隊列為空則終止運行 */
    if(q->front == q->rear){
        printf("隊列為空，無法刪除！ ");
        exit(1);
    }
    q->front = (q->front +1) % q->maxSize;        /* 使隊首指針指向下一個位置 */
    return q->queue[q->front];                    /* 返回隊首元素 */
}

/* 4.讀取隊首元素，不改變隊列狀態 */
elemType peekQueue(struct queue *q)
{
    /* 若隊列為空則終止運行 */
    if(q->front == q->rear){
        printf("隊列為空，無法刪除！ ");
        exit(1);
    }
    return q->queue[(q->front +1) % q->maxSize];/* 隊首元素是隊首指針的下一個位置中的元素 */
}

/* 5.檢查一個隊列是否為空，若是則返回1,否則返回0 */
int emptyQueue(struct queue *q)
{
    if(q->front == q->rear){
        return 1;
    }else{
        return 0;
    }
}

/* 6.清除一個隊列，並釋放動態存儲空間 */
void clearQueue(struct queue *q)
{
    if(q->queue != NULL){
        free(q->queue);
        q->queue = NULL;            /* 設置隊列空間指針為空 */
        q->front = q->rear = 0;        /* 設置隊列為空 */
        q->maxSize = 0;                /* 設置隊列大小為0 */
    }
    return;
}

/************************************************************************/

int main(int argc, char* argv[])
{
    struct queue q;
    int a[8] = {3, 8, 5, 17, 9, 30, 15, 22};
    int i;
    initQueue(&q, 5);
    for(i = 0; i < 8; i++){
        enQueue(&q, a[i]);
    }
    printf("%d ", outQueue(&q));    printf("%d  ", outQueue(&q));
    enQueue(&q, 68);
    printf("%d ", peekQueue(&q));    printf("%d  ", outQueue(&q));
    while(!emptyQueue(&q)){
        printf("%d ", outQueue(&q));
    }
    printf(" ");
    clearQueue(&q);
    system("pause");
    return 0;
}