专栏首页三分恶的专栏重学数据结构(二、栈)

重学数据结构(二、栈)

1、栈的定义和特点

栈(Stack)又称堆栈, 是限制在表的一端进行插入和删除运算的线性表。

如果要拿一个东西对比,羽毛球筒比较合适。

栈遵循后进先出( Last-in-first-out,LIFO)的原则。

比如上面的羽毛球筒,只能将最顶端的羽毛球移出,也只能将新的羽毛球放到最顶端——这两种操作分别称作入栈( Push)出栈( Pop)。入栈和出栈的示意图如下:

最顶端的羽毛球叫栈顶栈顶 (top),最底端的羽毛球称为栈底 (bottom)

2、栈的基本操作

栈的基本操作除了入栈和出栈外, 还有栈的初始化、 栈空的判定, 以及取栈顶元素等。

根据这些操作,我们定义一个接口:

/**
 * @Author 三分恶
 * @Date 2020/8/26
 * @Description 栈接口
 */
public interface Stack {
    public int getSize();          //返回栈中元素数目
    public boolean isEmpty();      //判空
    public Object top();           //取栈顶元素但不删除
    public void push(Object element);      //入栈
    public Object pop();              //出栈
}

线性表有顺序和链式两种实现,栈同样有两种实现。

3、顺序栈

这里我们通过一个可扩容的数组来实现。

/**
 * @Author 三分恶
 * @Date 2020/8/26
 * @Description 顺序栈--数组实现
 */
public class ArrayStack implements Stack{

    private static  int defaultSize=15;   //默认容量
    private int size;                    //实际容量:实际存储元素个数
    private Object[] data;               //存放元素的数组

    /**
     * 无参构造方法:按默认容量构造元素数组
     */
    public ArrayStack() {
        data=new Object[defaultSize];
        size=0;
    }

    /**
     * 有参构造方法:指定元素数组容量
     * @param size
     */
    public ArrayStack(int size){
        data=new Object[size];
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size==0;
    }

    /**
     * 取栈顶元素:不删除栈顶元素
     * @return
     */
    public Object top() {
        if (isEmpty())
            throw new RuntimeException("栈空");
        size--;
        return data[size-1];
    }

    /**
     * 入栈
     * @param element
     */
    public void push(Object element) {
        //数组已满,扩容
         if (size==data.length){
             //扩容两倍的新数组
             Object [] newData=new Object[size<<1];
             //拷贝数组
             System.arraycopy(data,0,newData,0,size);
             data=newData;
         }
         //栈顶上插入新元素
         data[size]=element;
         size++;
    }

    /**
     * 出栈
     * @return
     */
    public Object pop() {
        if (isEmpty())
            throw new RuntimeException("栈空");
        Object top=data[size-1];
        data[size-1]=null;
        size--;
        return top;
    }
}

时间复杂度分析:

  • getSize():O(1)
  • isEmpty():O(1)
  • top():O(1)
  • push():平均O(1),最坏(扩容)O(n)
  • pop(): O(1)

3、链栈

链栈指的是链式存储结构实现的栈。在前面的学习中,我们已经完成了单向链表的实现,代码如下,具体说明可查看上一篇内容:

现在我们通过单向链表来实现链栈:

/**
 * @Author 三分恶
 * @Date 2020/8/26
 * @Description
 */
public class ListStack implements Stack{
    //单向链表
    private SinglyLinkedList list;

    /**
     * 构造函数:初始化单向链表
     */
    public ListStack(){
        list=new SinglyLinkedList();
    }

    /**
     * 获取栈的容量
     * @return
     */
    public int getSize() {
        return list.getSize();
    }

    public boolean isEmpty() {
        return list.getSize()==0;
    }

    /**
     * 取栈顶元素
     * @return
     */
    public Object top() {
        //取列表的尾节点
        return list.get(list.getSize()-1);
    }

    /**
     * 入栈
     * @param element
     */
    public void push(Object element) {
        //队列尾插入
       list.addTail(element);
    }

    /**
     * 出栈
     * @return
     */
    public Object pop() {
        int topIndex=list.getSize()-1;
        //列表为节点
        Object top=list.get(topIndex);
        //删除尾结点
        list.remove(topIndex);
        return top;
    }
}

时间复杂度分析:

  • getSize():O(1)
  • isEmpty():O(1)
  • top():O(1)
  • push():O(1)
  • pop(): O(1)

4、java中的栈

在Java中有一个java.util.Stack类,它实现了栈的结构。

它是Vector的子类,也自定义了一些作为栈的方法。

java.util.Stack类是Vector的子类,实际上并不建议使用它。

在Java中还有另外一个集合,可以作为栈使用,它就是LinkedList。LinkedList中实现了push、pop方法。具体可以查看LinkedList源码阅读笔记


源码地址:https://gitee.com/LaughterYoung/data-structure-learn.git

上一篇:重学数据结构(一、线性表)


本文为学习笔记类博客,主要资料来源如下!

参考:

【1】:邓俊辉 编著. 《数据结构与算法》 【2】:王世民 等编著 . 《数据结构与算法分析》 【3】: Michael T. Goodrich 等编著.《Data-Structures-and-Algorithms-in-Java-6th-Edition》 【4】:严蔚敏、吴伟民 编著 . 《数据结构》 【5】:程杰 编著 . 《大话数据结构》 【6】:Java Stack 类

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 重学数据结构(三、队列)

    和上一篇的栈相反,队列(queue)是一种先进先出(First In First Out, FIFO)的线性表。

    三分恶
  • 设计模式—— 五:迪米特原则

    迪米特法则来自于1987年美国东北大学(Northeastern University)一个名为“Demeter”的研究项目。迪米特法则又称为最少知识原则(Le...

    三分恶
  • 设计模式—— 十七:装饰器模式

    ● Component(抽象构件) 抽象构件它是具体构件和抽象装饰类的共同父类,声明了在具体构件中实现的业务方法。

    三分恶
  • 数据结构之优先队列

    1、优先队列的底层实现可以使用最大堆进行实现,由于优先队列本身就是一个队列,所以可以复用队列的接口。

    别先生
  • 聊聊flink的window操作

    flink-streaming-java_2.11-1.7.0-sources.jar!/org/apache/flink/streaming/api/data...

    codecraft
  • php实现的表单验证类完整示例

    JavaScript正则表达式在线测试工具: http://tools.zalou.cn/regex/javascript

    砸漏
  • 厚土Go学习笔记 | 05. 函数

    函数可以没有参数,也可以有多个参数。 package main import( "fmt" ) //有两个参数的函数 func add(x,y in...

    李海彬
  • [干货来袭]C#7.0新特性(VS2017可用)

    前言 微软昨天发布了新的VS 2017 ..随之而来的还有很多很多东西... .NET新版本 ASP.NET新版本...等等..太多..实在没消化.. 分享一下...

    GuZhenYin
  • DP、DFS-LeetCode 198、332、165(DP, DFS)

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小...

    算法工程师之路
  • 堆排序

    大学里的混子

扫码关注云+社区

领取腾讯云代金券