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出栈
- 在出栈之前看看该栈是否为空,不为空才出栈…
- 将栈顶的元素的指针(指向下一个节点)赋值给栈顶指针(完成出栈)
/** * 出栈(将栈顶的指针指向下一个节点) * @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.2.5清空栈
当时学C的时候需要释放内存资源,可是Java不用呀,所以栈顶指向栈底,就清空栈了
/** * 清空栈 * @param stack */ public static void clearStack(Stack stack) { stack.stackTop = null; stack.stackBottom = stack.stackTop; }
三、数据结构【队列】就是这么简单
数据结构的队列长的是这个样子:
其实队列非常好理解,我们将队列可以看成小朋友排队
- 队尾的小朋友到指定的地点了-->出队
- 有新的小朋友加入了-->入队
相对于栈而言,队列的特性是:先进先出
- 先排队的小朋友肯定能先打到饭!
队列也分成两种:
- 静态队列(数组实现)
- 动态队列(链表实现)
这次我就使用数组来实现静态队列了。值得注意的是:往往实现静态队列,我们都是做成循环队列
做成循环队列的好处是不浪费内存资源!
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入队
- 判断该队列是否满了
- 入队的值插入到队尾中(具体的位置就是rear指针的位置【再次声明:rear指向的是无效元素的位置】
- 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; } }
队列没满时:
队列已满了就插入不了了(验证上面的方法是否正确):
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出队
出队的逻辑也非常简单:
- 判断该队列是否为null
- 如果不为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; } }
结果:
四、总结
数据结构的栈和队列的应用非常非常的多,这里也只是最简单的入门,理解起来也不困难。
- 栈:先进后出
- 队列:先进先出
关于数据结构这方面我就到暂时到这里为止了,都简单的入个门,以后遇到更加复杂的再继续开新的文章来写~毕竟现在水平不够,也无法理解更深层次的东西~数据结构这东西是必备的,等到研究集合的时候还会来回顾它,或者遇到新的、复杂的也会继续学习….
想要更加深入数据结构的同学就得去翻阅相关的书籍咯~这仅仅是冰山一角