[数据结构基础]栈和队列的结构及接口函数

news/2024/11/15 5:55:25/

一. 栈

1.1 栈的概念及结构

  • 栈是一种特殊的线性表，其只允许在固定的一段进行插入和删除元素的操作。进行数据插入和删除的一端成为栈顶，另一端称为栈底。栈结构中的数据遵循先进后出原则（LIFO：Last in First Out），即先存入栈的数据后出栈，后存入栈的数据先出栈。图1.1为栈结构中数据存取的抽象图。
图1.1 数据存取抽象图
  • 压栈：在栈中插入数据的操作称为进栈/压栈/入栈
  • 出栈：栈中数据删除的操作称为出栈

1.2 栈结构的实现

  • 栈结构有两种实现方式：数组栈和链式栈（见图1.2）。
  • 数组栈的结构类似于顺序表，其优点是可以随机访问栈中元素（通过下标访问），缺点是可能存在空间浪费和动态开辟内存存在消耗。
  • 用链式结构实现栈一般用链表表头作为栈顶，如果要用链表尾做为栈顶，则应设计为双向链表，否则每次进行出栈和入栈操作都要通过循环找链表尾（找栈顶），效率低下。
图1.2  数组栈和链式栈的抽象结构图

数组栈和链式栈那种更优？

由于数组结构实现的栈相对于链式结构实现的栈操作简单便捷，进行入栈和出栈操作效率高且缓存利用率高，数组结构实现的栈相对于链式结构实现的栈唯一的缺点就是增容，但链式结构实现的栈每存储一个数据都要存储一个对应的指针，存储指针也存在空间消耗。因此，综合比较，数组结构实现的栈略优。

定义数组栈的代码：

typedef int STDataType;  //数组栈中存储的数据类型

typedef struct stack

{

        STDataType* a;   //指向数组栈内存空间的指针

        int top;  //栈顶在数组中的下标

        int capacity;  //栈中最多可以容纳的数据个数

}ST;  //将数组栈结构体类型重定义为ST

1.3 栈的接口函数

1.3.1 栈初始化接口函数StackInit

初始化栈结构，经初始化后的栈暂时不存储数据，因此栈顶下标top和栈容量capacity均初始化为0，指向栈中数据内存空间的指针a初始化为NULL。

StackInit函数代码：

void StackInit(ST* ps)
{ps->a = NULL;ps->top = 0;  //top表示栈顶压栈元素位置ps->capacity = 0;  //栈容量
}

1.3.2 销毁栈接口函数StackDestroy

先释放存储数据的栈空间，然后将栈顶下标top和栈容量capacity均置0。

StackDestroy函数代码：

void StackDestroy(ST* ps)
{assert(ps);free(ps->a); ps->a = NULL;  //释放栈内存空间ps->top = 0;ps->capacity = 0;  
}

1.3.3 压栈接口函数StackPush

  • 函数先通过assert(ps)语句判断是否传入空指针，若传入的不是空指针，则通过判断ps->top==ps->capacity是否成立来判断栈中是否还存在剩余空间，若不存在剩余空间，则进行扩容操作。
  • 向栈中压入数据x，将数组下标为top处的元素置为x，然后执行ps->top++操作来记录栈顶的变化。
图1.3  压栈前后栈内存示意图

StackPush函数代码：

void StackPush(ST* ps, STDataType x)
{assert(ps);//判断栈是否已满，满了就扩容if (ps->top == ps->capacity){int new_capacity = (ps->capacity == 0 ? 4 : 2 * ps->capacity);STDataType* tmp = (STDataType*)realloc(ps->a, new_capacity * sizeof(STDataType));if (tmp == NULL){exit(-1);}ps->capacity = new_capacity;ps->a = tmp;}ps->a[ps->top] = x;ps->top++;
}

1.3.4 出栈接口函数StackPop

  • 函数先通过两个assert确保传入的参数不是空指针以及栈中存在数据，再通过ps->top--语言改变栈顶下标，以此来达到出栈的目的。
  • 除ps->top--语句以外，这里不需要另外的语句来删除数据。因为ps->top--改变栈顶下标，ps->top下标处后面的元素并不会被读取，再向栈中压入数据是压到改变后的下标ps->top处，再进行出栈操作是删除栈中ps->top-1下标处的元素。
图1.4 出栈前后top的变化示意图

StackPop函数代码：

void StackPop(ST* ps)
{assert(ps);  //保证栈指针不为NULLassert(ps->top);  //保证栈中有数据ps->top--;
}

