专栏首页wfaceboss栈的基本实现

栈的基本实现

1.栈的定义

栈是一种“先进后出”的一种线性数据结构,有压栈出栈两种操作方式。如下图:

2.栈的分类

栈主要分为两类:

  • 静态栈
  • 动态栈

【静态栈】

静态栈的核心是数组,类似于一个连续内存的数组,我们只能操作其栈顶元素。

【动态栈】

静态栈的核心是数组,类似于一个连续内存的数组,我们只能操作其栈顶节点。

 此节我们在我们之前封装的动态数组的基础上(引用封装好的动态数组),实现基本的栈操作。

3.栈实现

1.先定义一个接口Stack包括相关栈的基本操作

package Stack;

public interface Stack<E> {

    //栈中元素个数
    int getSize();

    //栈中元素个数是否为空
    boolean isEmpty();

    //进栈
    void push(E e);

    //出栈
    E pop();

    //查看栈顶元素
    E peek();
}

2.创建一个ArrayStack类实现接口

package Stack;

import Array.DynamicArray;

public class ArrayStack<E> implements Stack<E> {
    DynamicArray<E> array;

    //构造函数,传入栈的容量capacity构造函数
    public ArrayStack(int capacity) {
        array = new DynamicArray<E>(capacity);
    }

    //无参构造函数,默认栈的容量capacity=10
    public ArrayStack() {
        array = new DynamicArray<E>();
    }

    //获取栈中元素个数
    @Override
    public int getSize() {
        return array.getSize();
    }

    //获取栈中元素数据是否为空
    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    //获取栈的容量
    public int getCapacity() {
        return array.getCapacity();
    }

    //进栈操作
    @Override
    public void push(E e) {
        array.addLast(e);
    }

    //出栈操作
    @Override
    public E pop() {
        return array.removeLast();
    }

    //查看栈顶元素
    @Override
    public E peek() {
        return array.getLast();
    }

    //重写object类的toString方法
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack:");
        res.append('[');
        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize() - 1) {
                res.append(",");
            }
        }
        res.append("] top");//体现右侧为栈顶
        return res.toString();
    }

}

3.测试栈操作是否正确

新建一个类,包含main函数

(1)进栈操作

package Stack;

public class TestMain {
    public static void main(String[] args) {
        ArrayStack<Integer> stack = new ArrayStack<Integer>();
        for (int i = 0; i < 5; i++) {
            stack.push(i);
            System.out.println(stack);
        }
      
    }

}

结果为:

(2)出栈操作

 System.out.println("出栈");
 stack.pop();
 System.out.println(stack);

结果为:

4.栈的复杂度分析

有了我们关于动态数组复杂度分析的知识,在加上此处的栈是基于动态数组实现的,复杂度的分析方式是一致的。

源码地址 https://github.com/FelixBin/dataStructure/tree/master/out/test/structure/Stack

我的博客即将同步至腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=1h4cn9zbb1k0x

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • c#6.0特性

    (2)表达式属性(只有一个get访问器的单行属性,可以使用lambda表达式语法编写)

    wfaceboss
  • 2.简单工厂方法模式

    总结:该种方法是常用的面向细节的编程方法,具体操作的类可见,但是,当普通中的类名发生改变时,所有调用该类的类都需要进行修改,否则错误。

    wfaceboss
  • java中的排序(自定义数据排序)--使用Collections的sort方法

        当引用类型的内置排序方式无法满足需求时可以自己实现满足既定要求的排序,有两种方式:

    wfaceboss
  • java概念1

    public static void main(String[] args) {//其中[]也可以写在args后面,args也可以随便写成其他字母,例如asd...

    闵开慧
  • C++项目中采用CLR的方式调用C#编写的dll

    1、注意事项:在编写C#DLL类库时,最好不要出现相同的命名空间,否则在C++中调用可能会出现编译错误。 2、将C#的源码生成的“dll”文件复制到C++项目中...

    指尖改变世界
  • 排序算法总结

    Kevin_Zhang
  • java数组实现相关方法

    import com.sun.corba.se.impl.orbutil.graph.Node; import com.sun.corba.se.spi.pre...

    张俊怡
  • 教妹学Spring:Aware、异步编程、计划任务

    你好呀,我是沉默王二,一个和黄家驹一样身高,刘德华一样颜值的程序员(不信围观朋友圈呗)。从 2 位偶像的年纪上,你就可以断定我的码龄至少在 10 年以上,但实话...

    沉默王二
  • Spring实战——XML和JavaConfig的混合配置

    前言 看了园龄已经两年多了,再不能写完内容直接点击发布,留下一片密密麻麻的文字让别人看的头昏脑涨。所以现在每次写完主要内容后,还需要对于格式稍稍调整下。那么有没...

    JackieZheng
  • TestNG 三 测试方法

    测试方法是可以带有参数的。每个测试方法都可以带有任意数量的参数,并且可以通过使用TestNG的@Parameters向方法传递正确的参数。

    流柯

扫码关注云+社区

领取腾讯云代金券