数据结构笔记(四): 队列的顺序存储结构与链式存储结构实现

发布于 / 程序猿 / 0 条评论

使用顺序存储结构(循环队列)与链式存储结构来实现队列,完成队列的基本操作。若文中存在错误,敬请指出,感谢阅读。


基本知识

  • 队列的简介:元素先进先出,只能从队列末端插入和删除元素
  • 队列的基本操作:
#include<queue>
queue <int> q;
q.push(x);//将元素插入到队列末尾
q.pop();//弹出队列的第一个元素(队首),并不会返回元素的值
q.front();//访问队首的元素
q.back();//访问队尾元素
q.size();//返回队列中元素的个数

队列和上文提到的栈类似,本质上都是特殊的线性表,它是在一端(队头)进行删除操作,另一端(队尾)进行插入操作,遵守先进先出的规则。

既然队列也是线性表,当然也有两种数据存储方式:
– 顺序存储结构:这种结构事先要基本确定队列的大小,不支持动态分配存储空间,所以插入和删除元素比较省时,但是会造成空间的浪费。
为了节省空间,这里引入了循环队列,本质上也是顺序存储结构。
– 链式存储结构:可以不需要事先知道队列的大小,支持动态和释放空间,但是插入和删除操作比较耗时,也称链队列。
建议:当事先基本上确定队列的大小,且插入和删除操作比较频繁时,优先考虑循环队列。


演示:

  • 创建一个队列

  • 队首元素出队

  • 入队


代码:

  • 顺序存储结构(循环队列)
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int Max_ArrayQueue_Size = 100; // 队列最大长度

struct ArrayQueue_Tag
{
    int data[Max_ArrayQueue_Size]; // 存储数据
    int head; // 队首
    int rear; // 队尾
};

typedef ArrayQueue_Tag * ArrayQueue; // 使用 ArrayQueue 代替 ArrayQueue_Tag *

ArrayQueue createArrayQueue() // 创建线性表
{
    ArrayQueue ret = NULL;
    ret = (ArrayQueue)malloc(sizeof(struct ArrayQueue_Tag)); // 分配内存
    if (!ret) // 分配失败返回NULL
        return NULL;

    ret->head = ret->rear = 0; // 初始化为0
    return ret;
}

int pushArrayQueue(ArrayQueue Queue, int newValue) // 入队
{
    if (Queue->head == (Queue->rear + 1) % Max_ArrayQueue_Size) // 表示队列已满,返回-1
        return -1;

    Queue->data[Queue->rear++] = newValue;
    if (Max_ArrayQueue_Size == Queue->rear) // 循环从0开始
        Queue->rear = 0;
    return 0;
}

int popArrayQueue(ArrayQueue Queue) // 出队
{
    if (Queue->head == Queue->rear) // 相等表示队列为空,返回-1
        return -1;

    ++Queue->head; // ++(Queue->head),即head后移
    if (Max_ArrayQueue_Size == Queue->head) // 循环从0开始
        Queue->head = 0;
    return 0;
}

int frontArrayQueue(ArrayQueue const Queue, int *pResult) // 获取队首元素
{
    if (Queue->head == Queue->rear) // 相等表示队列为空,返回-1
        return -1;

    *pResult = Queue->data[Queue->head];
    return 0;
}

int backArrayQueue(ArrayQueue const Queue, int *pResult) // 获取队尾元素
{
    if (Queue->head == Queue->rear) // 相等表示队列为空,返回-1
        return -1;

    *pResult = Queue->data[Queue->rear-1];
    return 0;
}

int sizeArrayQueue(ArrayQueue const Queue) // 队列元素个数
{
    return (Queue->rear - Queue->head + Max_ArrayQueue_Size) % Max_ArrayQueue_Size;
}

int isEmptyArrayQueue(ArrayQueue const Queue) // 判断是否为空
{
    return Queue->head == Queue->rear; // 相等表示队列为空,返回-1
}

