97. 一网打尽面试中常被问及的8种数据结构（二）
3.堆栈
堆栈是一种LIFO（后进先出-最后放置的元素可以首先访问）结构，该结构通常在许多编程语言中都可以找到。该结构被称为"堆栈"，因为它类似于真实世界的堆栈-板的堆栈。
Image Source: pixabay
堆栈操作
下面给出了可以在堆栈上执行的2个基本操作。请参考图3，以更好地了解堆栈操作。
- Push 推送：在堆栈顶部插入一个元素。
- Pop 弹出：删除最上面的元素并返回。
Fig 3. Visualization of basic Operations of Stacks
此外，为堆栈提供了以下附加功能，以检查其状态。
- Peep 窥视：返回堆栈的顶部元素而不删除它。
- isEmpty：检查堆栈是否为空。
- isFull：检查堆栈是否已满。
堆栈的应用
- 用于表达式评估（例如：用于解析和评估数学表达式的调车场算法）。
- 用于在递归编程中实现函数调用。
4.队列
队列是一种FIFO（先进先出-首先放置的元素可以首先访问）结构，该结构通常在许多编程语言中都可以找到。该结构被称为"队列"，因为它类似于现实世界中的队列-人们在队列中等待。
Image Source: pixabay
队列操作
下面给出了可以在队列上执行的2个基本操作。请参考图4，以更好地了解堆栈操作。
- 进队：将元素插入队列的末尾。
- 出队：从队列的开头删除元素。
Fig 4. Visualization of Basic Operations of Queues
队列的应用
- 用于管理多线程中的线程。
- 用于实施排队系统（例如：优先级队列）。
5.哈希表
哈希表是一种数据结构，用于存储具有与每个键相关联的键的值。此外，如果我们知道与值关联的键，则它有效地支持查找。因此，无论数据大小如何，插入和搜索都非常有效。
当存储在表中时，直接寻址使用值和键之间的一对一映射。但是，当存在大量键值对时，此方法存在问题。该表将具有很多记录，并且非常庞大，考虑到典型计算机上的可用内存，该表可能不切实际甚至无法存储。为避免此问题，我们使用哈希表。
哈希函数
名为哈希函数（h）的特殊函数用于克服直接寻址中的上述问题。
在直接访问中，带有密钥k的值存储在插槽k中。使用哈希函数，我们可以计算出每个值都指向的表（插槽）的索引。使用给定键的哈希函数计算的值称为哈希值，它表示该值映射到的表的索引。
h：哈希函数
k：应确定其哈希值的键
m：哈希表的大小（可用插槽数）。一个不接近2的精确乘方的素数是m的一个不错的选择。
Fig 5. Representation of a Hash Function
- 1→1→1
- 5→5→5
- 23→23→3
- 63→63→3
从上面给出的最后两个示例中，我们可以看到，当哈希函数为多个键生成相同的索引时，就会发生冲突。我们可以通过选择合适的哈希函数h并使用链接和开放式寻址等技术来解决冲突。
