【数据结构】栈的代码实现

【数据结构】栈的代码实现 2022-05-16 314

栈是一种特殊的线性表, 只能在一端进行插入或者删除操作往栈中添加元素的操作，一般叫做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();
    }
}