【数据结构与算法01】栈

定义：只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。根据存储方式可分为顺序栈和链栈。

运算限制：后进先出。

基本概念：不含数据元素的栈称为空栈。操作数据的一端称为栈顶top。

基本运算：

                      1：初始化栈：创建一个空栈。

                      2：判空。

                      3：入栈：更新栈顶指针，添加栈顶数据。

                      4：出栈：删除栈顶数据，更新栈顶指针。

                      5：读栈顶数据。

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

顺序栈实现

public class SequenceStack implements Stack{
	private Integer[] array ;
	private int size ;
	private int top = -1 ;//表示空栈
	
	public SequenceStack(int size){
		this.size = size;
		this.array = new Integer[size];
	}
	
	@Override
	public boolean isEmpty() {
		return (top==-1);
	}
	
    //数组长度限制，需要判满
	@Override
	public boolean isFull() {
		return (top==size-1);
	}
	
	//入栈
	@Override
	public void push(int value) throws Exception{
		if(isFull()) throw new ArrayIndexOutOfBoundsException(size);
		array[++top] = value ;
	}
	
	//删除并返回栈顶元素，更新栈顶指针
	@Override
	public Integer pop(){
		if(isEmpty()) return null;
		int a= array[top];
		array[top] = null;
		top--;
		return a ;
	}
	
	//返回栈顶元素
	@Override
	public Integer top(){
		return isEmpty()?null:array[top];
	}
	
	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		for(Integer i : array){
			stringBuilder.append(i+",");
		}
		return stringBuilder.toString()
                .substring(0, stringBuilder.toString().length()-1);
	}
}

链栈实现

public class LinkStack implements Stack {
	
	private Link top;

	@Override
	public boolean isEmpty() {
		return (top==null);
	}

	@Override
	public boolean isFull() {
		return false;
	}

	@Override
	public void push(int value) throws Exception {
		Link newLink = new Link();
		newLink.data = value ;
		newLink.next = top ;
		top = newLink ;
	}

	@Override
	public Integer pop() {
		if(isEmpty()){
			return null;
		}
		Integer data = top.data;
		top = top.next;
		return data;
	}

	@Override
	public Integer top() {
		return isEmpty()?null:top.data;
	}

	static class Link{
		Integer data;
		Link next ;
	}
}

测试结果

public class Test {
	
	public static void main(String[] args) throws Exception {
		Stack sequenceStack = new SequenceStack(10);
		sequenceStack.push(999);
		System.out.println(sequenceStack);
		
		Stack linkstack = new LinkStack();
		System.out.println(linkstack.isEmpty());
		System.out.println(linkstack.pop());
		System.out.println(linkstack.top());
		linkstack.push(1);
		System.out.println(linkstack.pop());
		System.out.println(linkstack.top());
	}

}

999,null,null,null,null,null,null,null,null,null
true
null
null
1
null