Java-Stack的三种实现(数组,容器,链表)

来源于:https://segmentfault.com/a/1190000002516799

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

要实现Stack,至少应该包括:
1. pop() 出栈操作,弹出栈顶元素。
2. push(E e) 入栈操作
3. peek() 查看栈顶元素
4. isEmpty() 栈为空

另外,实现一个栈,还应该考虑到几个问题:
1. 栈的初始大小以及栈满以后如何新增栈空间
2. 对栈进行更新时需要进行同步


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

数据:

package gsm;
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];
    }
}

容器

package gsm;

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);
    }
}

链表

package gsm;

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的一个利器,方便高效。

喜欢的话订阅一个呗~第一时间收到文章更新哟~

发表评论

电子邮件地址不会被公开。