栈和队列没想象中那么难
# 一、前言
之前已经讲过链表了,它跟数组都是线性结构的基础,本文主要讲解线性结构的应用:**栈**和**队列**
如果写错的地方希望大家能够多多体谅并指正哦,如果有更好的理解的方式也希望能够在评论下留言,让大家学习学习~
# 二、数据结构【栈】就是这么简单
## 2.1数据结构【栈】介绍
数据结构的栈长的是这个样子:
![image](https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/ff7ab24f58d54ab38b52c6893c750233~tplv-k3u1fbpfcp-zoom-1.image)
其实非常好理解,我们将栈可以**看成一个箱子**
* 往箱子里面放东西叫做入栈
* 往箱子里面取东西叫做出栈
* 箱子的底部叫做栈底
* 箱子的顶部叫做栈顶
说到栈的特性,肯定会有一句经典的言语来概括:**先进后出(LIFO, Last In First Out)**
* 往箱子里边放苹果,箱子底部的苹果想要拿出来,得先把箱子顶部的苹果取走才行
## 2.2数据结构【栈】 代码实现
栈的分类有两种:
* 静态栈(数组实现)
* **动态栈(链表实现)**
从上一篇写链表我就认知到我的算法是有多渣了,普通的单链表操作也能把我绕得晕晕的。
由于我的链表还不是很熟,栈又不是很难,那么我就用链表来创建动态栈了!
既然是用链表,我们还是把上一篇节点的代码拿过来吧:
```
public class Node {
//数据域
public int data;
//指针域,指向下一个节点
public Node next;
public Node() {
}
public Node(int data) {
this.data = data;
}
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
```
要链表用来表示栈,这次会有两个指针:
* 栈顶
* 栈底
```
public class Stack {
public Node stackTop;
public Node stackBottom;
public Stack(Node stackTop, Node stackBottom) {
this.stackTop = stackTop;
this.stackBottom = stackBottom;
}
public Stack() {
}
}
```
### 2.2.1进栈
**将原本栈顶指向的节点交由新节点来指向,栈顶指向新加入的节点**
```
/**
* 进栈
*
* @param stack 栈
* @param value 要进栈的元素
*/
public static void pushStack(Stack stack, int value) {
// 封装数据成节点
Node newNode = new Node(value);
// 栈顶本来指向的节点交由新节点来指向
newNode.next = stack.stackTop;
// 栈顶指针指向新节点
stack.stackTop = newNode;
}
```
### 2.2.2遍历栈
**只要栈顶元素的指针不指向栈底**,那么就一直输出遍历结果:
```
/**
* 遍历栈(只要栈顶指针不指向栈底指针,就一直输出)
*
* @param stack
*/
public static void traverse(Stack stack) {
Node stackTop = stack.stackTop;
while (stackTop != stack.stackBottom) {
System.out.println("关注公众号:Java3y:" + stackTop.data);
stackTop = stackTop.next;
}
}
```
测试:
```
public static void main(String[] args) {
//初始化栈(无元素)
Stack stack = new Stack(new Node(), new Node());
//栈顶和栈尾是同一指向
stack.stackBottom = stack.stackTop;
//指向null
stack.stackTop.next = null;
//进栈
pushStack(stack, 3);
pushStack(stack, 4);
pushStack(stack, 5);
traverse(stack);
}
```
结果:
![1.jpg](https://p1-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/b0b686477ea24e29b23165fdee27b87f~tplv-k3u1fbpfcp-watermark.image)
这就符合了先进后出的特性了~
### 2.2.3判断该栈是否为空
很简单,只要栈顶和栈底是同一指向,那么该栈就为空
```
/**
* 判断该栈是否为空
*
* @param stack
*/
public static void isEmpty(Stack stack) {
if (stack.stackTop == stack.stackBottom) {
System.out.println("关注公众号:Java3y---->该栈为空");
} else {
System.out.println("关注公众号:Java3y---->该栈不为空");
}
}
```
### 2.2.4出栈
1. 在出栈之前看看该栈是否为空,不为空才出栈...
2. 将栈顶的元素的指针(指向下一个节点)赋值给栈顶指针(完成出栈)
```
/**
* 出栈(将栈顶的指针指向下一个节点)
* @param stack
*/
public static void popStack(Stack stack) {
// 栈不为空才能出栈
if (!isEmpty(stack)) {
//栈顶元素
Node top = stack.stackTop;
// 栈顶指针指向下一个节点
stack.stackTop = top.next;
System.out.println("关注公众号:Java3y---->出栈的元素是:" + top.data);
}
}
```
测试出栈:
![2.jpg](https://p9-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/2661c737940c4fa992c3d194d80fc630~tplv-k3u1fbpfcp-watermark.image)
多次出栈:
![3.jpg](https://p1-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/5d46955edd6148558074fef0ae521c11~tplv-k3u1fbpfcp-watermark.image)
### 2.2.5清空栈
当时学C的时候需要释放内存资源,可是Java不用呀,所以栈顶指向栈底,就清空栈了
```
/**
* 清空栈
* @param stack
*/
public static void clearStack(Stack stack) {
stack.stackTop = null;
stack.stackBottom = stack.stackTop;
}
```
# 三、数据结构【队列】就是这么简单
数据结构的队列长的是这个样子:
![image](https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/b1868ded61534e85b29303a4e326361c~tplv-k3u1fbpfcp-zoom-1.image)
其实队列非常好理解,我们将队列可以**看成小朋友排队**
* 队尾的小朋友到指定的地点了-->出队
* 有新的小朋友加入了-->入队
相对于栈而言,队列的特性是:先进先出
* **先排队的小朋友肯定能先打到饭!**
队列也分成两种:
* 静态队列(数组实现)
* 动态队列(链表实现)
这次我就使用数组来实现静态队列了。值得注意的是:**往往实现静态队列,我们都是做成循环队列**
![image](https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/07f473385b264cd38353351c1425b3a8~tplv-k3u1fbpfcp-zoom-1.image)
做成循环队列的**好处是不浪费内存资源**!
## 3.1数据结构【队列】 代码实现
这次我们使用的是数组来实现静态队列,因此我们可以这样设计:
```
public class Queue {
//数组
public int [] arrays;
//指向第一个有效的元素
public int front;
//指向有效数据的下一个元素(即指向无效的数据)
public int rear;
}
```
从上面的设计我们可以发现:**rear并不指向最后一个有效的元素,在循环队列中这样设计是非常方便的**!因为这样设计可以**让我们分得清队头和队尾**(不然循环队列不断入队或出队,位置是变化很快的)
由于我们是循环队列,所以`front`和`rear`值会经常变动,我们得把`front`和`rear`的值限定在一个范围内,不然会超出队列的长度的。
有这么一个算法:`rear=(rear+1)%数组长度`
* 比如rear的下标是2,数组的长度是6,往后面移一位是3,那么`rear = (rear+1) % 6`,结果还是3
### 3.1.2初始化队列
**此时队列为空,分配了6个长度给数组(只能装5个实际的数字,rear指向的是无效的位置的)**
```
public static void main(String[] args) {
//初始化队列
Queue queue = new Queue();
queue.front = 0;
queue.rear = 0;
queue.arrays = new int[6];
}
```
### 3.1.3判断队列是否满了
如果rear指针和front指针紧挨着,那么说明队列就满了
```
/**
* 判断队列是否满了,front和rear指针紧挨着,就是满了
* @param queue
* @return
*/
public static boolean isFull(Queue queue) {
if ((queue.rear + 1) % queue.arrays.length == queue.front) {
System.out.println("关注公众号:Java3y--->此时队列满了!");
return true;
} else {
System.out.println("关注公众号:Java3y--->此时队列没满了!");
return false;
}
}
```
### 3.1.4入队
1. 判断该队列是否满了
2. 入队的值插入到队尾中(具体的位置就是rear指针的位置【再次声明:rear指向的是无效元素的位置】
3. rear指针移动(再次指向无效的元素位置)
```
/**
* 入队
*
* @param queue
*/
public static void enQueue(Queue queue,int value) {
// 不是满的队列才能入队
if (!isFull(queue)) {
// 将新的元素插入到队尾中
queue.arrays[queue.rear] = value;
// rear节点移动到新的无效元素位置上
queue.rear = (queue.rear + 1) % queue.arrays.length;
}
}
```
### 3.1.5遍历
**只要front节点不指向rear节点,那么就可以一直输出**
```
/**
* 遍历队列
* @param queue
*
*/
public static void traverseQueue(Queue queue) {
// front的位置
int i = queue.front;
while (i != queue.rear) {
System.out.println("关注公众号:Java3y--->" + queue.arrays[i]);
//移动front
i = (i + 1) % queue.arrays.length;
}
}
```
队列没满时:
![4.jpg](https://p6-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/fc16bae936034caeb194f3c93d81a27e~tplv-k3u1fbpfcp-watermark.image)
队列已满了就插入不了了(验证上面的方法是否正确):
![5.jpg](https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/c281fa037d6f406089a3f6e266d175a6~tplv-k3u1fbpfcp-watermark.image)
### 3.1.6判断该队列是否为空
只要`rear`和`front`指针指向同一个位置,那该队列就是空的了
```
/**
* 判断队列是否空,front和rear指针相等,就是空了
* @param queue
* @return
*/
public static boolean isEmpty(Queue queue) {
if (queue.rear == queue.front) {
System.out.println("关注公众号:Java3y--->此时队列空的!");
return true;
} else {
System.out.println("关注公众号:Java3y--->此时队列非空!");
return false;
}
}
```
### 3.1.7出队
出队的逻辑也非常简单:
1. 判断该队列是否为null
2. 如果不为null,则出队,**只要front指针往后面移就是出队了**!
```
/**
* 出队
*
* @param queue
*/
public static void outQueue(Queue queue) {
//判断该队列是否为null
if (!isEmpty(queue)) {
//不为空才出队
int value = queue.arrays[queue.front];
System.out.println("关注公众号:Java3y--->出队的元素是:" + value);
// front指针往后面移
queue.front = (queue.front + 1) % queue.arrays.length;
}
}
```
结果:
![6.jpg](https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/85ef348b39a04016874029727c02a666~tplv-k3u1fbpfcp-watermark.image)
# 四、总结
数据结构的栈和队列的应用非常非常的多,这里也只是最简单的入门,理解起来也不困难。
* 栈:先进后出
* 队列:先进先出
关于数据结构这方面我就到暂时到这里为止了,都简单的入个门,以后遇到更加复杂的再继续开新的文章来写~毕竟现在水平不够,也无法理解更深层次的东西~数据结构这东西是必备的,等到研究集合的时候还会来回顾它,或者遇到新的、复杂的也会继续学习....
想要更加深入数据结构的同学就得去翻阅相关的书籍咯~这仅仅是冰山一角