1.3.5 栈顶元素获取接口函数StackTop

  • 先通过assert(ps)确保函数接收的参数不是空指针，再通过assert(ps->top>0)来确保栈中存有数据。
  • 栈顶元素在数组中的下标为ps->top-1，函数返回ps->a[ps->top-1]即可获取栈顶元素。
图1.5 栈顶数据及其下标示意图

StackTop函数代码：

STDataType StackTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}

1.3.6 获取栈中数据个数接口函数StackSize

ps->top的值等于栈中数据的个数。因此，在assert(ps)确保函数接收的参数不是空指针后，直接返回ps->top即可。

StackSize函数代码：

int StackSize(ST* ps)
{assert(ps);return ps->top;
}

1.3.6 判断栈是否为空接口函数StackEmpty

栈为空时top=0，因此函数判断ps->top==0是否成立即可。

StackEmpty函数代码：

bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

二. 队列

2.1 队列的概念及结构

  • 队列是一种只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。队列具有先进先出的特点FIFO（First in First Out）。
  • 入队列：进行插入数据操作的一端称为队尾
  • 出队列：进行删除数据操作的一端称为队头
图2.1 队列抽象结构示意图

2.2 队列的实现

队列可以通过链表实现也可以通过数组（顺序表）实现，使用链表实现队列要优于使用数组实现，因为使用数组实现队列进行删除数据时移动链表中的每个数据，效率低下。

用代码定义队列：

typedef int QDataType;   //将队列数据类型重定义为QDataType

//队列节点

typedef QueueNode 

{

        struct QueueNode* next;   //指向下一个队列节点的指针

        QDataType val;  //队列中的数据

}QueueNode;   //将队列节点结构体类型重定义为QueueNode

//包含指向队列队头和队尾的指针的结构体

typedef struct Queue

{

        QueueNode* head;  //指向队头的指针

        QueueNode* tail;  //指向队尾的指针

}Queue;

2.3 队列的接口函数

2.3.1 队列初始化接口函数QueueInit

assert断言传入函数的不是空指针，然后将队头指针head和队尾指针tail均置为空指针即可。

QueueInit函数代码：

void QueueInit(Queue* pq)
{assert(pq);  pq->head = NULL;pq->tail = NULL;
}

2.3.2 队列销毁接口函数QueueDestroy

  • 首先断言传入函数的参数不是空指针，然后遍历队列（链表）的每一个节点，依次释放每个节点的内存空间。
  • 将指向队头的指针和指向队尾的指针均置为空指针。

QueueDestroy函数代码：

void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* cur = pq->head;//使用cur遍历队列的每一个节点，释放内存空间while (cur){QueueNode* next = cur->next;free(cur);cur = next;}//将队列头指针和尾指针均置为NULLpq->head = NULL;pq->tail = NULL;
}

2.3.3 向队列中插入数据接口函数QueuePush

  • assert断言确定传入函数的不是空指针后，为存储插入数据x的新队列节点开辟内存空间，新节点的next指针指向NULL。
  • 分类讨论，若队列中无数据（pq->tail == NULL成立），则队头和队尾均置为新创建的节点，若队列中有数据，原来的队尾节点的next指针指向新节点，队尾改为新节点。
图2.2  链式队列插入数据前后的结构变化

QueuePush函数代码：

void QueuePush(Queue* pq, QDataType x)
{assert(pq);//为新插入的数据创建节点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (NULL == newnode){exit(-1);}newnode->val = x;newnode->next = NULL; //新节点向后指向NULL//分类讨论，若队列中原本无数据，则头结点为新创建的节点//若队列中有数据，则将链表原来的尾结点和新节点进行连接，更改尾结点为新节点if (pq->head == NULL){pq->head = newnode;pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}
}

2.3.4 从队列中删除数据接口函数QueuePop

  • 通过assert(pq)和assert(pq->tail)来确保传入函数的不是空指针以及队列中有数据。
  • 释放队头结点的内存空间，将指向队头的指针改为第二个节点(pq->head->next)。
  • 通过判断pq->head==NULL是否成立来判断删除数据后的队列是否还有数据，如果pq->head==NULL成立则表明队列中没有数据，应将指向队尾的指针pq->tail置为空指针。
图2.3 链式队列删除数据前后结构变化情况示意图

QueuePop函数代码：

