Java实现栈（链表和线性表两种方法实现）
Java实现栈（链表和线性表两种方法实现）
一、栈的介绍
任何数据结构都是一种规则
栈就是在最基础的结构——线性结构和链式结构上面定义规则形成的
如果对基本数据结构（线性表和链表）有疑问的同学可以看我之前的博客：https://www.cnblogs.com/yxm2020/p/12762888.html
规则如下：
限制链表或者线性表元素的插入和取出，只能在同一端进行操作，运行插入的一段称为栈顶（top),另一端为固定的一端，成为栈底。
图解：（入栈和出栈）
特点：
先入后出FILO(First in last out),最先放入栈的数据，只能最后才能出来，和队列完全相反
栈的应用场景：
保存运行过程中程序中的代码或者值，比如：
子程序的调用
处理递归的调用
表达式的转换（中缀转后缀）
二叉树的遍历
图形的深度优先遍历
二、代码的实现思路
1、思路
确定一个结构存储数据，线性表或者链表
既然只能在栈顶操作，那么定义一栈顶标志（top)
最基本的两个方法，入栈和出栈
入栈后，在栈顶加入一个元素，top上移一个单元
出栈后，在栈顶删除一个元素，top下移一个单元
2、Java实现
用Java数组模拟栈
java链表实现栈
三、Java数组模拟栈
public class ArrayStack {
//栈顶标志
private int top;
//java数组
private T[] stack;
//最大长度
private int maxsize;
public ArrayStack(int maxsize,Class<T> type){
this.maxsize = maxsize;
this.top = -1;
stack = (T[]) Array.newInstance(type,maxsize);
}
//长度
public int size(){
return top+1;
}
//栈满
public boolean isFull(){
return top == maxsize-1;
}
//栈空
public boolean isEnpty(){
return top == -1;
}
//入栈
public void push(T t){
if(isFull()){
throw new RuntimeException("栈满");
}
top++;
stack[top] = t;
}
//出栈
public T pop(){
if(isEnpty()){
throw new RuntimeException("栈空");
}
T value = stack[top];
top--;
return value;
}
//遍历
public void show(){
if(isEnpty()){
System.out.println("栈空");
}
int temp = top;
while (temp != -1){
System.out.println(stack[temp]);
temp--;
}
}}
四、Java链表实现栈
public class LinkedStack {
//定义一个栈顶标志，带了个
private Node top;
private class Node{
private Node next;
private T t;
public Node(T t){
this.t = t;
}
}
//创建
public LinkedStack(){
top = new Node(null);
}
//栈空
public boolean isEnpty(){
if(top.next == null){
return true;
}
return false;
}
//入栈
public void push(T t){
Node newNode = new Node(t);
//从栈顶入
newNode.next = top.next;
top.next = newNode;
}
//出栈
public T pop(){
if(isEnpty()){
System.out.println("栈空");
return null;
}
T value = top.next.t;
top.next = top.next.next;
return value;
}
//show
public void show(){
Node temp = top;
if(temp.next == null){
System.out.println("栈空");
}
while (temp.next!=null){
temp = temp.next;
System.out.println(temp.t);
}
}}
