酷客网栈,队列以及环形缓冲区，栈和队列，都可以不通过指定地址和索引来对数组的元素进行读写。需要临时保存计算过程中的数据、连接在计算机上的设备或者输入输出的数据时，都可以通过这些方法来使用内存。如果每次保存临时数据都需指定地址和索引，程序就会变得比较麻烦，因此要加以改进。
栈和队列的区别在于数据出入的顺序是不同的。在对内存数据进行读写时，栈用的是LIFO（Last Input First Out，后入先出）方式，而队列用的则是FIFO（First Input First Out，先入先出）方式。如果我们在内存中预留出栈和队列所需要的空间，并确定好写入和读出的顺序，就不用再指定地址和索引了。
如果要在程序中实现栈和队列，就需要以适当的元素数来定义一个用来存储数据的数组，以及对该数组进行读写的函数对。当然，在这些函数的内部，对数组的读写会涉及索引的管理，但从使用函数的角度来说，就没有必要考虑数组及索引了。
这里，我们暂且把往栈中写入数据的函数命名为Push，把从栈中读出数据的函数命名为Pop，把往队列中写入数据的函数命名为EnQueue，把从队列中读出数据的函数命名为DeQueue。Push和Pop以及EnQueue和DeQueue分别组成一对函数。Push和EnQueue用于为函数的参数传递要写入的数据。Pop和DeQueue用于将读出的数据作为函数返回值返回。通过使用这些函数，可以将数据临时保存（写入），然后再在需要时候把这些数据读出来（代码清单4-4、代码清单4-5）。
代码清单4-4 使用栈的程序示例
//往栈中写入数据
Push(123); //写入123
Push(456); // 写入456
Push(789); // 写入789
//从栈中读出数据
j =Pop(); // 读出789
k =Pop(); // 读出456
l =Pop(); // 读出123
代码清单4-5 使用队列的程序示例
//往队列中写入数据
EnQueue(123); // 写入123
EnQueue(456); // 写入456
EnQueue(789); // 写入789
//从队列中读出数据
m =DeQueue(); // 读出123
n =DeQueue(); // 读出456
o =DeQueue(); // 读出789
虽然示例程序中没有展示实际的数组以及Push、Pop、EnQueue、DeQueue的处理内容，不过还是希望大家能够据此对栈及队列是如何使用内存的有一个大体印象。
顾名思义，在栈中，LIFO方式表示栈的数组中所保存的最后面的数据（Last In）会被最先读取出来（First Out）。代码清单4-4的程序运行后，按照123、456、789的顺序写入的数据，结果却按照789、456、123的顺序被读取出来（图4-7）。
图4-7 代码清单4-4运行时栈的变化
栈的原意是“干草堆积如山”。干草堆积成山后，最后堆的干草会被最先抽取出来。干草堆也是用来临时保存家禽饲料的方式。程序中也是如此，为了实现临时保存数据的目的，使用这种类似于干草堆的机制是非常方便的。而这种机制体现在内存上，就是栈。当我们需要暂时舍弃当前的数据，随后再原貌还原时，会使用栈。
与栈相对的是队列，顾名思义，FIFO方式表示队列的数组中所保存的最初数据（First Input）会最先被读取出来（First Out）。代码清单4-5中的程序运行后，按照123、456、789的顺序写入的数据，结果会按照123、456、789的顺序被读取出来(图4-8)。
图4-8 代码清单4-5运行时队列的变化
队列这一方式也称为排队。排队指的是买车票时在自动售票机前等候的队列等。排队时，站在最前面的乘客先买票，购买后率先从队列中走出来。当随机前来的购票乘客数量和自动售票机的处理速度不相符时，排队能起到很好的缓冲作用。程序中也是如此，为了协调好数据输入和处理时机间的关系，采用类似于排队的机制是很方便的。在内存上，实现这种机制的方式就是队列。当我们需要处理通讯中发送的数据时，或由同时运行的多个程序所发送过来的数据时，会用到这种对队列中存储的不规则数据进行处理的方法。
队列一般是以环状缓冲区（ring buffer）的方式来实现的，也就是本章标题中所说的“熟练使用有棱有角的内存”。例如，假设我们要用有6个元素的数组来实现一个队列。这时可以从数组的起始位置开始有序地存储数据，然后再按照存储时的顺序把数据读出。在数组的末尾写入数据后，后一个数据就会被写入数组的起始位置（此时数据已经被读出所以该位置是空的）。这样，数组的末尾就和开头连接了起来，数据的写入和读出也就循环起来了（图4-9）。
图4-9 环状缓冲区的模型
酷客网相关文章：
评论前必须登录！
注册