大话数据结构（三）— 栈的两种java实现方式

栈：限定仅在表尾进行插入和删除操作的线性表。栈是一种后进先出的结构,我们将允许插入和删除的一端称为栈顶（top），而另一端就称之为栈底（bottom），当栈中无任何数据元素时称作空栈。

栈是一个线性表，它具有线性关系，即前驱后继的关系。由于栈限定了线性表插入和删除的位置，所以栈底也是固定的。在线性表中表头是栈底，表我是栈顶。最先入栈的只能在栈底。下面我们来看看栈的两种操作——进栈和出栈：

1.栈的顺序存储结构

用数组存放数据，top变量来指示栈顶元素在数组中的位置（栈顶指针）。一个长度为5的栈的示意图如下：

实验程序：

package com.tongcaipay.merchant.apply.study;
import java.util.Arrays;
/**
 * * 顺序栈
 * Created by xiaolei on 19-08-27
 */
public class ArrayStack<T> {
    private final int DEFAULT_SIZE = 10;   //设置默认尺寸
    private int capacity;  //保存当前数组长度
    private int addCapacity; //设置当超出原数组长度时增加的长度
    private Object[] elements; //初始化顺序栈数组
    private int size; //保存顺序栈中元素的个数


    //创建默认长度的空顺序栈
    public ArrayStack(){
        capacity = DEFAULT_SIZE;
        elements = new Object[capacity];
    }

    //创建指定长度的空顺序栈
    public ArrayStack(int capacity){
        this.capacity = capacity;
        elements = new Object[capacity];
    }

    /**
     * 创建指定长度的空顺序栈，并指定超出数组范围后的增量
     * @param capacity 设置指定长度
     * @param addCapacity 设置增量
     */
    public ArrayStack(int capacity,int addCapacity) {
        this.capacity = capacity;
        this.addCapacity = addCapacity;
        elements = new Object[capacity];
    }

    //获取顺序栈的长度
    public int getSize(){
        return size;
    }

    //判断顺序栈是否为空栈
    public boolean isEmpty(){
        return size == 0;
    }

    //确保数组长度，如果超出就进行拓展
    private void ensureCapacity(int inputCapacity){
        //如果输入的数组长度大于原有数组的长度
        if (inputCapacity > capacity){
            //若果有设定数组增量
            if(addCapacity > 0){
                while (inputCapacity > addCapacity)
                    capacity += inputCapacity;
            } else{
                while (inputCapacity > addCapacity)
                    capacity <<= 1;
            }
            //扩容后，将原数组复制到新数组中
            elements = Arrays.copyOf(elements, capacity);
        }
    }

    //进栈
    public void push(T element){
        //确保数组长度
        ensureCapacity(size+1);
        //元素进栈
        elements[size++] = element;
    }

    //出栈
    //同时返回弹出的元素
    public T pop(){
        //如果是空栈
        if (isEmpty())
            return null;
        T element = (T) elements[size-1];
        //释放栈顶元素并将长度减一
        elements[--size] = null;
        return element;
    }

    //获取栈顶元素
    public T getTop() {
        return (T) elements[size - 1];
    }

    //清空顺序栈
    public void clear(){
        for (int i = 0;i<size;i++)
            elements[i] = null;
        size = 0;
    }

    public String toString(){
        if(isEmpty())
            return "[]";
        else {
            //实例化对sb,构造方法

            StringBuilder sb = new StringBuilder("[");  //StringBuilder 的内容是可变的
            for (int i = size -1;i>=0;i--)
                sb.append(elements[i].toString()+" ");  //链式编程.append特点:能放很多类型的数据
            sb.append("]");
            int len = sb.length();
            return sb.delete(len - 2,len - 1).toString();
        }
    }

测试代码:

    public static void main(String[] args) {
        ArrayStack<String> ll = new ArrayStack<String>();
        System.out.println("原栈中的元素： "+ll);
        System.out.println("----------进栈----------");
        //压栈
        ll.push("haha");
        ll.push("hehe");
        ll.push("xixi");
        ll.push("hiahia");
        ll.push("heihei");
        System.out.println("压栈后栈中所含元素： "+ll);
        //获取栈顶元素
        System.out.println("栈顶元素为： "+ll.getTop());
        //获取栈中元素个数
        System.out.println("当前栈中元素个数为： "+ll.getSize());
        //出栈
        System.out.println("----------出栈----------");
        ll.pop();
        System.out.println("出栈后栈中所含元素： "+ll);
        //获取栈顶元素
        System.out.println("栈顶元素为： "+ll.getTop());
        //获取栈中元素个数
        System.out.println("当前栈中元素个数为： "+ll.getSize());
    }
}

测试结果：

2.栈的链式存储结构

下面我们再来看看链栈，
链栈的入栈操作如图：

链栈的出栈如下图：

实验程序：

package com.tongcaipay.merchant.apply.study;

public class LinkListStack<T> {

    //定义一个内部类 Node 表示单链表的结点
    private class Node {
        private T element;
        private Node next;

        //初始化空构造器
        
        public Node() {

        }

        //初始化含参数构造器
        public Node(T element, Node next) {
            this.element = element;
            this.next = next;
        }
    }

    private Node top;//存放栈顶结点
    private int size;//存放栈中结点数

    //初始化空栈
    public LinkListStack() {
    }

    //获取栈长度
    public int getSize() {
        return size;
    }

    //判断栈是否为空栈
    public boolean isEmpty() {
        return size == 0;
    }

    public void push(T element) {
        //进栈时,新结点的后驱指针next指向旧top
        Node newNode = new Node(element, top);
        //进来的新结点更新为top
        top = newNode;
        size++;

    }


    //出栈
    //返回弹出的元素
    public T pop() {
        //如果弹出时栈为空则返回空
        if (isEmpty())
            return null;
        //用一个结点保存原头结点
        Node p = top;
        //将现在的头结点更新为原结点的下一个结点
        top = top.next;
        //将原头结点释放
        p.next = null;
        size--;
        return p.element;
    }

    //获取栈顶元素
    public T getTop() {
        //如果为空栈则返回空
        if (isEmpty())
            return null;
        return top.element;
    }

    //清空栈
    public void clear() {
        top = null;
        size = 0;
    }

    public String toString() {
        if (isEmpty())
            return "[]";
        else {
            StringBuilder sb = new StringBuilder("[");
            for (Node current = top; current != null; current = current.next)
                sb.append(current.element.toString() + "->");
            sb.append("]");
            int len = sb.length();
            return sb.delete(len - 3, len - 1).toString();
        }
    }

测试代码：

public static void main(String[] args) {
        LinkListStack<String> ll = new LinkListStack<String>();
        System.out.println("原栈中的元素： " + ll);
        System.out.println("----------进栈啦----------");
        //压栈
        ll.push("haha");
        ll.push("hehe");
        ll.push("xixi");
        ll.push("hiahia");
        ll.push("heihei");
        System.out.println("压栈后栈中所含元素： " + ll);
        //获取栈顶元素
        System.out.println("栈顶元素为： " + ll.getTop());
        //获取栈中元素个数
        System.out.println("当前栈中元素个数为： " + ll.getSize());
        //出栈
        System.out.println("----------出栈啦----------");
        ll.pop();
        System.out.println("出栈后栈中所含元素： " + ll);
        //获取栈顶元素
        System.out.println("栈顶元素为： " + ll.getTop());
        //获取栈中元素个数
        System.out.println("当前栈中元素个数为： " + ll.getSize());
}

测试结果：