java中栈的数组和链表实现

栈的介绍

栈，是一种先进后出（FILO）的线性数据结构，主要操作为入栈和出栈。

栈底：最早进入的元素存放的位置。

栈顶：最后进入元素存放的位置（有些栈中将栈顶表示为栈顶元素的下一位置）。

免费在线学习视频推荐：java视频

栈的数组的实现

示例如下：

public class MyStack {     private int[] array;     private int top = -1;//用top来表示栈顶，指向栈顶元素       public MyStack(int capacity){         array = new int[capacity];     }       public void push(int data) throws Exception{         if(top >= array.length-1)             throw new IndexOutOfBoundsException("边界超过范围！");         else             array[++top] = data;//先将指针上移，后赋值     }       public int pop() throws Exception{         int temp;         if(top < 0)             throw new IndexOutOfBoundsException("栈为空，不能再删除元素！");         else{             temp = array[top];             array[top--] = 0;         }         return temp;     }       public void output(){         for(int i = 0; i <= top; i++){             System.out.println(array[i]);         }     }       public static void main(String[] args) throws Exception{         MyStack myStack = new MyStack(5);         myStack.push(1);         myStack.push(3);         myStack.push(2);         myStack.pop();         myStack.push(4);         myStack.pop();         myStack.output();     } }

栈的链表实现

栈用链表来实现时，和数组实现不同的是，在出栈时，因为我们只有一个top节点来指向栈顶，因此需要从头到尾遍历一遍，来找到栈顶的前一个位置。

具体的实现如下：

public class MyStack_LinkList {     private static class Node{         int data;         Node next;         Node(int data){             this.data = data;         }     }     private Node head;//定义链表的头结点     private Node top;     private int size;//定义栈中的元素个数     private int maxSize;       private MyStack_LinkList(int capacity){         maxSize = capacity;     }       public void push(int data) throws Exception{         if(size >= maxSize){             throw new IndexOutOfBoundsException("栈已满，不能再入栈！");         }         Node pushedNode = new Node(data);         if(size == 0){             head = pushedNode;             top = pushedNode;             pushedNode.next = null;         }         else{             top.next = pushedNode;             pushedNode.next = null;             top = pushedNode;         }         size++;     }       public int pop() throws Exception{         int temp = 0;         if(size <= 0)             throw new IndexOutOfBoundsException("栈为空，不能再出栈！");         else if(size == 1){//当栈中元素个数为1时，单独讨论，需将头节点置为空             temp = top.data;             top = null;         }         else{             temp = top.data;             top = get(size - 1);//此时需遍历一遍链表，用top指向需出栈的上一个节点             top.next = null;         }         size--;         return temp;       }       /*     从头到尾查找元素      */     public Node get(int index){         Node temp = head;         for(int i = 1; i < index; i++){             temp = temp.next;         }         return temp;     }       public void output(){         Node temp = head;         for(int i = 0; i < size; i++){             System.out.println(temp.data);             temp = temp.next;         }     }       public static void main(String[] args) throws Exception{         MyStack_LinkList myStack_linkList = new MyStack_LinkList(5);         myStack_linkList.push(1);         myStack_linkList.push(2);         myStack_linkList.pop();         myStack_linkList.push(3);         myStack_linkList.push(5);         myStack_linkList.output();     } }

栈的应用场景

（1）括号匹配判断，用于判断()、{}等是否匹配；

（2）进制转换时，逆向输出转换后的数；

（3）实现递归的逻辑可以用栈来实现；

（4）栈还可以用于面包屑导航，使用户在浏览页面时可以轻松地回溯到上一级或更上一级页面。

想学习更多相关知识请访问：java入门程序，欢迎大家一起来共同学习！

以上就是java中栈的数组和链表实现的详细内容，更多内容请关注技术你好其它相关文章！