您的位置 首页 技术

java中栈的数组和链表实现

栈的介绍 栈,是一种先进后出(FILO)的线性数据结构,主要操作为入栈和出栈。 栈底:最早进入的元素存放的位置。 栈顶:最后进入元素存放的位置(有些栈中将栈顶表示为栈顶元素的下一位…

栈的介绍

栈,是一种先进后出(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中栈的数组和链表实现的详细内容,更多请关注24课堂在线网其它相关文章!

本文来自网络,不代表24小时课堂在线立场,转载请注明出处:https://www.24ketang.cn/11809.html

为您推荐

返回顶部