数据结构与算法学习笔记三---栈和队列

目录

前言

一、栈

1.栈的表示和实现

1.栈的顺序存储表示和实现

1.C语言实现

2.C++实现

2.栈的链式存储表示和实现

1.C语言实现

2.C++实现

2.栈的应用

1.数制转换

二、队列

1.栈队列的表示和实现

1.顺序队列的表示和实现

2.链队列的表示和实现

2.循环队列

---

前言

    这篇文章主要介绍栈和队列的用法。

一、栈

        栈和队列都是访问受限的线性表。栈仅允许在表尾进行插入和删除操作。对于栈来说，允许操作的那一端叫栈顶，表头端口称为栈底。不含元素的空表称为空栈。

        栈的示意图如下：

  图1.栈的示意图

1.栈的表示和实现

        和线性表一样，栈也有两种存储表示方法。

1.栈的顺序存储表示和实现

        栈顶指针和栈中元素之间的关系如下图所示

        图2.栈顶指针和栈中元素之间的关系

1.C语言实现

        顺序栈的C语言实现看这里。

2.C++实现

        顺序栈的C++实现在这里。

2.栈的链式存储表示和实现

        链栈指的是采用链式存储实现的栈。链栈的示意图如下。

        图3.链栈示意图

        链栈的结点结构与单链表相同，这里不需要使用单链表的头结点。

1.C语言实现

        我用C语言实现了链栈，具体的实现可以看这篇文章。

2.C++实现

        C++的实现在这里。

2.栈的应用

1.数制转换

        例如我们要把十进制的168转成8进制的250。算法如下：

        图4.进制转换的算法

        这里使用C语言实现了一下，其实进制转换的过程就是栈push和pop的过程，核心代码如下：

// 数制转换函数
void conversion(int decimalNumber, int base) {SqStack stack;initSqStack(&stack); // 初始化栈// 字符集用于将余数转换为相应的字符char charSet[] = "0123456789ABCDEF";// 进行数制转换while (decimalNumber != 0) {int remainder = decimalNumber % base; // 计算余数pushSqStack(&stack, remainder); // 将余数入栈decimalNumber /= base; // 更新十进制数}// 输出转换结果printf("转换结果为：");while (!sqStackEmpty(&stack)) {int digit;popSqStack(&stack, &digit); // 从栈中取出数字printf("%c", charSet[digit]); // 输出对应的字符}printf("\n");
}void conversionTestUnit(void){int decimalNumber, base;// 输入十进制数和目标数制printf("请输入要转换的十进制数：");scanf("%d", &decimalNumber);printf("请输入目标数制（例如，二进制输入2，八进制输入8，十六进制输入16）：");scanf("%d", &base);// 进行数制转换并输出结果printf("将十进制数 %d 转换为 %d 进制的结果是：\n", decimalNumber, base);conversion(decimalNumber, base);
}

二、队列

        队列也是一种访问受限的线性表，仅允许在表头删除，表尾插入操作。队列是一种先进先出（FIFO）的线性表。

        队列的示意图如下：

        图4.队列的示意图

1.栈队列的表示和实现

1.顺序队列的表示和实现

        在队列的顺序存储结构中，除了使用使用一组连续的存储单元存放队列数据元素之外，设置一个头结点和尾节点。我们约定初始化的时候front = rear = 0.入队之后front+1;出队列之后，rear+1。        

              图5.顺序队列中头指针和尾指针以及数据元素之间的关系

        这里分别使用C语言和C++实现了顺序队列。

2.链队列的表示和实现

        使用链表表示的队列称为链队。示意图如下：

        图6.链队示意图

        这里分别使用C语言和C++实现了链队列。

2.循环队列

        为了防止顺序栈的“假溢出问题”，引入了循环队列。即牺牲顺序队列的一个存储空间，进行队尾+1取模运算。

        循环队列的示意图如下：

        图5.循环队列示意图

        这里分别使用C语言和C++实现了循环队列。