内容

• 比较表
• 堆栈的定义
• 例
• 队列的定义
• 例
• 堆栈实施
• 队列实施
• 堆栈操作
• 队列中的操作
• 堆栈的应用
• 队列的应用
• 结论

堆栈和队列都是非原始数据结构。堆栈和队列之间的主要区别在于，堆栈使用LIFO（先进先出）方法访问和添加数据元素，而队列使用FIFO（先进先出）方法访问和添加数据元素。

堆栈只有一个开放的一端可以推送和弹出数据元素，另一方面，队列的开放的两端都可以让数据元素入队和出队。

堆栈和队列是用于存储数据元素的数据结构，实际上是基于某些实际的等效项。例如，堆栈是CD的堆栈，您可以在其中取出CD并将其放入CD堆栈的顶部。类似地，该队列是剧院门票的队列，其中首先站在第一位的人，即队列的前面，而新到达的人将出现在队列的后面（队列的后端）。

1. 比较表
2. 定义
3. 关键差异
4. 实作
5. 运作方式
6. 应用领域
7. 结论

比较表

比较依据	堆	队列
工作原则	LIFO（后进先出）	FIFO（先进先出）
结构体	同一端用于插入和删除元素。	一端用于插入，即后端，而另一端用于删除元素，即前端。
使用的指针数	一	两个（在简单队列中）
执行的操作	推和弹出	入队和出队
空状态检查	上== -1	前== -1 ||前==后+ 1
全面检查	顶端==最大值-1	后方==最大值-1
变体	它没有变体。	它具有诸如循环队列，优先级队列，双端队列的变体。
实作	更简单	比较复杂

堆栈的定义

堆栈是非原始线性数据结构。它是一个有序列表，其中添加了新项，而仅从一端删除了现有元素，称为栈顶（TOS）。由于堆栈中所有删除和插入操作都是从堆栈顶部完成的，因此最后添加的元素将是第一个要从堆栈​​中删除的元素。这就是为什么堆栈被称为后进先出（LIFO）类型的列表的原因。

请注意，经常在堆栈中访问的元素是最顶层的元素，而最后一个可用的元素在堆栈的底部。

例

你们中有些人可能会吃饼干（或波平饼干）。如果您认为的话，盖子的只有一侧被撕裂，饼干被一一取出。这就是所谓的爆裂，类似地，如果您想在以后保留一些饼干，则可以通过相同的撕裂末端将它们放回包装中，这称为推入。

队列的定义

队列是非原始类型类别中的线性数据结构。它是相似类型元素的集合。新元素的添加发生在称为后端的一端。同样，删除现有元素的另一端称为“前端”，从逻辑上讲，它是列表的先进先出（FIFO）类型。

例

在我们的日常生活中，我们遇到了许多情况，我们要等待所需的服务，因此必须进入排队等待服务。可以将这个等待队列视为一个队列。

1. 另一方面，堆栈遵循LIFO机制，队列遵循FIFO机制以添加和删除元素。
2. 在堆栈中，同一端用于插入和删除元素。相反，队列中使用了两个不同的末端来插入和删除元素。
3. 由于堆栈只有一个开放端，这就是仅使用一个指针来引用堆栈顶部的原因。但是队列使用两个指针来引用队列的前端和后端。
4. 堆栈执行称为推入和弹出的两个操作，而在队列中称为入队和出队。
5. 堆栈实现比较容易，而队列实现则比较棘手。
6. 队列具有变体，例如循环队列，优先级队列，双端队列等。相比之下，堆栈没有变体。

堆栈实施

堆栈可以两种方式应用：

1. 静态实现 使用数组创建堆栈。静态实现虽然是一种轻松的技术，但却不是灵活的创建方式，因为必须在程序设计期间声明堆栈的大小，之后才能更改大小。另外，静态实现在内存利用率方面不是很有效。由于数组（用于实现堆栈）是在操作开始之前（在程序设计时）声明的。现在，如果堆栈中要排序的元素数量非常少，那么静态分配的内存将被浪费。另一方面，如果要在堆栈中存储更多元素，那么我们将无法更改数组的大小以增加其容量，从而无法容纳新元素。
2. 动态实施 也称为链表表示形式，并使用指针来实现数据结构的堆栈类型。

