同系列文章导读:【数据结构与算法】导读

所有文章均在本博客首发,其他平台同步更新

如有问题,欢迎指正(评论区留言即可)

发表评论时请填写正确邮箱,以便于接收通知【推荐QQ邮箱】

本文参考整理自小码哥的《恋上数据结构和算法》课程,图片转自课程ppt,如有侵权,请联系删除~

  • 栈是一种特殊的线性表, 只能在一端进行插入或者删除操作
  • 往栈中添加元素的操作,一般叫做push入栈
  • 从栈中移除元素的操作,一般叫做pop出栈(只能移除栈顶的元素)
  • 成员变量无非就是size和一个element数组或者链表作为存储元素的容器

接口设计

因为栈是只能在一端进行操作,也就是说除了最上面的元素用户可见,其余元素用户并不可见

因此可以知道栈的基本操作如下:

public class Stack<E> {
    // 元素的数量
    public int size();
    // 是否为空
    public boolean isEmpty();
    // 入栈
    public void push(E element);
    // 出栈
    public E pop();
    // 获取栈顶元素
    public E top();
    // 清空栈内元素
    public void clear();
}
  • 由上面的接口可以看到,基本上是前面做过的动态数组或链表的子集
  • 因此,在实现栈的操作时,我们可以对之前的动态数组双向链表进行再封装
  • 可以想到的是两种实现方式

    • 继承动态数组或双向链表
    • 将动态数组或者双向链表作为成员变量

代码实现

继承方式

继承方式会拿到父类所有非私有变量和方法,所以这里不需要再在Stack类中定义size变量和一些与父类相同的方法

只需要对有变化的方法进行重写或者新增父类中没有的方法

import top.hellocode.List.List;

/**
 * @author HelloCode
 * @site https://www.hellocode.top
 * @date 2022年05月16日 10:44
 */
public class Stack<E> extends ArrayList {

    // 入栈
    public void push(E element){
        add(element);
    }

    // 出栈
    public E pop(){
        return (E) remove(size - 1);
    }

    // 获取栈顶元素
    public E top(){
        return (E) get(size - 1);
    }
}

继承中有一个问题,虽然我们Stack类中只实现了这几个符合栈逻辑的方法

但是在调用Stack中的方法时,还可以拿到父类中所有的非私有方法,这样就会导致栈并不太符合逻辑

包含方式

除了使用继承,还可以将双向链表或者动态数组作为成员变量(私有)

Stack中的方法,通过调用成员变量的方法来实现

package top.hellocode.Stack;

import top.hellocode.List.ArrayList;
import top.hellocode.List.List;

/**
 * @author HelloCode
 * @site https://www.hellocode.top
 * @date 2022年05月16日 10:44
 */
public class Stack<E> {
    private List<E> list = new ArrayList<>();
  
    // 元素的数量
    public int size() {
        return list.size();
    }

    // 是否为空
    public boolean isEmpty() {
        return list.isEmpty();
    }

    // 入栈
    public void push(E element) {
        list.add(element);
    }

    // 出栈
    public E pop() {
        return list.remove(list.size() - 1);
    }

    // 获取栈顶元素
    public E top() {
        return list.get(list.size() - 1);
    }

    // 清空
    public void clear() {
        list.clear();
    }
}
用这种方式实现的栈就只能调用我们所设计的方法,符合栈逻辑。这种设计方式也是目前主流使用的一种

END

本文作者: 文章标题:【数据结构】栈的代码实现
本文地址:https://www.hellocode.top/archives/107/
版权说明:若无注明,本文皆HelloCode原创,转载请保留文章出处。
最后修改:2022 年 05 月 16 日
如果觉得我的文章对你有用,请随意赞赏