带你了解Java数据结构和算法之栈

目录
  • 1、栈的基本概念
  • 2、Java模拟简单的顺序栈实现  
  • 3、增强功能版栈
  • 4、利用栈实现字符串逆序
  • 5、利用栈判断分隔符是否匹配  
  • 6、总结

1、栈的基本概念

(英语:stack)又称为堆栈堆叠,栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。

由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。栈也称为后进先出表。

这里以羽毛球筒为例,羽毛球筒就是一个栈,刚开始羽毛球筒是空的,也就是空栈,然后我们一个一个放入羽毛球,也就是一个一个push进栈,当我们需要使用羽毛球的时候,从筒里面拿,也就是pop出栈,但是第一个拿到的羽毛球是我们最后放进去的。

2、Java模拟简单的顺序栈实现  

package com.ys.datastructure;
public class MyStack {
    private int[] array;
    private int maxSize;
    private int top;
    public MyStack(int size){
        this.maxSize = size;
        array = new int[size];
        top = -1;
    }
    //压入数据
    public void push(int value){
        if(top < maxSize-1){
            array[++top] = value;
        }
    }
    //弹出栈顶数据
    public int pop(){
        return array[top--];
    }
    //访问栈顶数据
    public int peek(){
        return array[top];
    }
    //判断栈是否为空
    public boolean isEmpty(){
        return (top == -1);
    }
    //判断栈是否满了
    public boolean isFull(){
        return (top == maxSize-1);
    }
}

测试:

package com.ys.test;
import com.ys.datastructure.MyStack;
public class MyStackTest {
    public static void main(String[] args) {
        MyStack stack = new MyStack(3);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.peek());
        while(!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }
}

结果:  

这个栈是用数组实现的,内部定义了一个数组,一个表示最大容量的值以及一个指向栈顶元素的top变量。构造方法根据参数规定的容量创建一个新栈,push()方法是向栈中压入元素,指向栈顶的变量top加一,使它指向原顶端数据项上面的一个位置,并在这个位置上存储一个数据。pop()方法返回top变量指向的元素,然后将top变量减一,便移除了数据项。要知道 top 变量指向的始终是栈顶的元素。

产生的问题:

  • ①、上面栈的实现初始化容量之后,后面是不能进行扩容的(虽然栈不是用来存储大量数据的),如果说后期数据量超过初始容量之后怎么办?(自动扩容)
  • ②、我们是用数组实现栈,在定义数组类型的时候,也就规定了存储在栈中的数据类型,那么同一个栈能不能存储不同类型的数据呢?(声明为Object)
  • ③、栈需要初始化容量,而且数组实现的栈元素都是连续存储的,那么能不能不初始化容量呢?(改为由链表实现)

3、增强功能版栈

对于上面出现的问题,第一个能自动扩容,第二个能存储各种不同类型的数据,解决办法如下:(第三个在讲链表的时候在介绍)

这个模拟的栈在JDK源码中,大家可以参考 Stack 类的实现。

