数据结构-----栈 、队列

1.数据结构中的栈和系统栈的区别

        数据结构中的栈（Stack）与系统栈在本质上是相似的，都遵循“先进后出”（Last In First Out,

LIFO）的原则，但它们在应用场景、实现方式和管理方式上存在显著的区别。

1.1数据结构中的栈

1. 定义与特性：
   • 数据结构中的栈是一种特殊的线性表，只允许在栈顶进行插入（Push）和删除（Pop）操作。
   • 栈底固定，栈顶随着元素的加入和删除而浮动。
   • 元素按照后进先出的顺序进行排列。
2. 实现方式：
   • 栈可以使用数组或链表来实现。
   • 数组实现的栈称为顺序栈，链表实现的栈称为链栈。
3. 应用场景：
   • 主要用于算法实现，如函数调用、表达式求值、括号匹配、数制转换、迷宫求解等。
   • 程序员需要显式地调用栈操作，如入栈、出栈等。
4. 内存管理：
   • 一般由程序员自行管理内存，如数组的大小限制、扩容等。

1.2系统栈

1. 定义与特性：
   • 系统栈，也称为程序栈或调用栈，是计算机内存中用于存储函数调用相关信息（如函数参数、局部变量、返回地址等）的区域。
   • 它也是遵循后进先出的原则，但存储的是程序的执行状态而非简单的数据元素。
2. 实现方式：
   • 系统栈通常由操作系统或编译器在程序运行时自动创建和管理。
   • 使用内存中的一段连续区域来实现，栈顶随着程序的执行动态变化。
3. 应用场景：
   • 主要用于函数调用的管理，包括参数的传递、局部变量的存储、函数返回地址的保存等。
   • 在多线程程序中，每个线程都有自己的系统栈。
4. 内存管理：
   • 由操作系统或编译器自动管理，程序员无需关心栈的创建、扩容和销毁等细节。
   • 系统栈的大小通常是有限的，如果栈溢出（如递归调用过深），则可能导致程序崩溃。

1.3区别总结

综上所述，数据结构中的栈和系统栈虽然都遵循后进先出的原则，但它们在定义、实现方式、应用场景和内存管理方面存在明显的区别。

2.顺序栈的基本操作

1. 初始化（InitStack）：
   • 分配一个固定大小的数组空间给栈，并设置栈顶指针（或称为栈顶索引）为-1（或数组的起始位置索引，这取决于具体实现，但-1通常用于表示栈为空的情况）。
2. 判断栈空（IsEmpty）：
   • 检查栈顶指针是否等于初始值（如-1），如果是，则栈为空。
3. 判断栈满（IsFull）：
   • 检查栈顶指针是否等于数组的最大索引值减1（因为栈顶指针指向的是栈顶元素的下一个位置），如果是，则栈满。注意，这个操作在固定大小的顺序栈中才有意义，动态数组实现的栈通常不需要这个操作，因为它们可以自动扩容。
4. 入栈（Push）：
   • 将新元素放到栈顶指针指向的位置，并将栈顶指针加1。如果栈满，则入栈操作失败。
5. 出栈（Pop）：
   • 返回栈顶元素的值，并将栈顶指针减1。如果栈空，则出栈操作失败。
6. 获取栈顶元素（GetTop）：
   • 返回栈顶元素的值，但不修改栈顶指针。如果栈空，则获取栈顶元素操作失败。

顺序栈的优缺点

优点：

• 实现简单，支持随机访问（虽然栈的操作主要集中在栈顶，但顺序栈的底层实现是数组，因此可以通过索引快速访问任意位置的元素）。
• 相对于链栈，顺序栈在栈满之前不需要额外的内存分配操作，因此可能具有更好的性能。

缺点：

• 栈的大小在初始化时就固定了，如果栈的大小设置不当，可能会导致栈溢出或内存浪费。
• 在栈的动态变化过程中，如果需要扩容（虽然这通常不是顺序栈的常规操作，但理论上可以通过复制数组到更大的内存空间来实现），则成本较高。

3.数据结构中的队列

3.1定义：

        队列是一种特殊的线性表，其特殊性在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。这种操作方式使得队列具有先进先出（FIFO—First In First Out）的特性。

3.2存储结构：

        队列的存储结构主要分为顺序存储结构和链式存储结构。

3.2.1顺序存储结构：

        使用一组地址连续的存储单元依次存放队列中的元素，并附设两个指针（队头指针front和队尾指针rear）分别指向队头元素和队尾元素的下一个位置。顺序队列可能会出现“假溢出”现象，即队列未满但无法继续插入新元素的情况。为了解决这一问题，引入了循环队列的概念，即将顺序队列的存储空间看成一个首尾相接的环形结构。

3.2.2链式存储结构：

        使用链表来实现队列，称为链队列。链队列中每个节点包含数据域和指向下一个节点的指针域。队头指针指向链队列的头节点（通常不存储数据），队尾指针指向链队列的最后一个节点。链队列不会出现“假溢出”现象，且可以动态增长。

3.3基本操作：

        队列的基本操作包括入队（在队尾插入新元素）、出队（删除队头元素）、判空（检查队列是否为空）、判满（对于循环队列，检查队列是否已满）、求队列长度等。