队列实施

队列可以通过两种方式实现：

1. 静态实现注意：如果使用数组实现队列，则必须事先确保要存储在队列中的元素的确切数量，因为必须在设计时或处理开始之前声明数组的大小。在这种情况下，数组的开始将成为队列的前面，而数组的最后一个位置将作为队列的后面。以下关系给出了使用数组实现时队列中存在的所有元素：
   前–后+ 1
   如果“ rear <front”，则队列中将没有元素，或者队列将始终为空。
2. 动态实施：使用指针实现队列，主要缺点是链接表示形式中的节点比数组表示形式中的相应元素消耗更多的内存空间。由于每个节点中至少有两个字段，一个用于数据字段，另一个用于存储下一个节点的地址，而在链接表示中，仅数据字段存在。当需要在一组其他元素的中间插入或删除一个元素时，使用链接表示形式的优点就显而易见。

堆栈操作

可以在堆栈上进行的基本操作如下：

1. 推：将新元素添加到堆栈顶部时，称为PUSH操作。将元素压入堆栈会调用该元素的添加，因为新元素将插入到顶部。每次按下操作后，顶部都会增加一个。如果阵列已满，并且无法添加任何新元素，则称为“堆满”条件或“堆满”。按钮操作– C语言中的功能：
   考虑栈被声明为
   int stack，top = -1;
无效push（）
{
int项目；
如果（前<4）
{
f（“输入号码”）；
扫描（“％d”和项目）；
顶部=顶部+ 1;
堆栈=项目;
}
其他
{
f（“堆栈已满”）；
}
}
2. 流行音乐：从堆栈顶部删除元素时，这称为POP操作。每次弹出操作后，堆栈减少一。如果堆栈上没有剩余元素并且执行了弹出操作，则将导致STACK UNDERFLOW状态，这意味着您的堆栈为空。 POP操作-C语言中的功能：
   考虑栈被声明为
   int stack，top = -1;
无效pop（）
{
int项目；
如果（顶部> = 4）
{
项目=堆栈;
顶部=顶部-1;
f（“删除的数字是=％d”，项目）；
}
其他
{
f（“堆栈为空”）；
}
}

队列中的操作

可以在队列上执行的基本操作是：

1. 入队：在队列中插入元素。在C中使操作函数排队：
   队列声明为
   int队列，前= -1，后= -1；
无效添加（）
{
int项目；
如果（后<4）
{
f（“输入号码”）；
扫描（“％d”和项目）；
如果（前== -1）
{
前= 0;
后= 0;
}
其他
{
后=后+1
}
队列=项目;
}
其他
{
f（“队列已满”）；
}
}

2. 出队：从队列中删除元素。在C中使操作函数排队：
   队列声明为
   int队列，前= -1，后= -1；
无效删除（）
{
int项目；
如果（前面！= -1）
{
项目=队列;
如果（前==后）
{
前= -1;
后方= -1;
}
其他
{
前=前+ 1;
f（“删除的数字是=％d”，项目）；
}
}
其他
{
f（“队列为空”）；
}
}

堆栈的应用

• 在编译器中解析。
• Java虚拟机。
• 在文字处理器中撤消。
• Web浏览器中的“后退”按钮。
• 面向用户的PostScript语言。
• 在编译器中实现函数调用。

队列的应用

• 数据缓冲区
• 异步数据传输（文件IO，管道，套接字）。
• 在共享资源（er，处理器）上分配请求。
• 流量分析。
• 确定在超市拥有收银员的数量。

结论

堆栈和队列是线性数据结构，在某些方面有所不同，例如工作机制，结构，实现，变体，但两者都用于在列表中存储元素并在列表上执行操作，例如元素的添加和删除。尽管简单队列有一些限制，但可以通过使用其他类型的队列来弥补。