自己实现集合框架(十):顺序栈的实现

内容简介：自己实现集合框架(十):顺序栈的实现

这是系列文章，每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现，从而对常用的数据结构和 java 集合有个大概的了解。当然实现没有 java 集合的实现那么复杂，功能也没有那么强大，但是可以通过这些简单的实现窥探到底层的一些共性原理。

一. 顺序栈

二. 顺序栈实现

1. 定义顺序栈

在前面的文章 自己实现集合框架(十一):栈接口 中已经定义了栈接口，顺序栈类 SeqStack 实现栈接口SStack类，并实现栈接口中定义的方法，代码如下所示：

package org.light4j.dataStructure.linearList.stack.sequence;

import org.light4j.dataStructure.linearList.stack.SStack;

public class SeqStack<E> implements SStack<E> {
    private Object[] value;// 储存栈的数据元素的数组
    private int top;// 栈顶元素下标

    public SeqStack() {// 构造默认容量的空栈
        this(16);// 初始化栈的容量为16
    }

    public SeqStack(int capacity) {// 构造指定容量的空栈
        this.value = new Object[Math.abs(capacity)];
        this.top = -1;// 栈顶下标初始化为-1
    }
}

代码解释：

①定义了两个构造函数，一个无参的构造函数，栈的容量默认是 16 ，另外一个有参的构造函数，可以指定栈的容量。

② Math.abs(capacity) 取栈容量的绝对值，做容错处理，防止传入负数的情况。

2. 判断栈是否为空

/**
     * 判断栈是否为空，若为空则返回true
     * 
     * @return
     */
    @Override
    public boolean isEmpty() {
        return this.top == -1;
    }

代码解释：

①判断栈是否为空的条件是根据栈顶元素的索引 top 是否为 -1 作为依据。

3. 入栈

/**
     * 元素入栈，成为新的栈顶元素，若操作成功返回true
     */
    @Override
    public boolean push(E element) {
        if (element == null) {// 元素不允许为空
            return false;
        }
        if (this.top == value.length - 1) {// 栈满则需要扩充容量
            Object[] temp = this.value;
            this.value = new Object[temp.length * 2];// 扩充数组容量为原来的数组容量的两倍
            for (int i = 0; i < temp.length; i++) {// 复制元素到新的数组
                this.value[i] = temp[i];
            }
        }
        this.top++;// 栈顶加1
        this.value[top] = element;// 把入栈的元素置于栈顶
        return true;
    }

4.出栈

/**
     * 元素出栈，返回当前栈顶元素，栈顶元素改变，若栈为空则返回null
     */
    @SuppressWarnings("unchecked")
    @Override
    public E pop() {
        if (isEmpty()) {// 如果是空栈则返回null
            return null;
        }
        return (E) this.value[top--];// 取出栈顶元素,栈顶元素改变,top减1
    }

5. 取栈顶元素

/**
     * 取栈顶元素值，元素未出栈，栈顶元素未改变
     */
    @SuppressWarnings("unchecked")
    @Override
    public E get() {// 如果是空栈则返回null
        if (isEmpty()) {
            return null;
        }
        return (E) this.value[top];// 返回栈顶元素，栈顶元素未改变,top不变
    }

6.重写 toString() 方法

/**
     * 返回栈中各元素的字符串表示
     */
    @Override
    public String toString() {
        String str = "(";
        for (int i = top; i >= 0; i--) {// 从栈顶开始遍历
            if (this.value[i] != null) {
                if (i == 0) {// i为0则是栈底元素
                    str += this.value[i];
                    // break;// 遍历完栈顶元素跳出循环
                } else {
                    str += this.value[i] + ",";
                }
            }
        }
        return str + ")";
    }

代码解释：

①返回栈中各元素的字符串表示，从栈顶开始遍历到栈底元素结束。

三. 测试

package org.light4j.dataStructure.linearList.stack.sequence;

import org.light4j.dataStructure.linearList.stack.SStack;

public class Test {
    public static void main(String[] args) {
        SStack<String> stack = new SeqStack<String>();
        System.out.println(stack.isEmpty());//判空
        stack.push("A");//入栈
        stack.push("B");
        stack.push("C");
        System.out.println(stack.toString());
        stack.pop();// 出栈
        stack.push("D");
        stack.get();// 取栈顶元素
        System.out.println(stack.toString());
        System.out.println(stack.isEmpty());//判空
    }
}

四.时间复杂度分析

由于栈只能在栈顶位置进行插入和删除，所以入栈 push() ，出栈 pop() 和获取栈顶元素 get() 的时间复杂度为 O(1) ，当需要扩充容量时，入栈操作 push() 的时间复杂度为 O(n) 。

五.源代码示例

github 地址： 点击查看

码云地址： 点击查看

欢迎关注人生设计师的微信公众账号

公众号ID：longjiazuoA

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

• QMQ 顺序消息设计与实现（上）
• 灵机一动之优雅实现用例顺序插入
• PHP 内部如何实现打乱字符串顺序函数 str_shuffle
• ViewGroup 默认顺序绘制子 View，如何修改？什么场景需要修改绘制顺序？
• JavaScript万物产生顺序
• SpringBoot配置加载顺序

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。