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 
栈的链表实现
栈用链表来实现时，和数组实现不同的是，在出栈时，因为我们只有一个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 
栈的应用场景
（1）括号匹配判断，用于判断()、{}等是否匹配；
（2）进制转换时，逆向输出转换后的数；
（3）实现递归的逻辑可以用栈来实现；
（4）栈还可以用于面包屑导航，使用户在浏览页面时可以轻松地回溯到上一级或更上一级页面。
想学习更多相关知识请访问：java入门程序，欢迎大家一起来共同学习！
                                                    
                                                
分享本文到 
×用微信扫描并分享
			
微海报分享

猜你喜欢：

如何实现java链表中的基本操作（增、删、查、改） 
java中关于队列的数组和链表实现 
java中动态数组的具体实现 
java笔试手写算法面试题大全含答案 
java中使用数组实现环形队列