搜 索

Java数据结构基础丨栈

  • 363阅读
  • 2021年02月20日
  • 0评论
首页 / 默认分类 / 正文

前言

数据结构从大的方向上分,可以分为逻辑结构和物理结构。逻辑结构是抽象的概念,它依赖于物理结构而存在。

  1. 物理结构可划分为:顺序存储结构与链式存储结构。

    • 顺序存储结构:把数据元素存放在地址连续存储单元里,其数据间的逻辑关系和物理关系是一致的。例如数组
    • 链式存储结构:其中逻辑关系和物理关系没有多大的关系,因为其中的数据元素会产生变化。链式存储结构是把数据元素存放在任意的存储单元里,存储单元可以是连续的也可以是不连续的。当然也比顺序存储结构更加灵活。例如链表
  2. 逻辑结构可划分为:线性结构与非线性结构。

    • 线性结构:顾名思义,一条线性的结构,元素间的关系就是一对一的。例如线性表队列
    • 非线性结构:包括树形结构、图形结构等。例如

栈的基本知识

栈,stack,又称堆栈,是一种线性结构。与数组相比,访问它的元素是受限制的:栈只能在同一端(栈顶)进行操作,且只允许访问一个数据项,即最后插入的数据项。栈中的元素只能先入后出(First In Last Out,简称FILO),最先进入的元素存放的位置叫栈底,最后进入的元素存放的位置叫栈顶

生活中也不缺可以体现出栈的特点的设计/例子,例如:老师批改一叠作业,正常情况下都是先拿起最上面的一本,处理完这本之后,再去批改下一本,从上到下,直到被压在最后的一本,但是最后一本是最开始放的。例如:兵乓球圆筒的一端封闭,另一端开口。往圆筒放入兵乓球,先放入的在圆筒底部,后放入的靠近圆筒入口。在圆筒直径条件限制下,只能按放入顺序相反的顺序取球。

栈的基本操作

  1. 入栈(push),就是把一个新元素放入栈中,只允许从栈顶一侧放入,下一个新元素放入的位置将成为新的栈顶。
  2. 出栈(pop),就是把一个元素从栈中弹出,只有栈顶的元素才允许弹出,出栈元素的前一个元素将成为新的栈顶。
  3. peek(),查看栈顶部的对象,但不对栈做任何改动。
  4. size(),返回栈内元素的大小。
  5. isEmpty(),测试栈是否为空,返回布尔值。
  6. isFull(),测试栈是否为满,返回布尔值。

栈的实现

栈既可以用数组来实现,也可以用链表来实现。注意,如果用数组来实现,需要先规定栈的大小;如果用链表来实现,则不需要先规定栈的容量。

数组实现
链表实现

class ArrayStack {
    // 最大长度
    private int maxSize;
    // 栈顶索引
    private int top;
    // 用于存储元素的数组
    private int[] stackArray;

    public ArrayStack(int val){
        maxSize = val;
        stackArray = new int[maxSize];
        top = -1;
    }
    // 栈空
    public boolean isEmpty(){
        return (top == -1);
    }
    // 栈满
    public boolean isFull(){
        return (top == maxSize - 1);
    }
    // 入栈
    public void push(int x){
        if (isFull()){
            throw new RuntimeException("栈已满!");
        }
        stackArray[++top] = x;
    }
    // 出栈
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("栈是空的!");
        }
        return stackArray[top--];
    }
    // 查看栈顶
    public int peek(){
        return stackArray[top];
    }
    // 长度
    public int size(){
        return top + 1;
    }
    // 遍历输出:输出顺序与输入顺序相反
    public void show(){
        if (isEmpty()){
            System.out.println("栈是空的!");
        }else {
            int temp = top;
            while (temp != -1) {
                System.out.println(stackArray[temp]);
                System.out.print(" ");
                temp--;
            }
        }
    }
}

class LinkStack<T>{
    // 栈顶
    private Node top;
    // 长度
    private int size = 0;
    // 节点
    private class Node{
        // 数据
        private T data;
        // next指针
        private Node next;
        public Node(T data){
            this.data = data;
        }
    }
    // 创建
    public LinkStack(){
        top = new Node(null);
    }
    // 栈空,链表没有定义存储限制,所以没有栈满
    public boolean isEmpty(){
        if (top.next == null){
            return true;
        }
        return false;
    }
    // 入栈
    public void push(T data){
        if (isEmpty()){
            top.next = new Node(data);
        }else{
            Node newNode = new Node(data);
            newNode.next = top.next;
            top.next = newNode;
        }
        size++;
    }
    // 出栈
    public T pop(){
        if (isEmpty()){
            System.out.println("栈是空的!");
            return null;
        }else {
            T val = top.next.data;
            top.next = top.next.next;
            size--;
            return val;
        }
    }
    // 获取栈顶元素
    public T peek(){
        if (isEmpty()){
            return null;
        }else{
            return top.next.data;
        }
    }
    // 栈的长度
    public int size(){
        return size;
    }
    // 输出
    public void show(){
        Node temp = top;
        if (isEmpty()){
            System.out.println("栈是空的!");
        }else{
            while(temp.next != null){
                temp = temp.next;
                System.out.print(temp.data + " ");
            }
        }
    }
}

栈的应用及效率

栈是一个重要的数据结构,其特性简而言之就是“先进后出”,可以用它辅助遍历二叉树的节点,也可以用它辅助查找图的顶点。
在计算机中,大部分微处理器运用基于栈的体系结构。在windows等大部分操作系统中,每个运行中的二进制程序都配有一个调用栈(Call Stack)和执行栈(Execution Stack)。当调用一个方法时,把它的返回地址和参数压入栈,方法结束返回时,那些数据就出栈,栈操作就嵌入在微处理器中。

  1. 用栈实现单词逆序;
  2. 中缀表达式求值;
  3. 实现十进制数和其他n进制数的转换;
  4. 用于解析某种类型的文本串,实现分隔符匹配;
  5. ......

栈操作所耗时间不依赖于栈中数据项的个数,因为入栈、出栈都是只影响到最后一个元素,不涉及比较和移动操作,所以无论是数组实现还是链表实现的,数据项入栈、出栈的时间复杂度都是常数级O(1)

打 赏
  • 支付宝
  • 微信
Alipay
WeChatPay
评论区
暂无评论
avatar