数据结构 | 再也不怕被问栈跟队列了

墨蓝 2021-10-18 18:34 370阅读 0赞

> 在之前的文章中，我们已经学习过了数组，链表两种最为基础的数据结构，并且花了很大的精力去分析了链表的应用，到现在我们可以开始学习基于这两种数据结构之上的其他数据结构啦，这篇文章将主要介绍栈跟队列，加油！给自己，也给正在阅读本文的你！（[数据结构与算法|目录汇总][Link 1]）

### 文章目录 ###

*   *   *   *   *  栈：
                 *   *  概念：
                     *  栈的实现：
                 *  队列：
                 *   *  概念：
                     *  队列的实现：
                 *  为什么需要队列跟栈这些数据结构？

##### 栈： #####

###### 概念： ######

> 百度百科：
> 
> 栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

**简单来说，栈就是一种先进后出的数据结构**，图示如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTA3OTkx_size_16_color_FFFFFF_t_70]

###### 栈的实现： ######

1.  数组

package com.study.spring.transaction.stack;
    
    import lombok.Getter;
    import lombok.Setter;
    
    /** * @author dmz * @date Create in 23:44 2019/8/12 */
    @Getter
    @Setter
    public class ArrayStack<T> { 
    
        public ArrayStack(int size) { 
            this.size = size;
            this.array = new Object[size];
        }
    
        // 初始化的大小
        private int size;
    
        private Object[] array;
        // 下一次要放入的元素的位置
        private int currentIndex;
    
        public void push(T t) { 
            if (currentIndex == size) { 
                throw new RuntimeException("栈中元素已满");
            }
            array[currentIndex++] = t;
        }
    
        public T pop() { 
            if (currentIndex == 0) { 
                throw new RuntimeException("栈中已经没有元素啦");
            }
            Object o = array[--currentIndex];
            return (T) o;
        }
    }
    
    package com.study.spring.transaction.stack;
    
    /** * @author dmz * @date Create in 23:43 2019/8/12 */
    public class StackDemo { 
        public static void main(String[] args) { 
            ArrayStack<Integer> arrayStack = new ArrayStack<>(5);
            arrayStack.push(1);
            arrayStack.push(2);
            arrayStack.push(3);
            arrayStack.push(4);
            arrayStack.push(5);
            System.out.println(arrayStack.pop());
            System.out.println(arrayStack.pop());
            System.out.println(arrayStack.pop());
            System.out.println(arrayStack.pop());
            System.out.println(arrayStack.pop());
        }
    }

运行结果就不贴了，大家可以自行运行测试

1.  链表

package com.study.spring.transaction.stack;
    
    import lombok.Getter;
    import lombok.Setter;
    
    import java.util.LinkedList;
    
    /** * @author dmz * @date Create in 0:01 2019/8/13 */
    @Getter
    @Setter
    public class LinkStack<T> { 
        // 最大容量
        private int size;
        // 存储数据的链表
        private LinkedList<T> linkedList;
    
        public LinkStack(int size) { 
            this.size = size;
            this.linkedList = new LinkedList<T>();
        }
    
        public void push(T t) { 
            if (linkedList.size() < size) { 
                linkedList.add(t);
            } else { 
                throw new RuntimeException("栈中元素已满");
            }
        }
    
        public T pop() { 
            if (linkedList.size() == 0) { 
                throw new RuntimeException("栈中已经没有元素啦");
            }
            return linkedList.removeLast();
        }
    }

大家可以按照数组的方式自行测试。其实JDK中的LinkedList本身就已经实现了栈这种数据结构。大家可以直接查找LinkedList中的push以及pop方法

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTA3OTkx_size_16_color_FFFFFF_t_70 1]

##### 队列： #####

###### 概念： ######

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

**简单来说，队列就是一种先进先出的数据结构**，如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTA3OTkx_size_16_color_FFFFFF_t_70 2]

###### 队列的实现： ######

1.  数组

package com.study.spring.transaction.queue;
    
    import lombok.Data;
    
    /** * @author dmz * @date Create in 0:25 2019/8/13 */
    @Data
    public class ArrayQueue<T> { 
        private int size;
        private Object[] objects;
        // 下个加入的元素的下标
        private int currentIndex;
    
        public ArrayQueue(int size) { 
            this.size = size;
            currentIndex = size - 1;
            objects = new Object[size];
        }
    
        public void offer(T t) { 
            if (currentIndex < 0) { 
                throw new RuntimeException("队列中元素已满");
            }
            objects[currentIndex--] = t;
        }
    
        public T peek() { 
            if (0 == size) { 
                throw new RuntimeException("队列中已经没有元素啦");
            }
            return (T) objects[--size];
        }
    }
    
    /** * @author dmz * @date Create in 0:25 2019/8/13 */
    public class QueueDemo { 
        public static void main(String[] args) { 
            ArrayQueue<Integer> arrayQueue = new ArrayQueue<>(5);
            arrayQueue.offer(5);
            arrayQueue.offer(4);
            arrayQueue.offer(3);
            arrayQueue.offer(2);
            arrayQueue.offer(1);
            System.out.println(arrayQueue.peek());
            System.out.println(arrayQueue.peek());
            System.out.println(arrayQueue.peek());
            System.out.println(arrayQueue.peek());
            System.out.println(arrayQueue.peek());
            System.out.println(arrayQueue.peek());
        }
    }

1.  链表

package com.study.spring.transaction.queue;
    
    import lombok.Data;
    
    import java.util.LinkedList;
    
    /** * @author dmz * @date Create in 0:25 2019/8/13 */
    @Data
    public class LinkQueue<T> { 
        private int size;
        private LinkedList<T> linkedList;
    
        public LinkQueue(int size) { 
            this.size = size;
            linkedList = new LinkedList<>();
        }
    
        public void offer(T t) { 
            if (size == linkedList.size()) { 
                throw new RuntimeException("队列中元素已满");
            }
            linkedList.addLast(t);
        }
    
        public T peek() { 
            if (size == 0) { 
                throw new RuntimeException("队列中已经没有元素啦");
            }
            return linkedList.removeLast();
        }
    }

关于链表的实现我也不验证了，大家可以参考之前的示例进行验证。

##### 为什么需要队列跟栈这些数据结构？ #####

通过 上面的例子已经讲解不知道大家有没有这个疑惑？既然栈跟队列可以通过数组或链表实现，它们其实就是一个受限的数组或链表。相比于数组跟链表，栈跟队列这种数据结构带来的更多不过是限制罢了，那么为什么我们还需要它们呢？事实上，从功能上来看，数组跟链表确实能完全提代这两种数据结构，但是我们要知道的是，特点的数据结构是对特定场景的抽象，而且数组跟链表暴露了过多的操作接口，虽然操作上更加灵活，但是使用时就更加不可控，更容易出错。

码字不易，喜欢的话，加个关注，点个赞吧，万分感谢，你的支持就是我写作的最大动力！

[数据结构与算法|目录汇总][Link 1]

[Link 1]: https://blog.csdn.net/qq_41907991/article/details/98533954
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTA3OTkx_size_16_color_FFFFFF_t_70]: /images/20211018/466af55871364cd6b46e0b7a6c42d06c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTA3OTkx_size_16_color_FFFFFF_t_70 1]: /images/20211018/40b612183ddc47909dbd6e1f61239fa1.png
[Link 2]: https://baike.baidu.com/item/%E7%BA%BF%E6%80%A7%E8%A1%A8/3228081
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTA3OTkx_size_16_color_FFFFFF_t_70 2]: /images/20211018/57e4a0da6a074869857a52335d05e7cf.png