队列和栈的异同

亦凉 2022-05-21 04:56 130阅读 0赞

## 1. 队列先进先出，栈先进后出 ##

## 2. 接口实现的异同 ##

队列和栈同属于Java合集框架，由Collcetion接口实现，队列由Queue接口实现，栈由List接口实现，

## 3. 逻辑结构和存储结构的的异同 ##

他们的逻辑结构同为线性结构，存储结构为顺序存储结构或者链式存储结构

## 4. 方法的异同 ##

他们同时含有绝大部分Collection接口中声明的方法，但同时两者各有扩展的方法，队列提供了四个操作头节点的方法

> <interface>  
> java.util.Queue

offer(element: E): boolean     插入一个元素到队列中
    poll(): E                      获取并移除队列的头元素，如果队列空则返回null
    remove(): E                    获取并移除队列头元素，如果队列空则抛出异常
    peek(): E                      获取但不移除队列头元素，如果队列为空则返回null
    element(): E                   获取但不移除队列头元素，如果队列为空则抛出异常

栈提供了对栈顶元素的操作以及在栈内搜索的方法

> java.util.Vector<E>

empty(): boolean               如果栈为空则返回真
    peek(): E                      返回栈中的顶部元素
    pop(): E                       返回并移除该栈中的顶部元素
    push(o: E): E                  增加一个新的元素到栈的顶部
    search(o: Object): int         返回该栈中指定元素的位置

## 5. 对插入和删除操作的"限定" ##

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

## 6. 遍历数据速度的异同 ##

栈只能从头部取数据，也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前后的一致性。  
队列基于地址指针进行遍历，而且可以从头或尾部开始遍历，无需开辟临时空间，速度要快的多。

## 7. 应用场景的异同 ##

常见栈的应用场景包括括号问题的求解，表达式的转换和求值，函数调用和递归实现，深度优先搜索遍历等。  
常见的队列的应用场景包括计算机系统中各种资源的管理，消息缓冲器的管理和广度优先搜索遍历等。