数据结构与算法 | 栈

栈

定义

线性表中的一种特殊数据结构，数据只能从固定的一端插入数据或删除数据，另一端是封死的。

特点

• FILO（First In Last Out）: 先进后出
• 栈满还存会“上溢”，栈空再取会“下溢”

分类

顺序栈

特点

• 采用数组实现，数据在物理结构上保持连续性。

代码实现

package one.wangwei.algorithms.datastructures.stack.impl;

import one.wangwei.algorithms.datastructures.stack.IStack;

import java.util.Arrays;

/**
 * 顺序栈
 *
 * @param <T>
 * @author wangwei
 * @date 2018/05/04
 */
public class ArrayStack<T> implements IStack<T> {

    /**
     * 默认大小
     */
    private static final int DEFAULT_SIZE = 10;
    /**
     * 数组
     */
    private T[] array = (T[]) new Object[DEFAULT_SIZE];
    /**
     * 大小
     */
    private int size;

    /**
     * 入栈
     *
     * @param value
     * @return
     */
    @Override
    public boolean push(T value) {
        if (size >= array.length) {
            grow();
        }
        array[size] = value;
        size++;
        return false;
    }

    /**
     * 扩容50%
     */
    private void grow() {
        int growSize = size + (size << 1);
        array = Arrays.copyOf(array, growSize);
    }

    /**
     * 压缩50%
     */
    private void shrink() {
        int shrinkSize = size >> 1;
        array = Arrays.copyOf(array, shrinkSize);
    }

    /**
     * 出栈
     *
     * @return
     */
    @Override
    public T pop() {
        if (size <= 0) {
            return null;
        }
        T element = array[--size];
        array[size] = null;

        int shrinkSize = array.length >> 1;
        if (shrinkSize >= DEFAULT_SIZE && shrinkSize > size) {
            shrink();
        }
        return element;
    }

    /**
     * 查看栈顶值
     *
     * @return
     */
    @Override
    public T peek() {
        if (size <= 0) {
            return null;
        }
        return array[size - 1];
    }

    /**
     * 删除元素
     *
     * @param value
     * @return
     */
    @Override
    public boolean remove(T value) {
        if (size <= 0) {
            return false;
        }
        for (int i = 0; i < size; i++) {
            T t = array[i];
            if (value == null && t == null) {
                return remove(i);
            }
            if (value != null && value.equals(t)) {
                return remove(i);
            }
        }
        return false;
    }

    /**
     * 移除 index 处的栈值
     *
     * @param index
     * @return
     */
    private boolean remove(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index != --size) {
            System.arraycopy(array, index + 1, array, index, size - index);
        }
        array[size] = null;

        int shrinkSize = array.length >> 1;
        if (shrinkSize >= DEFAULT_SIZE && shrinkSize > size) {
            shrink();
        }
        return true;
    }

    /**
     * 清空栈
     */
    @Override
    public void clear() {
        if (size <= 0) {
            return;
        }
        for (int i = 0; i < size; i++) {
            array[i] = null;
        }
        size = 0;
        array = null;
    }

    /**
     * 是否包含元素
     *
     * @param value
     * @return
     */
    @Override
    public boolean contains(T value) {
        if (size <= 0) {
            return false;
        }
        for (int i = 0; i < size; i++) {
            T t = array[i];
            if (value == null && t == null) {
                return true;
            }
            if (value != null && value.equals(t)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 栈大小
     *
     * @return
     */
    @Override
    public int size() {
        return size;
    }
}

查看源码

链表栈

特点

• 用线性表的链式结构存储，数据在物理结构上非连续

代码实现

package one.wangwei.algorithms.datastructures.stack.impl;

import one.wangwei.algorithms.datastructures.stack.IStack;

/**
 * 链表栈
 *
 * @param <T>
 * @author wangwei
 * @date 2018/05/04
 */
public class LinkedStack<T> implements IStack<T> {

    private Node<T> top;
    private int size;

    public LinkedStack() {
        this.top = null;
        this.size = 0;
    }

    /**
     * 入栈
     *
     * @param value
     * @return
     */
    @Override
    public boolean push(T value) {
        Node<T> newTop = new Node<>(value);
        if (top == null) {
            top = newTop;
        } else {
            Node<T> oldTop = top;
            top = newTop;
            oldTop.above = top;
            top.below = oldTop;
        }
        size++;
        return true;
    }

    /**
     * 出栈
     *
     * @return
     */
    @Override
    public T pop() {
        if (top == null) {
            return null;
        }

        Node<T> needTop = top;
        top = needTop.below;
        if (top != null) {
            top.above = null;
        }

        T needValue = needTop.element;
        needTop = null;

        size--;
        return needValue;
    }

    /**
     * 查看栈顶值
     *
     * @return
     */
    @Override
    public T peek() {
        return top == null ? null : top.element;
    }

    /**
     * 删除元素
     *
     * @param value
     * @return
     */
    @Override
    public boolean remove(T value) {
        if (top == null) {
            return false;
        }
        Node<T> x = top;
        if (value == null) {
            while (x != null && x.element != null) {
                x = x.below;
            }
        } else {
            while (x != null && !value.equals(x.element)) {
                x = x.below;
            }
        }
        return remove(x);
    }

    /**
     * 删除一个节点
     *
     * @param node
     * @return
     */
    private boolean remove(Node<T> node) {
        if (node == null) {
            return false;
        }
        Node<T> above = node.above;
        Node<T> below = node.below;

        // 删除中间元素
        if (above != null && below != null) {
            above.below = below;
            below.above = above;
        }
        // 删除top元素
        else if (above == null && below != null) {
            top = below;
            top.above = null;
        } else if (above != null && below == null) {
            above.below = null;
            below = null;
        } else {
            top = null;
        }
        node = null;
        size--;
        return true;
    }

    /**
     * 清空栈
     */
    @Override
    public void clear() {
        if (top == null) {
            return;
        }
        for (Node<T> x = top; x != null; ) {
            Node<T> below = x.below;
            x.element = null;
            x.above = null;
            x.below = null;
            x = below;
        }
        top = null;
        size = 0;
    }

    /**
     * 是否包含元素
     *
     * @param value
     * @return
     */
    @Override
    public boolean contains(T value) {
        if (value == null) {
            for (Node<T> x = top; x != null; x = x.below) {
                if (x.element == null) {
                    return true;
                }
            }
        } else {
            for (Node<T> x = top; x != null; x = x.below) {
                if (x.element.equals(value)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 栈大小
     *
     * @return
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 节点
     *
     * @param <T>
     */
    private static class Node<T> {
        private T element;
        private Node<T> above;
        private Node<T> below;

        public Node(T element) {
            this.element = element;
        }
    }
}

查看源码

参考资料

• http://data.biancheng.net/view/9.html