数据结构（三）用两种方式简单实现栈

数据结构（一）数组实现一个简单的ArrayList
数据结构（二）链表实现LinkedList
数据结构（三）用两种方式简单实现栈
数据结构（四）栈和队列的简单应用
数据结构（五）用两种方式简单实现队列
数据结构（六）BST二分搜索树（上）
数据结构（六）BST二分搜索树（下）
数据结构（七）两种方式实现set
数据结构（八）两种方式实现map
数据结构（九）set解决LeetCode349号问题

栈这个数据结构很奇特，像是一水桶，先进来的最后才能出去。但是他的用处很广。我们来简单的实现一个自己的栈。话不多说，下边是源码。

先贴一下栈的几个简单的方法

public interface Stack<E> {

    int size();
    boolean isEmpty();
    //进栈
    void push(E e);
    //出栈
    E pop();
    //获取栈顶元素
    E peek();
}

下边用两种方式实现栈

• 第一种是之前咱们自己实现的arraylist

public class ArrayStack<E> implements Stack<E> {

    Array<E> array;

    public ArrayStack(int capacity){
        array = new Array<>(capacity);
    }
    public ArrayStack(){
        array = new Array<>();
    }

    @Override
    public int size() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    public int getCatacity(){
        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();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        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();
    }
}

这里的源码其实很简单，因为大部分工作在之前的ArrayList里已经实现的了
-下边是第二中实现方法是用链表实现的。

/**
 * 链表栈
 * @param <E>
 */
public class LinkedListStack<E> implements Stack<E> {

    private DummyLinkedList<E> linkedList;

    public LinkedListStack() {
        linkedList = new DummyLinkedList<>();
    }

    @Override
    public int size() {
        return linkedList.getSize();
    }

    @Override
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

    @Override
    public void push(E e) {
        linkedList.addFirst(e);
    }

    @Override
    public E pop() {
        return linkedList.removeFirst();
    }

    @Override
    public E peek() {
        return linkedList.getFirst();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack : Top");
        res.append(linkedList);
        return res.toString();
    }

  
}

这里也很简单。大部分工作也是之前的LinkedList实现了。

• 下边会出一个栈的应用的文章，希望大家多多关注支持。