美文网首页
数据结构与算法（六）-- 队列（Queue）

数据结构与算法（六）-- 队列（Queue）

作者: 樂亦leeyii | 来源:发表于2020-04-14 23:26 被阅读0次

队列具有新进先出(FIFO)的特点.

1 队列的顺序结构

1.1 数据结构

#define OK 1
#define ERROR 0

#define TRUE 1
#define FALSE 0

#define MAXSIZE 10

typedef int QElemType;
typedef int Status;

typedef struct {
    int data[MAXSIZE];  // 存放数据的数组
    int front;          // 队首索引
    int rear;           // 队尾索引
}SqQueue;

1.2 入栈和出栈的实现

假设一个可以容纳5个元素的队列，如下：

{ x, x, x, x, x }
  ^
 front
 rear

我们使用 x 表示这个位置还没有插入任何元素.

此时队列的front 和 rear 都为0。

我们将元素1 2 3 和 4 依次入队，那么现在队列中的内容如下：

{ 1, 2, 3, 4, x }
  ^           ^
front        rear

现在front为0， rear为4, 接下来我们将 1 和 2 出队，队列内容为:

{ x, x, 3, 4, x }
        ^     ^
      front  rear

接着，我们将元素5 6依次入队，当元素6入队时，就会出现溢出，实际上队列中还有3个空位，但是现在只能入队1个元素，这里的溢出我们称之为假溢出。

为了解决假溢出，将队列的空间进行充分的利用，这里我们可以引入了一个循环队列的概念，当队尾索引等于数组的最大索引时，当下一个元素入队时，我们从数组的索引为0的位置开始入队。那么现在将元素5 6入队后，队列的内容如下：

{ 6, x, 3, 4, 5 }
     ^  ^     
   rear front

这样就能将充分的将空间利用起来， 但是现在又存在一个问题，如果我们继续入队元素7后：

{ 6, 7, 3, 4, 5 }
        ^
      front
       rear

这里队首索引和队尾索引又相等了，这时我们将无法区分队列为空和队列满的时候。因此当队列中只有一个空位时，我们就认为队列满了，不能继续入队，这样队列满的时候他们首尾索引就不相等了。

{ 6, x, 3, 4, 5 }
     ^  ^     
   rear front

1.3 代码实现

