数据结构（JAVA）栈-EW帮帮网

1. 栈

栈是一种特殊的线性表，只允许在一端进行插入和删除元素操作。他的操作顺序是先进后出。

栈顶：进行插入和删除元素操作的一端。

栈顶：不进行任何操作。

压栈：栈的插入操作。

出栈：栈的删除操作。

2. 栈的模拟实现

栈可以使用顺序表来实现，也可以使用链表来实现。

2.1 用顺序表实现的栈

2.1.1 栈的接口

public class MyStack {
    public int[] elem;
    public int usedSize;
    //构造方法
    public MyStack() {}
    //入栈
    public void push(int val) {}
    //出栈
    public int pop() {}
    //获取栈顶元素，但不删除
    public int peek() {}
    //判满
    private boolean isFull() {}
    //判空
    public boolean isEmpty() {}
}

2.1.2 栈的成员变量

用数组来表示栈，usedSize来表示栈中元素个数。

public int[] elem;
public int usedSize;

2.1.3 栈的构造方法

在构造方法中我们先开劈10个int空间。

    public MyStack() {
        this.elem = new int[10];
    }

2.1.4 入栈

思路：

1. 首先判断数组是否已满，已满进行扩容。

2. 进行元素插入，再usedSize++;

    public void push(int val) {
        if(isFull()) {
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;
    }

2.1.5 出栈

思路：

1. 首先判断数组是否为空，为空异常。

2. 再usedSize-- ，并返回usedSize下标的元素。

public int pop() {
    if(isEmpty()) {
       throw new StackEmptyException();
    }
    usedSize--;
    return elem[usedSize];
}

2.1.6 获取栈顶元素，但不删除

思路：

1. 判断判断数组是否为空，为空异常。

2. 返回 usedSize-1下标的元素。

    public int peek() {
        if(isEmpty()) {
            throw new StackEmptyException();
        }
        return elem[usedSize-1];
    }

2.1.7 判满

判断数组的长度是否等于usedSize。

    private boolean isFull() {
        return this.elem.length == usedSize;
    }

2.1.8 判空

判断usedSize是否等于零。

    public boolean isEmpty() {
        return usedSize == 0;
    }

2.2 用链表实现栈

由于栈的先入后出的特性，如果我们使用单向链表，那么要拿到最后节点，它的时间复杂度为O(n)，所以使用双向链表。

2.2.1 栈的接口

public class MyStack {
   static class ListNode {
      public ListNode next;
      public ListNode prev;
      public int val;

      public ListNode(int val) {
        this.val = val;
      }
    }
    public ListNode first;
    public ListNode last;
    //入栈
    public void push(int val) {}
    //出栈
    public int pop() {}
    //获取栈顶元素，但不删除
    public int peek() {}
    //判空
    public boolean isEmpty() {}
}

2.2.2 内部类

和双向连表差不多。

    static class ListNode {
        public ListNode next;
        public ListNode prev;
        public int val;

        public ListNode(int val) {
            this.val = val;
        }
    }

2.2.3 入栈

思路：

1. 判断栈是否为空，为空头结点，尾结点同时指向node结点。

2. 否则就进行尾插。

    public void push(int val) {
        ListNode node = new ListNode(val);
        if(isEmpty()) {
            first = last = node;
        }
        last.next = node;
        node.prev = last;
        last = node;
    }

2.2.4 出栈

思路:

1. 判断栈是否为空，为空直接抛异常。

2. 否则把尾结点删除。

3. 最后返回删除之前尾结点的数值。

    public int pop() {
        if(isEmpty()) {
            throw new StackEmptyException();
        }
        int val = last.val;
        last.prev.next = null;
        last = last.prev;
        return val;
    }

2.2.5 获取栈顶元素，但不删除

思路：

1. 判断栈是否为空，为空直接抛异常。

2. 返回尾结点的数值。

    public int peek() {
        if(isEmpty()) {
            throw new StackEmptyException();
        }
        int val = last.val;
        return val;
    }

2.2.6 判空

判断头节点是否为空。

    public boolean isEmpty() {
        return first == null;
    }

3. JAVA中的栈

Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表。

实现了Serializable接口，可序列化

实现了Cloneable 接口，可克隆

实现了RandomAccess接口，可随机访问

数据结构（JAVA）栈