java数据结构之（顺序栈+链式栈）

﹏ヽ暗。殇╰゛Y 2022-08-23 00:39 296阅读 0赞

今天介绍一下数据结构中的栈。栈实现和线性表实现差不多都是有两种实现方式，一种是顺序栈，另一种就是链式栈。

下面先介绍一下顺序栈的实现方式：

package stack;
    import java.util.Arrays;
    /**
     * @ClassName: ArrayStack
     * @Description: 顺序栈
     * @date 2016年6月2日 下午21:01
     * @param 无
     */
    public class ArrayStack{
    	private Object[] arrayStack;//用来存储顺序栈的数组
    	private static final int length=10;//数组初始化的长度
    	private int size;//顺序栈的元素个数
    	public ArrayStack(){//初始化信息
    		this.arrayStack=new Object[length];
    		this.size=0;
    	}
    	public ArrayStack(int length){//自定义初始化信息
    		this.arrayStack=new Object[length];
    		this.size=0;
    	}
    	public Object peek(){//获取栈顶数据，但是不出栈
    		if(size==0){
    			return null;
    		}else{
    			return arrayStack[size-1];
    		}
    	}
    	public void push(Object value){//添加value元素到栈顶位置
    		if((size+1)>this.arrayStack.length){
    			this.arrayStack=Arrays.copyOf(arrayStack,this.arrayStack.length*2);
    		}
    		this.arrayStack[size++]=value;
    	}
    	public Object pop(){//获取栈顶元素并出栈
    		if((size-1)<0){
    			return null;
    		}else{
    			Object result=this.arrayStack[size-1];
    			this.arrayStack[--size]=null;
    			return result;
    		}
    	}
    	public boolean isEmpty(){//判断顺序栈是否为空
    		return size==0;
    	}
    	
    	public int size(){//获取顺序栈的元素个数
    		return this.size;
    	}
    	public void clear(){//清空顺序栈的所有元素
    		this.size=0;
    		Arrays.fill(this.arrayStack,null);
    	}
    	public void disPlay(){//打印顺序栈的所有元素
    		for(int i=0;i<this.size;i++){
    			System.out.print(this.arrayStack[i]+"\t");
    		}
    		System.out.println();
    	}
    	public static void main(String[] args) {
    		ArrayStack a=new ArrayStack();
    		for(int i=0;i<5;i++){
    			a.push(i);
    		}
    		a.disPlay();
    //		System.out.println(a.size());
    //		System.out.println(a.isEmpty());
    		a.clear();
    		a.disPlay();
    	}
    }

链式栈实现方式：

package stack;
    /**
     * @ClassName: LinkStack
     * @Description: 链式栈
     * @date 2016年6月2日 下午21:01
     * @param 无
     */
    public class LinkStack {
    	@SuppressWarnings("unused")
    	private class Node{//创建一个节点类
    		private Object data;//节点带有的数据
    		private Node next;//下一个节点
    		public Node(){
    			
    		}
    		public Node(Object data,Node next){//初始化节点类信息
    			this.data=data;
    			this.next=next;
    		}
    	}
    	private Node top;//定义一个指向栈顶的top结点
    	private int size=0;//链式栈的元素个数
    	public LinkStack(){//初始化栈顶节点信息
    		top=null;
    	}
    	public int size(){//获取链式栈的元素个数
    		return size;
    	}
    	public boolean isEmpty(){//判断链式栈是否为空
    		return size==0;
    	}
    	public void clear(){//清空链式栈的所有元素
    		size=0;
    		top=null;
    	}
    	public void push(Object data){//在链式栈栈顶部分添加元素
    		top=new Node(data,top);
    		size++;
    	}
    	public Object pop(){//获取链式栈栈顶元素，并出栈
    		if(top!=null){
    			Node temp=top;
    			top=top.next;
    			temp.next=null;
    			size--;
    			return temp.data;
    		}else{
    			return null;
    		}
    	}
    	public Object peek(){//获取链式栈栈顶元素，但是不出栈
    		return top.data;
    	}
    	
    	public void disPlay(){//打印链式栈所有元素
    		Node temp=top;
    		while(temp!=null){
    			System.out.print(temp.data+"\t");
    			temp=temp.next;
    		}
    		System.out.println();
    	}
    	public static void main(String[] args) {
    		LinkStack l=new LinkStack();
    		System.out.println("isEmpty:"+l.isEmpty());
    		System.out.println("size:"+l.size());
    		for(int i=0;i<5;i++){
    			l.push(i);
    		}
    		l.disPlay();
    		System.out.println("isEmpty:"+l.isEmpty());
    		System.out.println("size:"+l.size());
    		l.clear();
    //		System.out.println("top:"+l.peek());
    //		System.out.println("top:"+l.pop());
    //		System.out.println("top:"+l.pop());
    //		System.out.println("top:"+l.pop());
    //		System.out.println("top:"+l.pop());
    //		System.out.println("top:"+l.pop());
    //		System.out.println("top:"+l.pop());
    		l.disPlay();
    	}
    }

顺序栈和链式栈的时间复杂度都是O(1)，但是顺序栈初始化时需要确定一个固定的长度，所以存在存储元素限制和空间浪费的情况， 而链式栈虽然不需要确定一个固定的长度，但是每个元素都是一个对象，产生了额外的开销。

所以当存在栈的个数变化比较大情况下建议使用链式栈，反之则使用顺序栈。

**如果有什么不清楚或者有啥疑问意见可以加我QQ/[微信][Link 1]  208017534  / qiang220316，欢迎一起交流一起进步。**

**![Center][]**

[Link 1]: http://lib.csdn.net/base/5
[Center]: /images/20220722/32dbeeb0508f4a8da95cc3292ef85b5e.png