Java---堆栈的三种实现

哎，面试被问住了，就记得当时学过的先进后出了，在此记录下。
(转载了一个大神回答，地址在这:https://segmentfault.com/a/1190000002516799

Stack

栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
java 没有栈这样的数据结构，如果想利用先进后出（FILO）这样的数据结构，就必须自己实现。

要实现Stack，至少应该包括：

• 1. pop() 出栈操作，弹出栈顶元素。
• 2. push(E e) 入栈操作
• 3. peek() 查看栈顶元素
• 4. isEmpty() 栈为空

另外，实现一个栈，还应该考虑到几个问题：

• 1. 栈的初始大小以及栈满以后如何新增栈空间
• 2. 对栈进行更新时需要进行同步

有三种实现的方式，数组，容器，以及链表的方法。

数组：

import java.util.*;

public class StackArray{
    private int[] array;//用数组实现
    private int top; //栈顶指针
    private final static int size = 100;
    public StackArray(){
        array = new int[size];
        top = -1; //栈空的时候 
    }
    //压栈
    public void push(int element){
        if(top == size-1){
            throw new StackOverflowError();
        }
        else 
            array[++top] = element;
    }
    //弹栈
    public int pop(){
        if(top == -1){
            throw new EmptyStackException();
        }
        return array[top--];
    }
    //判断是否为空
    public boolean isEmpty(){
        return top == -1;
    }
    //返回栈顶元素
    public Integer peek(){
        if(top == -1){
            throw new EmptyStackException();
        }
        return array[top];
    }
}

容器

public interface Stack<T> {
    public T pop();
    public void push(T element);
    public boolean isEmpty();
    public T peek();
}

package gsm;
import java.util.*;

public class StackList<T> implements Stack<T> {
    private List<T> list ; //用容器实现
    StackList(){
        list = new ArrayList<T>();
    }
    //弹栈
    public T pop(){
        if(this.isEmpty() == true){
            throw new EmptyStackException();
        }

        return list.remove(list.size()-1);
    }
    //压栈
    public void push(T element){
        list.add(element);
    }
    //判断是否为空
    public boolean isEmpty(){
        return list.size() == 0;
    }
    //返回栈顶元素
    public T peek(){
        if(this.isEmpty() == true){
            throw new EmptyStackException();
        }
        return list.get(list.size()-1);
    }
}

链表

import java.util.EmptyStackException;

public class LinkedStack<T> implements Stack<T>{
    //不用容器或者数组等数据结构存储节点
    //Node定义一个节点类
    private static class Node<U>{
        private U item; //存储的data
        private Node<U> next; //类似指针
        Node(){
            this.item = null;
            this.next = null;
        }
        Node(U item, Node<U> next){
            this.item = item;
            this.next = next;
        }
        boolean end(){
            return item == null && next == null;
        }
    } 

    private Node<T> top ; //栈顶指针
    LinkedStack(){
        top = new Node<T>();
    }


    //弹栈
    public T pop(){
        if(this.isEmpty() == true){
            throw new EmptyStackException();
        }
        T result = top.item;
        if(!top.end())
        {
            top = top.next;
        }
        return result;
    }
    //压栈
    public void push(T element){
        top = new Node<T>(element, top);
    }
    //判断是否为空
    public boolean isEmpty(){
        return  top.end();
    }
    //返回栈顶元素
    public T peek(){
        if(this.isEmpty() == true){
            throw new EmptyStackException();
        }
        T result = top.item;
        return result;
    }   
}

可以发现容器果然是java的一个利器，方便高效。