一、前言
上一篇已经讲过了链表【Java实现单向链表】了，它跟数组都是线性结构的基础，本文主要讲解线性结构的应用：栈和队列
如果写错的地方希望大家能够多多体谅并指正哦，如果有更好的理解的方式也希望能够在评论下留言，让大家学习学习～
二、数据结构【栈】就是这么简单
2.1数据结构【栈】介绍
数据结构的栈长的是这个样子：
其实非常好理解，我们将栈可以看成一个箱子
- 往箱子里面放东西叫做入栈
- 往箱子里面取东西叫做出栈
- 箱子的底部叫做栈底
- 箱子的顶部叫做栈顶
说到栈的特性，肯定会有一句经典的言语来概括：先进后出(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); }
结果：
这就符合了先进后出的特性了～
