美文网首页
数据结构(一) -- 栈

数据结构(一) -- 栈

作者: 峰峰小 | 来源:发表于2016-09-21 22:27 被阅读339次

一,栈

栈是存放对象的一种特殊容器,在插入与删除对象时,这种结构遵循后进先出(Last-in-first-out,LIFO)的原则--也就是说,对象可以任意插入栈中,但每次取出的都是此前插入的最后一个对象。
比如一摞椅子,只能将最顶端的椅子移出,也只能将新椅子放到最顶端--这两种操作分别称作入栈(Push)和退栈(Pop)。



栈是最基本的数据结构之一,在实际应用中几乎无所不在。例如,网络浏览器会将用户最近访问过的地址组织为一个栈:用户每访问一个新页面,其地址就会被存放至栈顶;而用户每次按下“Back”按钮,最后一个被记录下的地址就会被清除掉。再如,当今主流的文本编辑器大都支持编辑操作的历史记录功能:用户的编辑操作会被依次记录在一个栈中;一旦出现误操作,用户只需按下“Undo”按钮,即可撤销最近一次操作并回到此前的编辑状态。

由于栈的重要性,在Java 的java.util 包中已经专门为栈结构内建了一个类--java.util.Stack


二,栈ADT(AbstractDataType)

作为一种抽象数据类型,栈必须支持以下方法:

操作方法 功能描述
push(x) 将对象x 压至栈顶
输入:一个对象
输出:无
pop() 若栈非空,则将栈顶对象移除,并将其返回否则,报错
输入:无
输出:对象

此外,还可以定义如下的方法:

操作方法 功能描述
getSize() 返回栈内当前对象的数目
输入:无
输出:非负整数
isEmpty() 检查栈是否为空
输入:无
输出:布尔标志
top() 若栈非空,则返回栈顶对象(但并不移除)否则,报错
输入:无
输出:栈顶对象

三,基于数组的简单实现

先定义一个Stack接口:

public interface Stack {
    public int getSize();//返回栈中元素数目
    public boolean isEmpty();//判断栈是否为空
    public Object top() throws ExceptionStackEmpty;//取栈顶元素(但不删除)
    public void push (Object ele) throws ExceptionStackFull;//入栈
    public Object pop() throws ExceptionStackEmpty;//出栈
}

定义用到的两个异常:
一个stack空异常

/*
* 当试图对空栈应用pop或top方法时,本意外将被抛出
*/
package dsa;
    public class ExceptionStackEmpty extends RuntimeException {
    public ExceptionStackEmpty(String err) {
        super(err);
    }
}

一个stack满异常

/*
* 当试图对满栈应用push方法时,本意外将被抛出
*/
package dsa;
    public class ExceptionStackFull extends RuntimeException {
    public ExceptionStackFull (String err) {
        super(err);
    }
}

为了实现栈接口,我们可以用一个数组来存放其中的元素。具体来说,就是使用一个容量为N的数组S,再加上一个变量top 来只是当前栈顶的位置。

由于Java数组的元素都是从0 开始编号,所以top必须初始化为-1;反过来,只要top = -1,就说明栈为空。

基于数组的栈实现细节:

/*
* 借助定长数组实现Stack接口
*/
package dsa;
public class Stack_Array implements Stack {
    public static final int CAPACITY = 1024;//数组的默认容量
    protected int capacity;//数组的实际容量
    protected Object[] S;//对象数组
    protected int top = -1;//栈顶元素的位置
    //按默认容量创建栈对象
    public Stack_Array()
    { this(CAPACITY); }
    //按指定容量创建栈对象
    public Stack_Array(int cap) {
        capacity = cap;
        S = new Object[capacity];
    }
    //获取栈当前的规模
    public int getSize()
    { return (top + 1); }
    //测试栈是否为空
    public boolean isEmpty()
    { return (top < 0); }
    //入栈
    public void push(Object obj) throws ExceptionStackFull {
        if (getSize() == capacity)
        throw new ExceptionStackFull("意外:栈溢出");
        S[++top] = obj;
    }
    //取栈顶元素
    public Object top() throws ExceptionStackEmpty {
        if (isEmpty())
        throw new ExceptionStackEmpty("意外:栈空");
        return S[top];
    }
    //出栈
    public Object pop() throws ExceptionStackEmpty {
        Object elem;
        if (isEmpty())
        throw new ExceptionStackEmpty("意外:栈空");
        elem = S[top];
        S[top--] = null;
        return elem;
    }
}

四,栈应用实例

  • ** Tip借助栈进行数组倒置**

     public static Integer[] reverse(Integer[] a) {
      Stack_Array S = new Stack_Array(a.length);
      Integer[] b = new Integer[a.length];
      for (int i = 0; i < a.length; i++)
          S.push(a[i]); // 所有元素顺序入栈
      for (int i = 0; i < a.length; i++)
          b[i] = (Integer) (S.pop()); // 逆序退栈
      return b;
    }
    
  • ** 括号匹配算法**

  • ** HTML文档的标志匹配**

相关文章

  • 栈和队列

    1、栈 栈是一种先进先出的数据结构。栈顶进栈,栈顶出栈。 数据结构 栈的初始化 进栈 出栈 栈的最小值 2、队列 ...

  • 栈和堆以及栈区和堆区的区别

    栈和堆以及栈区和堆区的区别 数据结构中的栈和堆 栈:具有先进后出性质的数据结构 堆:一种经过排序的树形数据结构,节...

  • 004 go语言实现栈

    1 数据结构 数据结构: 要实现的功能:0 栈的初始化1 获取栈长度2 入栈3 出栈4 清空栈内容5 判断栈是否为...

  • 数据结构与算法 第二节:栈 栈: 一种先进后出的数据结构。可以想象成手枪的弹夹。 栈的特点: 栈的行为: 栈的代...

  • 什么是堆栈?

    堆与栈是两种数据结构,并不是一种数据结构,堆是堆,栈是栈。 1、栈:是一种只能在一端进行插入和删除的数据结构。 允...

  • 2019-07-11—栈

    栈:Java数据结构和算法(四)——栈 string和char一般这么转化: 21、定义栈的数据结构,请在该类型中...

  • java高级知识点

    1.数据结构 程序=数据结构+算法 栈:后进先出,线性结构 入栈:push 出栈:pop假如已知入栈顺序是ab...

  • 05--栈 递归

    栈 栈(Stack)又名堆栈,它是一种重要的数据结构。从数据结构角度看,栈也是线性表,其特殊性在于栈的基本操作是线...

  • 栈内存和堆内存

    一、栈和堆: 栈steak(数据结构):一种后进先出的的数据结构 栈(操作系统):由编译器自动分配释放 ,存放函数...

  • 数据结构与算法 (栈实现篇)

    数据结构与算法 (栈实现篇) 在数据结构与算法中,栈(stack)又名堆栈,栈是一种受限的线性储存结构,只允许在一...

网友评论

      本文标题:数据结构(一) -- 栈

      本文链接:https://www.haomeiwen.com/subject/ennoettx.html