package com.ys.datastructure;
import java.util.Arrays;
import java.util.EmptyStackException;
public class ArrayStack {
    //存储元素的数组,声明为Object类型能存储任意类型的数据
    private Object[] elementData;
    //指向栈顶的指针
    private int top;
    //栈的总容量
    private int size;
    //默认构造一个容量为10的栈
    public ArrayStack(){
        this.elementData = new Object[10];
        this.top = -1;
        this.size = 10;
    }
    public ArrayStack(int initialCapacity){
        if(initialCapacity < 0){
            throw new IllegalArgumentException("栈初始容量不能小于0: "+initialCapacity);
        }
        this.elementData = new Object[initialCapacity];
        this.top = -1;
        this.size = initialCapacity;
    }
    //压入元素
    public Object push(Object item){
        //是否需要扩容
        isGrow(top+1);
        elementData[++top] = item;
        return item;
    }
    //弹出栈顶元素
    public Object pop(){
        Object obj = peek();
        remove(top);
        return obj;
    }
    //获取栈顶元素
    public Object peek(){
        if(top == -1){
            throw new EmptyStackException();
        }
        return elementData[top];
    }
    //判断栈是否为空
    public boolean isEmpty(){
        return (top == -1);
    }
    //删除栈顶元素
    public void remove(int top){
        //栈顶元素置为null
        elementData[top] = null;
        this.top--;
    }
    /**
     * 是否需要扩容,如果需要,则扩大一倍并返回true,不需要则返回false
     * @param minCapacity
     * @return
     */
    public boolean isGrow(int minCapacity){
        int oldCapacity = size;
        //如果当前元素压入栈之后总容量大于前面定义的容量,则需要扩容
        if(minCapacity >= oldCapacity){
            //定义扩大之后栈的总容量
            int newCapacity = 0;
            //栈容量扩大两倍(左移一位)看是否超过int类型所表示的最大范围
            if((oldCapacity<<1) - Integer.MAX_VALUE >0){
                newCapacity = Integer.MAX_VALUE;
            }else{
                newCapacity = (oldCapacity<<1);//左移一位,相当于*2
            }
            this.size = newCapacity;
            int[] newArray = new int[size];
            elementData = Arrays.copyOf(elementData, size);
            return true;
        }else{
            return false;
        }
    }
}

测试:

//测试自定义栈类 ArrayStack
//创建容量为3的栈,然后添加4个元素,3个int,1个String.
@Test
public void testArrayStack(){
    ArrayStack stack = new ArrayStack(3);
    stack.push(1);
    //System.out.println(stack.peek());
    stack.push(2);
    stack.push(3);
    stack.push("abc");
    System.out.println(stack.peek());
    stack.pop();
    stack.pop();
    stack.pop();
    System.out.println(stack.peek());
}v

结果:

4、利用栈实现字符串逆序

我们知道栈是后进先出,我们可以将一个字符串分隔为单个的字符,然后将字符一个一个push()进栈,在一个一个pop()出栈就是逆序显示了。如下:

将 字符串“how are you” 反转!!!

ps:这里我们是用上面自定的栈来实现的,大家可以将ArrayStack替换为JDK自带的栈类Stack试试

//进行字符串反转
@Test
public void testStringReversal(){
    ArrayStack stack = new ArrayStack();
    String str = "how are you";
    char[] cha = str.toCharArray();
    for(char c : cha){
        stack.push(c);
    }
    while(!stack.isEmpty()){
        System.out.print(stack.pop());
    }
}

结果:  

5、利用栈判断分隔符是否匹配  

写过xml标签或者html标签的,我们都知道<必须和最近的>进行匹配,[ 也必须和最近的 ] 进行匹配。

比如:<abc[123]abc>这是符号相匹配的,如果是 <abc[123>abc] 那就是不匹配的。

对于 12<a[b{c}]>,我们分析在栈中的数据:遇到匹配正确的就消除

最后栈中的内容为空则匹配成功,否则匹配失败!!!

//分隔符匹配
//遇到左边分隔符了就push进栈,遇到右边分隔符了就pop出栈,看出栈的分隔符是否和这个有分隔符匹配
@Test
public void testMatch(){
    ArrayStack stack = new ArrayStack(3);
    String str = "12<a[b{c}]>";
    char[] cha = str.toCharArray();
    for(char c : cha){
        switch (c) {
        case '{':
        case '[':
        case '<':
            stack.push(c);
            break;
        case '}':
        case ']':
        case '>':
            if(!stack.isEmpty()){
                char ch = stack.pop().toString().toCharArray()[0];
                if(c=='}' && ch != '{'
                    || c==']' && ch != '['
                    || c==')' && ch != '('){
                    System.out.println("Error:"+ch+"-"+c);
                }
            }
            break;
        default:
            break;
        }
    }
}

6、总结

根据栈后进先出的特性,我们实现了单词逆序以及分隔符匹配。所以其实栈是一个概念上的工具,具体能实现什么功能可以由我们去想象。栈通过提供限制性的访问方法push()和pop(),使得程序不容易出错。

