java实现栈的数组和链表的方法
这期内容当中小编将会给大家带来有关java实现栈的数组和链表的方法,以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。
站在用户的角度思考问题,与客户深入沟通,找到北湖网站设计与北湖网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都做网站、成都网站制作、企业官网、英文网站、手机端网站、网站推广、申请域名、网络空间、企业邮箱。业务覆盖北湖地区。
栈的介绍
栈,是一种先进后出(FILO)的线性数据结构,主要操作为入栈和出栈。
栈底:最早进入的元素存放的位置。
栈顶:最后进入元素存放的位置(有些栈中将栈顶表示为栈顶元素的下一位置)。
栈的数组的实现
示例如下:
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实现栈的数组和链表的方法
当前地址:http://pwwzsj.com/article/jighsp.html