动手实现基于数组的栈和队列

基础知识

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。

栈是一种后进先出（LIFO）的数据结构。

队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列是一种先进先出（FIFO）的数据结构。

制定手写方案

如果我们要手写一个栈或者队列，先要确定用什么数据结构保存数据，需要实现哪些功能？

选取数据结构

为了更好的理解栈和队列的原理，尽量采用简单的数据结构来保存数据，这样实现的逻辑会变得简单易懂，所以本次采用的是数组。

实现哪些功能

对于栈：

• 入栈和出栈
• 获取栈顶元素但不删除此元素
• 获取栈是否为空的方法
• 获取栈大小的方法

对于队列：

• 进队列和出队列
• 获取队列头元素但不删除此元素
• 获取队列是否为空的方法
• 获取队列大小的方法

使用数组实现栈：

import java.util.Arrays;
import java.util.EmptyStackException;


class Stack<E> {
    private E[] _data; // 数据
    private int _size; // 数组长度
    private int _realLength; // 数组已用长度

    @SuppressWarnings("unchecked")
    public Stack(int initSize) {
        this._size = initSize;
        this._data = (E[]) new Object[initSize];
        this._realLength = 0;
    }

    /**
     * 默认数组长度为20
     */
    public Stack() {
        this(20);
    }

    /**
     * 入栈
     *
     * @param element 添加的元素
     */
    public void push(E element) {
        if (size() >= _size) {
            grow();
        }
        _data[_realLength++] = element;
    }

    /**
     * 出栈
     *
     * @return 返回栈顶的元素
     */
    public E pop() {
        if (size() < 1) {
            throw new EmptyStackException();
        }
        E top = _data[_realLength - 1];
        _data[--_realLength] = null;
        return top;
    }

    /**
     * 获取栈顶元素
     *
     * @return 返回的是栈顶元素
     */
    public E peek() {
        if (size() < 1) {
            throw new EmptyStackException();
        }
        return _data[_realLength - 1];
    }

    /**
     * 判断栈是否为空栈
     *
     * @return true代表空栈
     */
    public boolean isEmpty() {
        return _realLength == 0;
    }

    /**
     * 栈的大小
     *
     * @return 大小值
     */
    public int size() {
        return _realLength;
    }

    /**
     * 数组的扩容，扩容大小为原先的2倍
     */
    private void grow() {
        // 扩容后size也要变化
        _size = _size * 2;
        _data = Arrays.copyOf(_data, _size);
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>(1);
        stack.push(0);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("stack is empty: " + stack.isEmpty());
        System.out.println("stack size is: " + stack.size());
        System.out.println("stack pop is: " + stack.pop());
        System.out.println("stack top is: " + stack.peek());
        // stack is empty: false
        // stack size is: 4
        // stack pop is: 3
        // stack top is: 2
    }
}

需要注意的几个点：

• 数组的扩容，做法是每次扩容原先长度的2倍
• 出栈后数组的变更，元素出栈后需要将之前的元素置空，便于 GC
• 对数组越界问题的把握，只要涉及到获取元素的操作，都需要对下标进行是否越界判断，可以返回 null，也可以直接抛出异常，具体看个人

使用数组实现队列：

import java.util.Arrays;
import java.util.NoSuchElementException;


/**
 * FIFO
 */
class Queue<E> {

    private E[] _data;
    private int _realLength;
    private int _size;

    @SuppressWarnings("unchecked")
    public Queue(int initSize) {
        this._data = (E[]) new Object[initSize];
        this._size = initSize;
        this._realLength = 0;
    }

    /**
     * 默认数组长度为20
     */
    public Queue() {
        this(20);
    }

    /**
     * 向队列尾端添加元素
     *
     * @param element 元素
     */
    public void offer(E element) {
        if (size() >= _size) {
            grow();
        }
        _data[_realLength++] = element;
    }

    /**
     * 取出队列头元素，并且从队列中删除它
     *
     * @return 头元素
     */
    public E poll() {
        if (isEmpty()) {
            throw new NoSuchElementException("queue is empty");
        }
        E first = _data[0];
        _data = Arrays.copyOfRange(_data, 1, _size);
        _realLength--;
        return first;
    }

    /**
     * 取出队列头元素，但是不删除它
     *
     * @return 头元素
     */
    public E element() {
        if (isEmpty()) {
            throw new NoSuchElementException("queue is empty");
        }
        return _data[0];
    }

    /**
     * 判断队列是否为空
     *
     * @return true代表空队列
     */
    public boolean isEmpty() {
        return _realLength == 0;
    }

    /**
     * 队列的大小
     *
     * @return 大小值
     */
    public int size() {
        return _realLength;
    }

    /**
     * 数组的扩容，扩容大小为原先的2倍
     */
    private void grow() {
        // 扩容后size也要变化
        _size = _size * 2;
        _data = Arrays.copyOf(_data, _size);
    }

    public static void main(String[] args) {
        Queue<Integer> queue = new Queue<Integer>();
        queue.offer(0);
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println("queue is empty: " + queue.isEmpty());
        System.out.println("queue size is: " + queue.size());
        System.out.println("queue poll: " + queue.poll());
        System.out.println("queue poll: " + queue.poll());
        System.out.println("queue poll: " + queue.poll());
        System.out.println("queue poll: " + queue.poll());
        // queue is empty: false
        // queue size is: 4
        // queue poll: 0
        // queue poll: 1
        // queue poll: 2
        // queue poll: 3
    }
}

使用数组来实现队列相比较栈更加的容易，添加元素、判空和 size() 两者都相似，只是在出队列的时候做法与出栈不相同而已，出队列出的是头部元素，也就是最先添加的元素，出队列之后需要重新调整数组，使用系统提供的 Arrays.copyOfRange(_data, 1, _size) 可轻松的复制数组一段元素。

手写栈和队列不仅可以用数组来实现，也可以用链表来实现，用链表可以可以更好的控制添加和删除操作，毕竟链表采用的是指针方案。有兴趣的可以自行实现一波。

如果本文章你发现有不正确或者不足之处，欢迎你在下方留言或者扫描下方的二维码留言也可！