栈和队列的存储方式（栈和队列的存储方式）

本文目录

• 栈和队列的存储方式
• 程序中的栈和队列是什么意思
• 简述栈和队列的顺序存储结构和链式存储结构的优缺点
• 栈与队列的区别
• 堆栈和队列 的本质区别
• 线性表、栈、队列有何异同

栈和队列的存储方式

栈和队列都是在一个特定范围的存储单元中存储的数据，这些数据都可以重新被取出使用。不同的是，栈就象一个很窄的桶先存进去的数据只能最后才能取出来，而且队列则不一样，即“先进后出”。队列有点象日常排队买东西的人的“队列”先牌队的人先买，后排队的人后买，即“先进先出”。有时在数据结构中还有可能出现按照大小排队或按照一定条件排队的数据队列，这时的队列属于特殊队列，就不一定按照“先进先出”的原则读取数据了。

程序中的栈和队列是什么意思

栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表(LastInFirstOut)。通常栈有顺序栈和链栈两种存储结构。栈的基本运算有六种：·构造空栈：InitStack(S)·判栈空:StackEmpty(S)·判栈满：StackFull(S)·进栈：Push(S,x)·退栈：Pop(S)·取栈顶元素：StackTop(S)在顺序栈中有“上溢“和“下溢“的现象。·“上溢“是栈顶指针指出栈的外面是出错状态。·“下溢“可以表示栈为空栈,因此用来作为控制转移的条件。顺序栈中的基本操作有六种：·构造空栈·判栈空·判栈满·进栈·退栈·取栈顶元素链栈则没有上溢的限制，因此进栈不要判栈满。链栈不需要在头部附加头结点，只要有链表的头指针就可以了。链栈中的基本操作有五种：·构造空栈·判栈空·进栈·退栈·取栈顶元素队列(Queue)是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear),队列的操作原则是先进先出的，又称作FIFO表(FirstInFirstOut)。队列也有顺序存储和链式存储两种存储结构。队列的基本运算有六种：·置空队：InitQueue(Q)·判队空：QueueEmpty(Q)·判队满：QueueFull(Q)·入队：EnQueue(Q,x)·出队：DeQueue(Q)·取队头元素：QueueFront(Q)顺序队列的“假上溢“现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了“上溢“现象。为了克服“假上溢“现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。判定循环队列是空还是满，方法有三种：·一种是另设一个布尔变量来判断；·第二种是少用一个元素空间，入队时先测试（(rear+1)%m=front）?满：空；·第三种就是用一个计数器记录队列中的元素的总数。队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入(入队)的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。

简述栈和队列的顺序存储结构和链式存储结构的优缺点

顺序栈--入栈操作受数组上界的约束有可能发生栈上溢，且需要地址连续的存储单元。链栈--无须地址连续，便于多个栈共享存储单元，且不存在栈满上溢情况。顺序队列--需地址连续且有假上溢现象（需改为循环队列才可解决假上溢）链式队列--特别适合于数据元素变动比较大的情况，且不存在队列满而产生的溢出问题。

栈与队列的区别

1、队列先进先出，栈先进后出。

2、对插入和删除操作的“限定“不同。

栈是限定只能在表的一端进行插入和删除操作的线性表。     

队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。  

3、遍历数据速度不同。

栈只能从头部取数据，也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性。

队列则不同，它基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像数据结构，速度要快的多

扩展资料

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。

向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

参考资料来源：百度百科—队列 （常用数据结构之一）

参考资料来源：百度百科—栈 （计算机术语）

堆栈和队列 的本质区别

队列和栈是两种不同的数据结构。它们有以下本质区别：

1、操作的名称不同。

队列的插入称为入队，队列的删除称为出队。栈的插入称为进栈，栈的删除称为出栈。

2、操作的限定不同。

队列是在队尾入队，队头出队，即两边都可操作。而栈的进栈和出栈都是在栈顶进行的，无法对栈底直接进行操作。

3、操作的规则不同。

队列是先进先出（FIFO），即队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（不能从中间插入），每次离开的成员总是队列头上（不允许中途离队）。

而栈为后进先出（LIFO）,即每次删除（出栈）的总是当前栈中最新的元素，即最后插入（进栈）的元素，而最先插入的被放在栈的底部，要到最后才能删除。

4、遍历数据速度不同。

队列是基于地址指针进行遍历，而且可以从头部或者尾部进行遍历，但不能同时遍历，无需开辟空间，因为在遍历的过程中不影响数据结构，所以遍历速度要快。

栈是只能从顶部取数据，也就是说最先进入栈底的，需要遍历整个栈才能取出来，而且在遍历数据的同时需要为数据开辟临时空间，保持数据在遍历前的一致性。

扩展资料：

1、堆栈的储存方式：

堆栈是一个特定的存储区或寄存器，它的一端是固定的，另一端是浮动的   。对这个存储区存入的数据，是一种特殊的数据结构。

所有的数据存入或取出，只能在浮动的一端（称栈顶）进行，严格按照“先进后出”的原则存取，位于其中间的元素，必须在其栈上部（后进栈者）诸元素逐个移出后才能取出。

在内存储器（随机存储器）中开辟一个区域作为堆栈，叫软件堆栈；用寄存器构成的堆栈，叫硬件堆栈。

单片机应用中，堆栈是个特殊存储区，堆栈属于RAM空间的一部分，堆栈用于函数调用、中断切换时保存和恢复现场数据。

堆栈中的物体具有一个特性：第一个放入堆栈中的物体总是被最后拿出来， 这个特性通常称为先进后出 (FILO—First-In/Last-Out)。 

堆栈中定义了一些操作， 两个最重要的是PUSH和POP。 PUSH（入栈）操作：堆栈指针（SP）加1，然后在堆栈的顶部加入一 个元素。

POP（出栈）操作相反，出栈则先将SP所指示的内部ram单元中内容送入直接地址寻址的单元中（目的位置），然后再将堆栈指针（SP）减1。这两种操作实现了数据项的插入和删除。

2、队列的储存方式：

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。

进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。

因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

参考资料来源：百度百科—堆栈

参考资料来源：百度百科—队列

线性表、栈、队列有何异同

相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。

不同点：

1、运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。

2、用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。

扩展资料：

顺序堆栈—堆栈的顺序存储结构：

栈属于一种特殊的线性表，它支持推栈和推栈空满等基本操作。您可以使用数组来模拟具有顶值的堆栈，以完成上述基本操作。

双栈共享空间（双端栈）：

如果您需要在程序中使用两个具有相同数据类型的堆栈，您可以通过数组模拟为这两个堆栈创建共享空间，称为双向堆栈。两栈共享空间：一个数组用于存储两个堆栈，一个堆栈的底部作为数组的开始，另一个堆栈的底部作为数组的结束，两个堆栈从各自的端点延伸到中间。