栈和队列

秒速五厘米 2023-07-14 15:57 257阅读 0赞

> ***栈** *是限定 ***仅在表尾 ***进行***插入和删除操作***的线性表
> 
> ***队列 ***是只允许 ***在一端 ***进行 ***插入 ***操作、而在 ***另一端 ***进行 ***删除 ***操作的线性表

## ##

### 第一部分 相关定义  ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70][]

如果使用数组实现，下表从0开始

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 1][]

队列的顺序存储：出队复杂度高O(n), 容易假溢出

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 2][]

中缀运算符转为后缀表达式

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 3][]

后缀表达式通过栈实现，数字直接显示，符号入栈

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 4][]

### 第二部分 简单的源码阅读 ###

stack 栈 和 queue 队列并没有自己的实现逻辑，相关的实现可以查看链表的具体实现，查看[链表的源码阅读][Link 1]

1）stack 相关方法

push操作，添加元素

public E push(E item) {
            addElement(item);
    
            return item;
        }

pop 添加***查询并删除***栈中的元素 ，其中peek为获取元素操作

public synchronized E pop() {
            E       obj;
            int     len = size();
    
            obj = peek();
            removeElementAt(len - 1);
    
            return obj;
        }

search 为查询元素

public synchronized int search(Object o) {
            int i = lastIndexOf(o);
    
            if (i >= 0) {
                return size() - i;
            }
            return -1;
        }

2）queue 队列相关方法

>     public interface Queue<E> extends Collection<E>

boolean add(E e);
    
        boolean offer(E e);
    
        E remove();
    
        E poll();
    
        E element();
    
        E peek();

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70]: /images/20230529/e48238db6fb844ac97843e908c90d473.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 1]: /images/20230529/1703fa9428ad43699c13e2b6039637a3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 2]: /images/20230529/7b7078231b81411296e5597a130f5094.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 3]: /images/20230529/eafbcc36aeef4b8b88b9d3392ed2af89.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 4]: /images/20230529/d08f547184fc4fd3ab66cd9af37edae8.png
[Link 1]: https://blog.csdn.net/qq_35275233/article/details/104865017