教你怎么用Java数组和链表实现栈

一、何为栈？

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈可以类比成现实生活中的弹夹或者羽毛球桶

二、用数组实现栈

用数组模拟栈的思路分析如图：

1.定义一个top变量（指针）表示栈顶初始化为-1.
2.定义一个变量来记录栈的大小。
3.入栈操作有数据加入到栈中：top++; arr[top]=value;
4.出栈操作： int value=arr[top]; top–; return value;

下面看完整代码示例：

class Stack{
   public int maxsize;//栈的大小
   public int top=-1;//栈顶
   public int[] arr;

public Stack(int maxsize) {
       this.maxsize = maxsize;
       arr=new int[maxsize];
   }

//判断栈是否为空
   public boolean isEmpty(){
       return top==-1;
   }
   //判断栈是否满
   public boolean isFull(){
       return top==maxsize-1;
   }

//添加一个元素
   public void push(int value){
       if(isFull()){
           throw new RuntimeException("栈满");
       }
       top++;
       arr[top]=value;
   }
   //弹出一个元素
   public int pop(){
       if(isEmpty())
           throw new RuntimeException("栈空");
       int value=arr[top];
       top--;
       return value;
   }
   //遍历栈中的元素
   public void traverse(){
       if (isEmpty()){
           return;
       }
       //需要从栈顶开始显示数据
       for(int i = top; i >= 0 ; i--) {
           System.out.printf("stack[％d]=％d\n", i, arr[i]);
       }
       }
   }

入栈操作 top++;arr[top]=value;其实可以直接改写为arr[++top]=value;
出栈操作可以将 int value=arr[top]; top–;return value;改为return arr[top–];

三、链表实现栈

思路分析：

入栈操作：用一个临时节点保存当前栈顶节点，将入栈的新节点作为栈顶元素，并将next域指向原来的旧节点。 Node temp=top; top.setNext(temp);

出栈操作：先判断栈是否为空，不为空则将top节点的数据返回，并将top指向top的下一个next域：top=top.getNext();

public class LinkedListStack<V> {
     static class Node<V>{
       private V data;
       private Node<V> next;

public V getData() {
           return data;
       }

public void setData(V data) {
           this.data = data;
       }

public Node<V> getNext() {
           return next;
       }

public void setNext(Node<V> next) {
           this.next = next;
       }
   }
   public int stackSize;//栈内元素的个数
   public Node<V> top;//栈顶元素

public LinkedListStack() {
       stackSize = 0;
       top = null;
   }

//入栈
   public void push(V element){
       Node<V> temp=top;
       top=new Node<>();
       top.setData(element);
       top.setNext(temp);
       stackSize++;
   }
   //出栈
   public V pop(){
       if (isEmpty())
           throw new RuntimeException("empty stack");
       V value=top.getData();
       //栈顶指向下一个元素
       top=top.getNext();
       stackSize--;
       return value;
   }
   //查看栈顶元素
   public V peek(){
       return top.getData();
   }
   //判断是否为空
   public boolean isEmpty(){
       return stackSize==0;
   }
   //查看栈内元素个数
   public int getStackSize(){
       return stackSize;
   }
   }

四、测试

public class Test {
   public static void main(String[] args) {
       LinkedListStack<String> stack = new LinkedListStack<>();
       stack.push("a");
       stack.push("b");
       stack.push("c");
       System.out.println(stack.pop());
       System.out.println(stack.peek());
       System.out.println(stack.getStackSize());
   }
}
测试结果:
c
b
2

来源：https://blog.csdn.net/weixin_44991304/article/details/116713784