对于栈的实现,我们稍微分析就知道,数据入栈和出栈的时间复杂度都为O(1),也就是说栈操作所耗的时间不依赖栈中数据项的个数,因此操作时间很短。而且需要注意的是栈不需要比较和移动操作,我们不要画蛇添足。  

本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注我们的更多内容!

(0)

相关推荐

  • 带你了解Java数据结构和算法之前缀,中缀和后缀表达式

    目录 1.人如何解析算术表达式 ①.求值 3+4-5 ②.求值 3+4*5 2.计算机如何解析算术表达式 3.后缀表达式 ①.如何将中缀表达式转换为后缀表达式? 一.先自定义一个栈 二.前缀表达式转换为后缀表达式 三.测试 四.结果 五.分析 ②.计算机如何实现后缀表达式的运算? 4.前缀表达式 ①.如何将中缀表达式转换为前缀表达式? ②.计算机如何实现前缀表达式的运算? 总结 1.人如何解析算术表达式 如何解析算术表达式?或者换种说法,遇到某个算术表达式,我们是如何计算的: ①.求值 3+4-

  • 带你了解Java数据结构和算法之数组

    目录 1.Java数组介绍 ①.数组的声明 ②.访问数组元素以及给数组元素赋值 ③.数组遍历 2.用类封装数组实现数据结构 3.分析数组的局限性 4.总结 1.Java数组介绍 在Java中,数组是用来存放同一种数据类型的集合,注意只能存放同一种数据类型(Object类型数组除外). ①.数组的声明 第一种方式: 数据类型 [] 数组名称 = new 数据类型[数组长度]; 这里 [] 可以放在数组名称的前面,也可以放在数组名称的后面,我们推荐放在数组名称的前面,这样看上去 数据类型 [] 表示

  • 带你了解Java数据结构和算法之队列

    目录 1.队列的基本概念 2.Java模拟单向队列实现 3.双端队列 4.优先级队列 5.总结 1.队列的基本概念 队列(queue)是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表.进行插入操作的端称为队尾,进行删除操作的端称为队头.队列中没有元素时,称为空队列. 队列的数据元素又称为队列元素.在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队.因为队列只允许在一端插入,在

  • Java数据结构和算法之冒泡,选择和插入排序算法

    目录 1.冒泡排序 2.选择排序 3.插入排序 4.总结 1.冒泡排序 这个名词的由来很好理解,一般河水中的冒泡,水底刚冒出来的时候是比较小的,随着慢慢向水面浮起会逐渐增大,这物理规律我不作过多解释,大家只需要了解即可. 冒泡算法的运作规律如下: ①.比较相邻的元素.如果第一个比第二个大,就交换他们两个. ②.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.这步做完后,最后的元素会是最大的数(也就是第一波冒泡完成). ③.针对所有的元素重复以上的步骤,除了最后一个. ④.持续每次对越

  • 带你了解Java数据结构和算法之栈

    目录 1.栈的基本概念 2.Java模拟简单的顺序栈实现 3.增强功能版栈 4.利用栈实现字符串逆序 5.利用栈判断分隔符是否匹配 6.总结 1.栈的基本概念 栈(英语:stack)又称为堆栈或堆叠,栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表.它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来).栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针. 栈是允许在同一端进行插入和删除操

  • Java数据结构与算法之栈(动力节点Java学院整理)

    stack,中文翻译为堆栈,其实指的是栈,heap,堆.这里讲的是数据结构的栈,不是内存分配里面的堆和栈. 栈是先进后出的数据的结构,好比你碟子一个一个堆起来,最后放的那个是堆在最上面的. 队列就是排队买苹果,先去的那个可以先买. 栈 public class Stack { private int array[]; private int max; private int top; public Stack(int max){ this.max = max; array = new int[m

  • Java数据结构与算法之栈(Stack)实现详解

    本篇是java数据结构与算法的第2篇,从本篇开始我们将来了解栈的设计与实现,以下是本篇的相关知识点: 栈的抽象数据类型顺序栈的设计与实现链式栈的设计与实现栈的应用 栈的抽象数据类型   栈是一种用于存储数据的简单数据结构,有点类似链表或者顺序表(统称线性表),栈与线性表的最大区别是数据的存取的操作,我们可以这样认为栈(Stack)是一种特殊的线性表,其插入和删除操作只允许在线性表的一端进行,一般而言,把允许操作的一端称为栈顶(Top),不可操作的一端称为栈底(Bottom),同时把插入元素的操作

  • 带你了解Java数据结构和算法之递归

    目录 1.递归的定义 2.求一个数的阶乘:n! 3.递归的二分查找 4.分治算法 5.汉诺塔问题 6.归并排序 7.消除递归 8.递归的有趣应用 ①.求一个数的乘方 ②.背包问题 ③.组合:选择一支队伍 9.总结 1.递归的定义 递归,就是在运行的过程中调用自己. 递归必须要有三个要素: ①.边界条件 ②.递归前进段 ③.递归返回段 当边界条件不满足时,递归前进:当边界条件满足时,递归返回. 2.求一个数的阶乘:n! 规定: ①.0!=1 ②.1!=1 ③.负数没有阶乘 上面的表达式我们先用fo

  • 带你了解Java数据结构和算法之二叉树

    目录 1.树 2.二叉树 3.查找节点 4.插入节点 5.遍历树 6.查找最大值和最小值 7.删除节点 ①.删除没有子节点的节点 ②.删除有一个子节点的节点 ③.删除有两个子节点的节点 ④.删除有必要吗? 8.二叉树的效率 9.用数组表示树 10.完整的BinaryTree代码 11.哈夫曼(Huffman)编码 ①.哈夫曼编码 ②.哈夫曼解码 12.总结 1.树 树(tree)是一种抽象数据类型(ADT),用来模拟具有树状结构性质的数据集合.它是由n(n>0)个有限节点通过连接它们的边组成一个

  • 带你了解Java数据结构和算法之无权无向图

    目录 1.图的定义 ①.邻接: ②.路径: ③.连通图和非连通图: ④.有向图和无向图: ⑤.有权图和无权图: 2.在程序中表示图 ①.顶点: ②.边: 3.搜索 ①.深度优先搜索(DFS) ②.广度优先搜索(BFS) ③.程序实现 4.最小生成树 5.总结 1.图的定义 我们知道,前面讨论的数据结构都有一个框架,而这个框架是由相应的算法实现的,比如二叉树搜索树,左子树上所有结点的值均小于它的根结点的值,右子树所有结点的值均大于它的根节点的值,类似这种形状使得它容易搜索数据和插入数据,树的边表示

  • 带你了解Java数据结构和算法之链表

    目录 1.链表(Linked List) 2.单向链表(Single-Linked List) ①.单向链表的具体实现 ②.用单向链表实现栈 4.双端链表 ①.双端链表的具体实现 ②.用双端链表实现队列 5.抽象数据类型(ADT) 6.有序链表 7.有序链表和无序数组组合排序 8.双向链表 9.总结 前面博客我们在讲解数组中,知道数组作为数据存储结构有一定的缺陷.在无序数组中,搜索性能差,在有序数组中,插入效率又很低,而且这两种数组的删除效率都很低,并且数组在创建后,其大小是固定了,设置的过大会

  • 带你了解Java数据结构和算法之哈希表

    目录 1.哈希函数的引入 ①.把数字相加 ②.幂的连乘 2.冲突 3.开放地址法 ①.线性探测 ②.装填因子 ③.二次探测 ④.再哈希法 4.链地址法 5.桶 6.总结 1.哈希函数的引入 大家都用过字典,字典的优点是我们可以通过前面的目录快速定位到所要查找的单词.如果我们想把一本英文字典的每个单词,从 a 到 zyzzyva(这是牛津字典的最后一个单词),都写入计算机内存,以便快速读写,那么哈希表是个不错的选择. 这里我们将范围缩小点,比如想在内存中存储5000个英文单词.我们可能想到每个单词

随机推荐