目录 1、理解栈与队列 2、用代码谈谈栈 3、用代码谈谈队列 我们今天主要来谈谈“栈”以及队列这两种数据结构。 回顾一下上一章中【数据结构01】数组中，在数组中只要知道数据的下标，便可通过顺序搜索很快查询到数据，可以根据下标不同自由查找，然而今天要讲的“栈”以及队列这两种数据结构访问是受限制的，只允许在一端读取、插入和删除数据，这时候对它存在的意义产生了很大的疑惑。因为会觉得，相比数组和链表，栈带给我的只有限制，并没有任何优势。那我直接使用数组或者链表不就好了吗？为什么还要用这个“操作受限”的“栈”呢？事实上，从功能上来说，数组或链表确实可以替代栈，但你要知道，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。 @ 1、理解栈与队列 首先，如何理解“栈”？用现实一个通俗贴切的例子，我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们是从上往下一个一个地依次取，不能从中间任意抽出，先进后出，这就是典型的“栈”结构,当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。 其次如何理解队列？同样用现实一个通俗贴切的例子，平时在校的时候饭堂吃饭都是排队，而且不能插队，先进先出，这就是典型的队列结构 2、用代码谈谈栈 实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。不管是顺序栈还是链式栈，我们存储数据只需要一个大小为n的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是O(1)。 注意，这里存储数据需要一个大小为n的数组，并不是说空间复杂度就是O(n)。因为，这n个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。 空间复杂度分析是不是很简单？时间复杂度也不难。不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是O(1)。 还有一点，JVM内存管理中有个“堆栈”的概念。栈内存用来存储局部变量和方法调用，堆内存用来存储Java中的对象。那JVM里面的“栈”跟我们这里说的“栈”是不是一回事呢？如果不是，那它为什么又叫作“栈”呢？知道的大牛请自觉评论区见面~在这里插入图片描述 2.1、用数组实现的栈：顺序栈 public class MyStack { //栈的底层我们使用数组来存储数据 int[] elements; public MyStack() { elements = new int[0]; } //压入元素 public void push(int element) { // 创建一个新的数组 int[] newArr = new int[elements.length + 1]; // 把原数组中的元素复制到新数组中 for (int i = 0; i < elements.length; i++) { newArr[i] = elements[i]; } // 把添加的元素放入新数组中 newArr[elements.length] = element; // 使用新数组替换旧数组 elements = newArr; } //取出栈顶元素 public int pop() { //栈中没有元素 if(elements.length==0) { throw new RuntimeException("stack is empty"); } //取出数组的最后一个元素 int element = elements[elements.length-1]; //创建一个新的数组 int[] newArr = new int[elements.length-1]; //原数组中除了最后一个元素的其它元素都放入新的数组中 for(int i=0;i