void QueuePop(Queue* pq)
{assert(pq);assert(pq->head);  //断言队列中有数据//释放头结点，将队头改为原来的第二个节点//如果队列中所有数据均被删除，则将队尾指针改为NULL以防止野指针QueueNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL){pq->tail = NULL;}
}

2.3.5 获取队尾数据接口函数QueueBack

在确保队列中有数据后，让函数返回pq->tail节点中存储的数据pq->tail->val即可。

QueueBack函数代码：

QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->head);  //断言队列中含有数据return pq->tail->val;
}

2.3.6 获取队头数据接口函数QueueFront

在确保队列中有数据后，让函数返回pq->head节点中存储的数据pq->head->val即可。

QueueFront函数代码：

QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->head); //断言队列中含有数据return pq->head->val;
}

2.3.7 获取队列中数据个数接口函数QueueSize

在确保传入函数的不是空指针后，以pq->head为起点，pq->tail为终点，遍历队列的每一个节点，统计遍历到的节点的个数即可。

QueueSize函数代码：

int QueueSize(Queue* pq)
{assert(pq);int num = 0;QueueNode* cur = pq->head;//遍历队列中每个节点，直到遇到队尾空指针while (cur){++num;cur = cur->next;}return num;
}

2.3.8 判断队列是否为空接口函数QueueEmpty

若队列为空，则pq->head==NULL成立，函数返回pq->head==NULL的值即可。

QueueEmpty函数代码：

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;
}

http://www.ppmy.cn/news/9225.html

相关文章

【数据篇】33 # 可视化数据处理的一般方法是什么？

【数据篇】33 # 可视化数据处理的一般方法是什么？

说明 【跟月影学可视化】学习笔记。 数据可视化的一般过程 先看有什么样的数据：分析真实数据然后看想从数据中了解什么信息：获取想要的信息再决定使用何种可视化方式呈现：为数据选择正确的呈现形式最后看展示的效果怎么样，是否…
阅读更多...
mysql 存储过程批量删除重复数据

mysql 存储过程批量删除重复数据

mysql 存储过程批量删除重复数据 表结构： LOAD DATA INFILE /usr/local/phone_imsi_12 replace INTO TABLE tbl_imsi2number_new FIELDS TERMINATED BY \t ENCLOSED BY (number,imsi); 先用SQL语句来进行去重操作： delete from tbl_imsi2number_new …
阅读更多...
191：vue+openlayers 选择feature，固定按钮删除selected feature

191：vue+openlayers 选择feature，固定按钮删除selected feature

第191个 点击查看专栏目录 本示例的目的是介绍如何在vue+openlayer中使用select来选择feature元素，通过按键来删除selected的feature。 直接复制下面的 vue+openlayers源代码，操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源代码（共95行）相关API参考专栏目标…
阅读更多...
Qt编译CTK

Qt编译CTK

文章目录一、CTK简介二、CTK下载三、CTK编译一、CTK简介 CTK是什么 CTK 为支持生物医学图像计算的公共开发包，其全称为 Common Toolkit CTK 提供了什么 当前，CTK 工作的主要范围包括： DICOM：提供了从 PACS 和本地数据库中查询和…
阅读更多...
redis配置文件

redis配置文件

redis主要配置项： bind 0.0.0.0 #监听地址，可以用空格隔开后多个监听IP protected-mode yes #redis3.2 之后加入的新特性，在没有设置bind IP和密码的时候,redis只允许访问 127.0.0.1:6379，远程访问将提示警告信息并拒绝远程访问…
阅读更多...
java基础 多线程

java基础 多线程

线程(thread)是一个程序内部的一条执行路径。 多线程的实现方案一：继承Thread类 public Thread(String name) 可以为当前线程指定名称 public Thread(Runnable target) 封装Runnable任务对象成为线程对象 public Thread(Runnable target &#x…
阅读更多...
CAN 通信协议

CAN 通信协议

CAN 概述 CAN 是Controller Area Network 的缩写（以下称为CAN），它的设计目标是以最小的CPU负荷来高效处理大量的报文。1986 年德国电气商BOSCH公司开发出面向汽车的CAN 通信协议。此后，CAN 通过ISO11898 及ISO11519 进行了标准化…
阅读更多...
数据在内存中的存储

数据在内存中的存储

专栏：C语言 每日一句：立志趁早点，上路轻松点，目光放远点，苦累看淡点，努力多一点，奋斗勇一点，胜利把名点，祝你折桂冠，成功新起点，幸福多一点&#…
阅读更多...
最新文章

Copyright @ 2022~2023