// 1.初始队列
Status initQueue(SqQueue *Q) {
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

// 2.队列清空
Status clearQueue(SqQueue *Q) {
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

// 3.队列是否为空
Status queueEmpey(SqQueue Q) {
    return Q.rear == Q.front;
}

// 4.队列的长度
int queueLength(SqQueue Q) {
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

// 5.获取队列的头部
Status getQueueHead(SqQueue Q, QElemType *e) {
    if (Q.rear == Q.front) return ERROR;
    *e = Q.data[Q.front];
    return OK;
}

// 6.入队
Status enqueue(SqQueue *Q, QElemType e) {
    if ((Q->rear + 1) % MAXSIZE == Q->front) return ERROR;
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return OK;
}

// 7.出队
Status dequeue(SqQueue *Q, QElemType *e) {
    if (Q->front == Q->rear) return ERROR;
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return OK;
}

// 遍历
void queueTraverse(SqQueue Q) {
    
    int i = Q.front;
    while (i != Q.rear) {
        printf("%d  ", Q.data[i]);
        i = (i + 1) % MAXSIZE;
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    // insert code here...
    
    SqQueue Q;
    QElemType e;
    
    if (initQueue(&Q)) {
        printf("初始化队列成功\n");
    }
    
    for (int i = 0; i < 10; i++) {
        enqueue(&Q, i);
    }
    printf("队列中的元素为:");
    queueTraverse(Q);
    printf("队列的长度为:%d\n", queueLength(Q));
    dequeue(&Q, &e);
    printf("获取出队元素:%d\n", e);
    printf("队列中的元素为:");
    queueTraverse(Q);
    getQueueHead(Q, &e);
    printf("获取队列头部:%d\n", e);
    printf("队列是否为空:%d\n", queueEmpey(Q));
    printf("清空队列\n");
    clearQueue(&Q);
    printf("队列是否为空:%d\n", queueEmpey(Q));
    printf("队列中的元素为:");
    queueTraverse(Q);
    printf("队列的长度为:%d\n", queueLength(Q));
    
    return 0;
}

//输出:
//初始化队列成功
//队列中的元素为:0  1  2  3  4  5  6  7  8
//队列的长度为:9
//获取出队元素:0
//队列中的元素为:1  2  3  4  5  6  7  8
//获取队列头部:1
//队列是否为空:0
//清空队列
//队列是否为空:1
//队列中的元素为:
//队列的长度为:0

2 队列的链式结构

使用顺序储存结构时，会出现假溢出问题，因此我们引入循环队列的概念来解决假溢出问题，这样的话如果队列满了，要将队列进行扩容时，将会变得十分复杂。如果我们使用链式结构来实现队列的话就没有上面的问题。

2.1 数据结构

#define OK 1
#define ERROR 0

#define TRUE 1
#define FALSE 0

typedef int QElemType;
typedef int Status;

typedef struct QNode {
    QElemType data;
    struct QNode *next;
}QNode, *QNodePtr;

typedef struct {
    QNodePtr front;
    QNodePtr rear;
    int count;
} LinkQueue;

2.2 代码实现

// 1.初始化
Status initQueue(LinkQueue *Q) {
    if (Q == NULL) return ERROR;
    // 初始化头结点
    Q->rear = Q->front = (QNodePtr)malloc(sizeof(QNode));
    if (Q->front == NULL) return ERROR;
    Q->front->next = NULL;
    Q->count = 0;
    return OK;
}

// 2.销毁队列
Status destoryQueue(LinkQueue *Q) {
    if (!Q) return ERROR;
    // 从头结点开始依次释放结点
    while (Q->front) {
        Q->rear = Q->front->next;
        Q->front = Q->front->next;
        free(Q->rear);
    }
    Q->count = 0;
    return OK;
}

// 3.清空队列
Status clearQueue(LinkQueue *Q) {
    if (!Q) return ERROR;
    // 保留头结点,释放其余结点
    QNodePtr p, q;
    // 指向首元结点
    p = Q->front->next;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    Q->front->next = NULL;
    Q->rear = Q->front;
    Q->count = 0;
    return OK;
}

// 4.队列是否为空
Status queueEmpty(LinkQueue Q) {
    return Q.front == Q.rear;
}

// 5.获取队列的长度
int queueLength(LinkQueue Q) {
    return Q.count;
}

// 6.获取队头
Status getQueueHead(LinkQueue Q, QElemType *e) {
    *e = Q.front->next->data;
    return OK;
}

// 7.入队
Status enqueue(LinkQueue *Q, QElemType e) {
    if (!Q) return ERROR;
    QNodePtr p = (QNodePtr)malloc(sizeof(QNode));
    if (!p) return ERROR;
    p->next = NULL;
    p->data = e;
    Q->rear->next = p;
    Q->rear = p;
    Q->count++;
    return OK;
}

// 8.出队
Status dequeue(LinkQueue *Q, QElemType *e) {
    if (!Q) return ERROR;
    if (Q->count == 0) return ERROR;
    // 获取队头结点的值
    *e = Q->front->next->data;
    // 获取队头结点
    QNodePtr p = Q->front->next;
    Q->front->next = p->next;
    free(p);
    Q->count--;
    // 删空后,将队尾指向头结点
    if (Q->count == 0) Q->rear = Q->front;
    return OK;
}

// 9.遍历
void queueTraverse(LinkQueue Q) {
    
    QNodePtr p = Q.front->next;
    
    while (p) {
        printf("%d  ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    // insert code here...
    LinkQueue q;
    int e;
    
    if (initQueue(&q)) {
        printf("队列初始化成功\n");
    }
    for (int i = 0; i < 10; i++) {
        enqueue(&q, i);
    }
    printf("队列中的元素为:");
    queueTraverse(q);
    printf("队列的长度为: %d\n", queueLength(q));
    printf("队列是否为空: %d\n", queueEmpty(q));
    dequeue(&q, &e);
    printf("出队元素为: %d\n", e);
    getQueueHead(q, &e);
    printf("获取队头: %d\n", e);
    printf("队列中的元素为:");
    queueTraverse(q);
    printf("队列的长度为: %d\n", queueLength(q));
    printf("队列是否为空: %d\n", queueEmpty(q));
    clearQueue(&q);
    printf("队列中的元素为:");
    queueTraverse(q);
    printf("队列的长度为: %d\n", queueLength(q));
    printf("队列是否为空: %d\n", queueEmpty(q));
    destoryQueue(&q);
    
    return 0;
}

输出：
队列初始化成功
队列中的元素为:0  1  2  3  4  5  6  7  8  9  
队列的长度为: 10
队列是否为空: 0
出队元素为: 0
获取队头: 1
队列中的元素为:1  2  3  4  5  6  7  8  9  
队列的长度为: 9
队列是否为空: 0
队列中的元素为:
队列的长度为: 0
队列是否为空: 1

相关文章

网友评论

      本文标题：数据结构与算法（六）-- 队列（Queue）

      本文链接：https://www.haomeiwen.com/subject/udyfvhtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|数据结构与算法（六）-- 队列（Queue）|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！