本文主要是介绍Java-数据结构-栈和队列-Stack和Queue (oﾟ▽ﾟ)o，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文本目录：
❄️一、栈(Stack)：
▶ 1、栈的概念：
▶ 2、栈的使用和自实现：
☑ 1）、Stack():
☑ 2）、push(E e):
☑ 3）、empty():
☑ 4）、peek(E e):
☑ 5）、pop(E e):
☑ 6）、size(E e):
▶ 3、栈自实现的总代码：
❄️二、队列(Queue)：
▶ 1、栈的概念：
▶ 2、队列的使用和自实现：
☑ 1）、Queue():
☑ 2）、isEmpty()：
☑ 3）、size()：
☑ 4）、offer(E e)：
☑ 5）、peek()：
☑ 6）、poll()：
▶ 3、队列的自实现的总代码：
❄️三、循环队列：
▶ 1、成员变量和初始化：
▶ 2、isEmpty()方法：
▶ 3、enQueue(int value)方法：、
▶ 3、isEmpty()方法：
▶ 4、deQueue()方法：
▶ 5、Front()方法：
▶ 6、Rear()方法：
❄️四、双端队列：
❄️五、总结：
❄️一、栈(Stack)：
▶ 1、栈的概念：
栈：是一种特殊的线性表，其 只允需在固定的一端进行插入和删除操作。
进行插入和删除的一端叫做栈顶，另一端叫做栈底。并且要遵循 先进后出 的规则。
压栈：栈的插入操作叫做压栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据在栈顶。
我们来看看图片是怎样进行的：
▶ 2、栈的使用和自实现：
我们来自实现一个栈，并且和 Java 自带的栈的方法进行比较，看看效果是否一样：
☑ 1）、Stack():
构造一个空的栈。
这也是对于 栈 的构造方法，我们先来看看Java 中自带的是什么效果并且看看如何使用的：
这就是Java自带的栈的构造方法。
我们接下来看看我们自己定义的栈是怎样写这个方法的，在写方法之前呢，我们先来把栈的成员变量来实现一下，我们对于栈呢，我们使用数组来存放数据：
我们来看看构造方法如何实现，这是个无参构造方法：
这个呢就是我们的自实现构造方法，我们来看看使用自实现的构造方法的效果：
所以效果是一样的。
☑ 2）、push(E e):
将 e 这个数据入栈。
我们同样先来看看Java 中自带的是什么效果并且看看如何使用的：
这就是 Java 里面自带的入栈操作。
我们来看看自实现的push，在编写代码之前，我们先来看看 push 的思路是什么：
我们的 push 呢，就是每次往数组下标指向的那个里面放数据，这个下标呢就是我们的 usedSize 这个下标，之后我们放入元素之后，我们要把 usedSize 这个长度往后加1。
但是这里插入元素的时候呢，我们要注意，当我们的数组的内存满了的话，我们是不是要2倍扩容，所以我们要注意这一点：
对于 push 方法呢就是这个意思了。 我们来看看代码是如何实现的：
我们来看看使用效果如何：
我们可以看到结果是一样的对于数据的存放。说明我们对于 push 这个方法是没有问题的。
☑ 3）、empty():
判断栈是否为空。
这个方法就非常简单了，我们之间来看看Java 的和自实现的比较是否结果一样：
当我们一开始创建栈的之后呢，判断栈是否为空的话，肯定是为空的所以返回 true 是正确的。由此可得我们的自定义的 empty() 代码是没有问题的。
☑ 4）、peek(E e):
返回栈顶的元素，但是不出栈顶的元素。
我们也是来看看如何实现的：
这个代码也是很简单的，我们至于要返回 usedSize-1 的这个下标的元素就可以了，因为我们的usedSize总是比下标长 1 个单位。
但是这里我们也是需要注意的是，我们需要先判断一下，我们的栈是否为空，如果为空，都没有元素，所以返回不了元素。这也是 为什么我要先写 empty 这个方法的原因。
我们先来看代码，之后再看看Java中的和自实现的有没有区别：
运行的比较： 
☑ 5）、pop(E e):
出栈顶的元素，并且把栈顶的元素删除。
这个呢，我们先把栈顶的元素打印出来，之后呢我们把 usedSize 自减一次，使得我们访问不到删除的元素，这个比较简单，我们直接来看看代码：
我们来看看实现代码的比较：
我们可以看到我们最先访问的 23 这个栈顶，这个方法是pop，所以会把栈顶元素删除，之后我们再用peek 方法访问的是12，所以呢这个删除方法 peek 没有问题。
☑ 6）、size(E e):
返回栈的长度。
这个方法是非常简单的，我们直接返回数组的有效的数组长度。我们直接看代码的实现吧：
▶ 3、栈自实现的总代码：
OK，我们呢对于栈的方法的实现现在常用的都自实现完事了，我们现在来看看总代码：
public class MyStack {public int[] elem;//存放栈的数据public int usedSize;//我们数组的有效长度public MyStack() {this.elem = new int[10];}private boolean isFull() {return usedSize == elem.length;}public void push(int e) {if (isFull()) {//二倍扩容this.elem = Arrays.copyOf(elem,2*elem.length);}//这是在放完元素后再自加elem[usedSize++] = e;}public boolean empty() {return usedSize == 0;}public int peek() {if (empty()) {System.out.println("栈为空没有元素");return -1;}return elem[usedSize - 1];}public int pop() {int e = peek();usedSize--;return e;}public int size() {return usedSize;}
}
OK，我们对于栈的实现就已经完事了，我们开看看一道关于栈的选择题来看看吧：
练习：
我们来看看这道题选什么？ 这道题呢，我们正确的呢是选择 C 因为C中呢我们出 3 后栈里的元素为2，1 从栈顶到栈底，所以我们不可能出1，在不先出2的情况下，所以C 是错误的。
你是否选择正确了呢？
❄️二、队列(Queue)：
在了解队列之前呢，我们请出我们的那个数据结构的那个表单：
我们要学习的 Queue 和我们之后要了解的 Deque 我们之前学习过的 LinkedList 这个类中都将它们实现了，所以呢我们的 LinkedList 类呢有 Queue 和 Deque 的性质。所以呢，LinkedList可以使链表、可以是队列(Queue)、可以是双端队列(Deque)。
▶ 1、栈的概念：
队列：是一种只允许一端进行插入元素，在另一端进行删除元素的特殊的线性表。
队列具有 先进先出 的性质：进行插入的一端叫做队尾，进行删除的一端叫做队头。也就是队尾进，队头出。
队列呢就相当于是我们 排队打饭 的例子，我们先来打饭的先走，后打饭的后走。
我们来看看流程的表：
相当于这样：
▶ 2、队列的使用和自实现：
☑ 1）、Queue():
这里我们创建队列的时候要注意了，我们的 队列只是一个接口，不是类，所以不能创建对象，所以我们需要使用 LinkedList 类来进行创建，进行向上转型。
我们来看看这个队列要如何创建：
这个就是用 LinkedList 来进行来创建 队列 的方法。
在我们自实现方法之前呢，我们来想一下，我们的队列使用什么结构来进行存储元素呢？
我们在之前呢，我们了解到了 顺序存储 和 链式存储 两种方式，对于我们队列呢我们使用 链式存储 的方式来进行存储元素，但是我们 链式存储 有 单链表 和 双链表 两种方式，我们呢最好使用 双链表 的形式，这样呢方便我们 存储和删除，而且我们的队列要有头和尾，所以双链表更加的合适。这样呢我们了解队列怎样存储之后，我们来看看自实现队列：
☑ 2）、isEmpty()：
判断队列是否为空。
这个方法是非常简单的，我们只需要判断 队头 是不是空就可以了，或者我们判断一下有效长度是不是 0 也是可以判断的，因为我们每次出元素都在队头，当我们的头为空说明没有元素了。我们来看看代码：
这个呢，我们就不进行演示了，我们直接继续往下看：
☑ 3）、size()：
返回队列的长度。
我们再来看一个简单的代码，这个代码就非常简单了，我们不是定义了一个 usedSize 这个成员变量了吗，这个就是我们队列的有效长度，所以我们直接返回这个 usedSize 这个成员变量就可以了，我们来看看代码的实现：
是不是很简单呢，所以我们这个也不进行代码的演示了，我们还是继续往下看：
☑ 4）、offer(E e)：
入队列操作。
对于入队的之前呢，我们要先进行对队列的判断，如果我们的队列是空的话，我们要把我们的要入队的节点newNode，我们要执行 firast = last = newNode 的操作。
第一步，当我们的队列不为空的时候呢，我们要把 last.next 指向 newNode 这个节点。
第二步，我们把新的节点 newNode.prev 指向我们的last这个节点，
第三步，把 last 往后移一位。
这个呢，就是我们入队的操作思路啦，之后我们，来看看代码是如何实现的： 
这个呢就是我们的入队操作了，我们来看看 Java 中的队列和自实现的队列的 入队 操作有没有不同的。 
我们可以看到，我们的自实现是没有问题的。Ok，我们来看下一个 队列 的操作：
☑ 5）、peek()：
获得队头的元素
对于这个方法呢，是非常的简单的，我们想要队头的元素的话，我们只需要返回 first.val 这个数据就可以了：
比如这个呢，我们的队头元素就是 first.val 这个元素 ，所以我们来看看代码：
看一下运行的结果怎么样：
OK，我们可以看到这个方法是没有问题的，我们接下来看看 队列 的最后一个常用的方法：
☑ 6）、poll()：
出队列操作。
我们对于出队列之前呢，我们要先把队列判断一下是否为空，之后我们才能进行出队操作。
对于出队操作呢，我们是出队头的元素，我们呢要先把队头元素出出来，之后我们在把 first 往后移动一位，是我们出的那个元素，在队列中删除。但是呢，如果我们的 first 不是空的话，我们呢要把 first.prev 赋值为null，因为我们要把前一个节点删除，所以呢，我们要置空。
我们来看看方法的思路：
了解思路之后呢，我们来看看代码如何编写的：
我们来看看代码有没有问题：
我们可以看到当我们的 poll 执行之后呢，我们的 peek 的元素就变了，说明我们已经出队了，所以没有问题。
▶ 3、队列的自实现的总代码：
public class MyQueue {static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode first;//队头public ListNode last;//队尾public int usedSize;//长度public boolean isEmpty() {return first == null;//return usedSize == 0;}public int size() {return usedSize;}public void offer(int val) {ListNode newNode = new ListNode(val);if (isEmpty()) {first = last = newNode;}else {last.next = newNode;newNode.prev = last;last = last.next;}usedSize++;}public int poll() {if (isEmpty()) {return -1;}int val = first.val;first = first.next;if (first != null) {first.prev = null;}usedSize--;return val;}public int peek() {if (isEmpty()) {return -1;}return first.val;}
}我们的队列呢就到这里就结束了，接下来我们来看一个特殊的队列——循环队列。
❄️三、循环队列：
我们呢，先来了解一下循环队列长什么样的，是怎样进行循环的，我们来看看循环队列的形状：
这个呢就是我们的循环队列了，它就像一个轮子一样，是一个环状的。就相当于我们把数组给卷起来似得。
当这个队列是空的时候呢，我们的 front 和 rear 是在同一个位置，就是相等。
那么我们接下来看看这个的存储过程，并且当什么时候呢我们才能知道我们的空间是满的呢？
我们一个一个来解决：
这样存放元素呢，我们满的话呢·，front 和 rear 是在一个位置上，但是我们在一个位置上的时候呢，我们是用来判断是否是空的情况下，所以呢，判满是不能这样判断的，那么我们用什么办法呢？我们呢，有三种方法来判断循环队列是否是满的：
1、定义size来判断
当我们的队列的长度和size的长度相等的时候呢，我们就是满的。
2、添加标记，用boolean来判断
每当我们放元素的时候呢，我们把那个位置标记为 true 没有元素为 false，来判断是否满
3、保留一个位置，浪费一个空间来进行判断
就是当 rear 的下一个位置为 front 的时候呢，我们就是满的。比如这样：
我们呢要如何才能判断 rear 的下一个是 front 呢？ 是不是想到的是 rear + 1 = front 就可以了呢？
这个呢还是有点小瑕疵的，当我们的 rear 是 0 的时候我们的 front 为 1 的时候这种的是可以判断的，像这样：
但是呢当我们的 rear 为 7 ，front 为 0 的时候就不对了，rear + 1 = 8 ≠ front ，那么我们要如何才能判断呢，我们呢这时候就有了一个公式：
比如我们 7 和 0 就是这样：(7 + 1) % 8 = 0
这个队列呢，也是一道题，我们来看链接：
循环队列
▶ 1、成员变量和初始化：
正确的代码：
▶ 2、isEmpty()方法：
判断是否是满的
这里我们直接用公式：
▶ 3、enQueue(int value)方法：、
入队操作
这里呢，我们就是直接往 rear 下标进行放入元素，之后 rear 进行增加，但是这里我们不能使用rear++ 来进行增加，因为当我们的 rear 为7时候呢，不能++，那样就为8了，所以这里我们也要用公式来写：
▶ 3、isEmpty()方法：
判断队列是否为空
这个比较简单，我们直接判断 rear 是否等于 front 就可以了。
▶ 4、deQueue()方法：
出队操作
对于这个方法，我们只需要把 front 这个下标往后走就可以了，虽然我们没有删除元素，但是当我们再次在那个位置添加元素的时候，会把原先的数据覆盖掉，但是这里我们的 front 的移动也需要使用公式来移动。来看代码：
▶ 5、Front()方法：
得到队头元素
这个呢，我们直接返回 front 下标的元素即可 。
▶ 6、Rear()方法：
得到队尾元素。
这个方法呢，我们在对于队尾的位置判断上要麻烦一些，当我们 rear 在0下标的时候，队尾下标为7，但是呢，我们在 rear -1 的时候，和结果不一致，这里呢我们要判断，当 rear=0 的时候，我们的队尾下标为 elem.length- 1，其余时为 rear-1，我们来看代码：
我们的循环队列就到这里就结束了，我们再来看一种特殊的队列，叫——双端队列(Deque)。
❄️四、双端队列：
这个队列呢，我们不进行详细的讲解，我们了解一下其工作原理的图和其构造方法即可。和我们学习的队列差不多，只是增加了 头尾都可以进出 ：
之后我们来看一下其接口是实现：
❄️五、总结：
OK，这次的关于呢 线性表中的 栈和队列 就都介绍完毕了，下次呢我们来练习一下它们的习题，这次就到这里就结束了，让我们期待下次的分享吧！！！拜拜~~~
这篇关于Java-数据结构-栈和队列-Stack和Queue (oﾟ▽ﾟ)o的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