int destoryArrayQueue(ArrayQueue *pt) // 销毁队列,回收空间
{
    free(*pt);
    pt = NULL;
    return 0;
}

int main()
{
    ArrayQueue A = createArrayQueue();
    for (int i = 1; i <= 100; ++i) // 入队
        pushArrayQueue(A, i);
    cout << sizeArrayQueue(A) << endl; // 大小
    while (!isEmptyArrayQueue(A))
    {
        int result1 = 0, result2 = 0;
        frontArrayQueue(A, &result1); // 队首元素
        backArrayQueue(A, &result2); // 队尾元素
        cout << "head: " << result1 << " rear: " << result2 << endl;
        popArrayQueue(A);
    }
    destoryArrayQueue(&A);
    return 0;
}
  • 链式存储结构
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct Node
{
    int data;
    struct Node *next;
};

struct LinkedQueue_Tag
{
    Node *head;
    Node *rear;
};

typedef LinkedQueue_Tag * LinkedQueue; // 使用 LinkedQueue 代替 LinkedQueue_Tag *

LinkedQueue createLinkedQueue() // 创建队列
{
    Node * pt = NULL;
    pt = (Node *)malloc(sizeof(Node));
    if (!pt)
        return NULL;

    LinkedQueue ret = NULL;
    ret = (LinkedQueue)malloc(sizeof(LinkedQueue_Tag));
    if (!ret)
        return NULL;

    ret->head = ret->rear = pt; // 初始化
    return ret;
}

int pushLinkedQueue(LinkedQueue Queue, int newValue) // 入队
{
    Node *pt = NULL;
    pt = (Node *)malloc(sizeof(Node));
    if (!pt)
        return -1;

    pt->data = newValue; // 存储新值
    pt->next = NULL;
    Queue->rear->next = pt; // 完成入队操作
    Queue->rear = pt;
    return 0;
}

int popLinkedQueue(LinkedQueue Queue) // 出队
{
    if (Queue->head == Queue->rear) // 相等表示为空返回-1
        return -1;

    Node *pt = Queue->head->next;
    if (pt == Queue->rear) // 相差一个元素,出队后为空
        Queue->rear = Queue->head;
    Queue->head->next = pt->next; // 完成出队操作
    free(pt);
    return 0;
}

int frontLinkedQueue(LinkedQueue const Queue, int *pResult) // 取队首元素
{
    if (Queue->head == Queue->rear) // 相等表示为空返回-1
        return -1;

    *pResult = Queue->head->next->data;
    return 0;
}

int isEmptyLinkedQueue(LinkedQueue const Queue) // 判断是否为空
{
    return Queue->head == Queue->rear;
}

int sizeLinkedQueue(LinkedQueue const Queue) // 获取队列元素个数
{
    Node* pt = Queue->head->next;
    int cnt = 0;
    while (pt)
    {
        pt = pt->next;
        ++cnt;
    }
    return cnt;
}

int destoryLinkedQueue(LinkedQueue * pt) // 销毁队列,回收内存
{
    while ((*pt)->head != (*pt)->rear)
        popLinkedQueue(*pt);
    free((*pt)->head);
    free(*pt);
    pt = NULL;
    return 0;
}

int main()
{
    LinkedQueue A =  createLinkedQueue();
    for (int i = 1; i <= 99; ++i)
        pushLinkedQueue(A, i);
    cout << sizeLinkedQueue(A) << endl;
    while (!isEmptyLinkedQueue(A))
    {
        int result = 0;
        frontLinkedQueue(A, &result);
        cout << result << endl;
        popLinkedQueue(A);
    }
    destoryLinkedQueue(&A);
    return 0;
}

本文基础知识部分参考:队列的实现c++

最后,致敬迅哥


The end.
2017-10-28 星期六

转载原创文章请注明,转载自: 太傅 » 数据结构笔记(四): 队列的顺序存储结构与链式存储结构实现
Not Comment Found