栈和队列（1）
空栈先移动栈顶再加数据，满栈先插入数据再移
栈的基本概念栈是一种后进先出（LIFO，Last In First Out）的数据结构。栈支持两种主要的操作：•压栈（Push）：向栈中添加一个元素。•弹栈（Pop）：从栈顶移除一个元素。
术语解释1. 空栈（Empty Stack）：•一个没有任何元素的栈。•空栈的大小为 0。
在栈的数据结构中，栈顶指针（通常称为 top）用于指示栈顶元素的位置。对于空栈而言，栈顶指针通常设置为 -1，这意味着栈顶指针并没有指向任何实际的元素。栈顶指针的含义1. 空栈：•当栈是空的时候，栈顶指针 top 设置为 -1。•这意味着栈中没有任何元素，栈顶指针指向栈底前的一个位置。2. 非空栈：•当栈中有元素时，栈顶指针 top 指向栈顶元素的位置。•栈顶元素位于数组的 top 下标位置。
2. 满栈（Full Stack）：•一个达到了最大容量的栈。•如果继续压栈，将会导致溢出（overflow）
满栈（full stack）是指栈已经达到了其最大容量，不能再添加新的元素。在满栈的情况下，栈顶仍然有一个元素，只是这个栈无法再接受更多的元素了。满栈的定义满栈指的是栈中的元素数量已经达到其设定的最大容量，此时不能再进行压栈（push）操作，否则就会发生栈溢出（overflow）。栈顶的状态无论栈是否满，只要栈不为空，栈顶就一定存在一个元素。满栈的状态是栈顶有元素，但不能再向栈中添加新的元素。。
3. 增栈（Push Operation）：•向栈中添加一个元素的操作。•如果栈已经是满栈，继续压栈会导致溢出。•如果栈是空栈，压栈后栈就不再是空栈。
4. 减栈（Pop Operation）：•从栈顶移除一个元素的操作。•如果栈是空栈，继续弹栈会导致下溢（underflow）。
5. 空增栈（Push on Empty Stack）：•在空栈上进行压栈操作。•压栈后，栈不再是空栈。
6. 满增栈（Push on Full Stack）：•在满栈上进行压栈操作。•这种操作会导致栈溢出（overflow），通常程序会抛出错误或异常。
在讨论栈（stack）的操作（如增栈（push）和减栈（pop））时，栈的实现方式会影响栈顶指针相对于内存地址的变化。具体来说，栈可以在内存中向上增长（向高地址方向增长）或向下增长（向低地址方向增长）。这里我们探讨栈的增长方向与增栈、减栈的关系。栈的增长方向栈的增长方向取决于实现方式，主要有两种：1. 向上增长（Growing Upwards）：•栈顶指针随着元素的增加而向更高的地址移动。•新的元素总是被添加到较高的地址处。•弹栈（pop）时，栈顶指针向较低的地址移动。2. 向下增长（Growing Downwards）：•栈顶指针随着元素的增加而向更低的地址移动。•新的元素总是被添加到较低的地址处。•弹栈（pop）时，栈顶指针向较高的地址移动
栈的容量栈的容量是一个静态属性，通常在栈创建时就已经确定，它决定了栈最多能存储多少个元素。栈的容量是由栈的实现方式决定的，比如在顺序栈中，容量通常由分配给栈的数组大小决定。栈顶指针栈顶指针（top）是一个动态属性，它会随着压栈（push）和弹栈（pop）操作而变化。栈顶指针用来指示当前栈顶元素的位置。
关系•栈顶指针（top）：指向当前栈顶元素的位置。在空栈的情况下，top 通常初始化为 -1。
•栈的容量（capacity）：栈可以容纳的最大元素数量。
系统栈（System Stack）系统栈是操作系统和编译器提供的栈，主要用于存储函数调用过程中的局部变量、函数参数、返回地址等信息。系统栈的主要特点如下：1. 自动管理：•系统栈由操作系统和编译器自动管理，程序员不需要手动控制它的增长或缩减。•每当函数被调用时，系统栈会自动为其分配空间，并在函数返回时释放空间。2. 有限容量：•系统栈的容量通常是有限的，由操作系统分配。如果超出容量限制，则会发生栈溢出（stack overflow）。•由于系统栈的空间是有限的，因此递归深度过深或者局部变量占用过多空间可能导致栈溢出。3. 用途：•存储函数调用期间的局部变量、函数参数、返回地址等信息。•用于保存函数调用堆栈，跟踪函数调用的历史。4. 增长方向：•系统栈通常向下增长（向低地址方向增长），这样更容易管理和实现。5. 实现：•系统栈由硬件和操作系统底层支持，通常使用 CPU 提供的寄存器来管理栈指针（如 ESP/rsp）。数据结构栈（Data Structure Stack）数据结构栈是一种抽象数据类型（ADT），它提供了一组标准的操作（如 push 和 pop），遵循先进后出（LIFO）的原则。
数据结构栈的主要特点如下：1. 手动管理：•数据结构栈由程序员自己实现和管理，可以使用数组或链表等多种数据结构来实现。•程序员需要自己控制栈的增长或缩减。2. 可变容量：•数据结构栈的容量可以根据需要动态调整，可以通过重分配内存来扩展或缩小栈的大小。•可以通过预先设置容量或者动态扩展来避免栈溢出。3. 用途：•用于实现算法中的临时数据存储，如表达式求值、括号匹配、回溯算法等。•可以作为数据缓冲区或其他数据处理过程中的中间存储。4. 增长方向：•数据结构栈的增长方向可以根据实现方式灵活选择，既可以向上增长也可以向下增长。5. 实现：•数据结构栈可以使用数组或链表等多种数据结构来实现。•可以在任何编程语言中实现，且实现细节由程序员决定。
队列（Queue）是一种基本的数据结构，它具有特定的特性和操作行为。队列是一种先进先出（FIFO，First In First Out）的数据结构，即最先加入队列的元素最先被移除。以下是队列的一些主要特性：1. 先进先出（FIFO）这是队列最核心的特性。队列中的元素按照它们进入队列的顺序被处理。最先加入队列的元素最先被移除（出队）。（可用io于缓冲区）
操作系统中的 I/O 缓冲区通常位于内存中，以下是几个例子：Linux 中的 I/O 缓冲区Linux 操作系统提供了多种类型的 I/O 缓冲区，包括：•页缓存（Page Cache）：•页缓存用于缓存文件系统的读写操作。当应用程序请求读取文件时，操作系统会首先检查页缓存中是否有该文件的数据。如果有，就直接从内存中读取；如果没有，则从磁盘读取并存入页缓存中。•类似地，当应用程序写入文件时，数据首先被写入页缓存中，然后在适当的时候同步到磁盘。•块缓存（Block Cache）：•块缓存用于缓存块设备上的读写操作。尽管现代 Linux 内核中，块缓存已经被页缓存所取代，但概念上仍然存在。当你在程序中写入文件时，操作系统通常不会立即把数据写入硬盘，而是先将数据存放在内存中的缓冲区（也称为缓存）。这个过程是为了提高 I/O 效率。具体来说，操作系统会将数据写入一个内存缓冲区，当缓冲区写满或满足某些条件时，操作系统才会将数据实际写入硬盘。
2. 主要操作队列支持两种主要操作：•入队（Enqueue）：在队列的尾部添加一个新的元素。•出队（Dequeue）：从队列的头部移除一个元素。
3. 特殊指针队列通常使用两个指针来管理：•头指针（Front）：指向队列的第一个元素。•尾指针（Rear）：指向队列的最后一个元素。
4. 空队列与满队列•空队列（Empty Queue）：队列中没有任何元素。•满队列（Full Queue）：队列中已经无法再添加新的元素，因为它已经达到了最大容量。
5. 动态与静态队列•静态队列：队列的大小在创建时固定，不能改变。•动态队列：队列的大小可以随着元素的添加和移除动态调整。
6. 循环队列•循环队列（Circular Queue）：队列的头部和尾部相连，形成一个循环结构，可以更高效地利用存储空间。 •假溢出问题：在循环队列中，由于头指针和尾指针的位置关系，即使队列中还有空闲空间，也可能无法插入新的元素。
7. 双端队列（Deque）•双端队列（Double-ended Queue，Deque）：允许在队列的两端同时进行插入和删除操作，因此它结合了队列和栈的特性。
8. 优先队列（Priority Queue）•优先队列（Priority Queue）：每个元素都有一个优先级，队列按照优先级的高低顺序处理元素，而不是按照加入队列的顺序。
9. 阻塞队列（Blocking Queue）•阻塞队列（Blocking Queue）：当队列满时，试图入队的线程会被阻塞；当队列空时，试图出队的线程会被阻塞，直到队列变得非空。
10. 并发安全•并发安全队列：在多线程环境中，队列需要确保线程安全，防止多个线程同时访问队列导致的数据不一致问题。
队列假溢出（pseudo-overflow）是指在循环队列（Circular Queue）中出现的一种现象。在循环队列中，即使还有可用空间，但由于队列的头指针（front）和尾指针（rear）的特殊位置关系，使得队列看起来像是满了，但实际上还可以插入新的元素。这种情况就是所谓的“假溢出”。循环队列的特点循环队列是一种特殊的队列实现，其中队列的头部和尾部连接起来形成一个圆环，这样可以有效地利用队列的存储空间。循环队列的关键在于队列的头指针（front）和尾指针（rear）的管理。队列假溢出的原因在循环队列中，如果只使用尾指针（rear）来表示队列的末尾位置，并且头指针（front）来表示队列的起始位置，那么在某些情况下，即使队列中还有空闲空间，也可能因为头指针和尾指针的位置关系导致无法插入新的元素。
文件系统缓存的作用包括：1. 减少磁盘访问：•通过将数据暂存在内存中，减少了对磁盘的实际访问次数，从而提高了读取速度。2. 提高读取效率：•对于重复读取相同数据的情况，可以直接从内存中读取，无需每次都访问磁盘。3. 平滑数据流：•在连续读取大量数据时，文件系统缓存可以提供平滑的数据流，即使磁盘读取速度不稳定，也可以保持稳定的读取速率。注意事项虽然文件系统缓存可以显著提高读取效率，但也需要注意以下几点：1. 内存占用：•文件系统缓存会占用一定量的内存，特别是在读取大量数据时。如果内存不足，可能会导致其他应用程序受到影响。2. 数据一致性：•在某些情况下，如果文件系统缓存中的数据没有及时更新，可能会导致应用程序读取到旧的数据。因此，在需要严格一致性的场景中，可能需要显式地刷新缓存。
线程邮箱：队列
指针函数： 返回值为指针的函数
1. 返回de指针不能指向一个局部变量的空间
2. malloc
全局变量
静态变量
3.返回值判断
