【数据结构】(堆栈的三种Java实现与经典应用)

堆栈在Java编程中无处不在,作为重要的数据结构类型之一,本篇使用了三种方式(数组\链表\共享数组空间)来实现堆栈,并且对一些经典的应用方法进行了定义,欢迎阅览ㄟ(◑‿◐ )ㄏ

前言

LIFO(先进后出)的一种线性表，栈的优点是存取速度快，仅次于寄存器，并且栈的数据是可共享的，但是存放在栈的数据的大小和生存周期是固定的，缺乏一定的灵活性。在本篇对栈的实现使用的是链表与数组的形式，因为这两种形式简化了在ArrayList和LinkedList中的逻辑。

数组形式对栈实现

public class Stack<E> {

	private Object[] data;
	private int maxsize;
	private int top;
	//若没有定义初始长度则自定义一个5为初始长度
	public Stack(){
		this(5);
	}
	//若有定义初始长度，则调用此构造函数来初始化数组长度
	public Stack(int maxsize) {
		if(maxsize>0) {
			this.maxsize = maxsize;
			data = new Object[maxsize];
			top = -1;  //top目前指向第一个元素之前的位置
		}else {
			System.out.println("初始化长度不能为0及小于0");
		}
	}
	//判断栈是否为空
	public boolean isEmpty() {
		return top==-1;
	}
	//入栈
	public void push(Object o) {
		if(top>=maxsize-1) {
			System.out.println("栈满，无法放入新元素");
		}else {
			data[++top] = o;  //若栈味满则此时top指针向上移动一位后存放入元素，此时成为栈顶元素
		}
	}
	//获取栈顶元素但不弹出
	public E peek() {
		if(isEmpty()) {
			System.out.println("栈空，无栈顶元素");
			return null;
		}else {
			return (E)data[top];
		}
	}
	//出栈
	public E pop() {
		if(isEmpty()){
			System.out.println("栈空，无栈顶元素");
			return null;
		}else {
			return (E)data[top--];
		}
	}
	//寻找元素在栈中的位置
	public int search(E order) {
		int toptem = top;  //临时top节点，以便查找完成后回到初始状态
		while(top!=-1) {
			if(data[top]==order) {
				break;
			}else {
				--top;
			}
		}
		int result = ++top;
		top = toptem;
		return result;
	}
	public static void main(String[] args) {
		Stack mystack= new Stack(6);
		mystack.push(1);
		mystack.push(2);
		mystack.push(3);
		mystack.push(4);
		System.out.println("mystack 是否为空？"+mystack.isEmpty());
		System.out.println("mystack的栈顶元素为："+mystack.peek());
		System.out.println("依次出栈前两个:"+mystack.pop()+mystack.pop());
		System.out.println("此时栈顶元素为："+mystack.peek());
		System.out.println("元素1此时在栈中的位置为："+mystack.search(2));
	}

链表形式堆栈实现

public class LinkStack<T> {

	Node<T> top = null;
	//用内部类对栈的节点进行定义
	class Node<T>{
		private T data;
		private Node<T> next=null;
		public Node(T data) {
			this.data = data;
		}
	}
	//入栈
	public void push(T data) {
		Node<T> newnode = new Node<T>(data);
		newnode.next = top;
		top = newnode;
	}
	//出栈
	public T pop() {
		if(top==null) {
			return null;
		}
		T data = top.data;
		top = top.next;
		return data;
	}
	//判断栈是否为空
	public boolean isEmpty() {
		return top==null;
	}
	//取栈顶的值
	public T peek() {
		if(top==null) {
			return null;
		}
		return top.data;
	}
	public static void main(String[] args) {
		LinkStack ls = new LinkStack();
		ls.push(1);
		ls.push(6);  //依次入栈
		ls.push(2);
		System.out.println("栈是否为空:"+ls.isEmpty());
		System.out.println(ls.pop());
		System.out.println(ls.pop());  //先入后出是栈的最大的特点
		System.out.println(ls.pop());
		System.out.println("取出栈顶元素:"+ls.peek()); //栈已经全部弹出 栈顶元素为null
	}
}

3.共享数组空间的双重栈形式

public class DoubleStack {

	private int maxsize = 20;
	private int topl;
	private int topr;
	private int[] data;
	public DoubleStack() {
		data = new int[maxsize];
		topl = -1;
		topr = maxsize;
	}
	//判断是否栈空
	public boolean isEmpty() {
		return ((topl==0)&&(topr==maxsize));
	}
	//判断是否栈满
	public boolean isFull() {
		return (topl+1==topr);
	}
	//清空栈
	public void clearStack() {
		topl = -1;
		topr = maxsize;
	}
	//获取栈的长度
	public int length() {
		if(isEmpty()) {
			return 0;
		}
		if(isFull()) {
			return maxsize;
		}
		int length = (topl+1)+(maxsize-topr);
		return length;
	}
	//获取左栈栈顶值
	public int getLeftStack() {
		if(topl==-1) {
			System.out.println("左栈什么都没有喔～");
			return 0;
		}
		return data[topl];
	}
	//获取右栈栈顶值
	public int getRightStack() {
		if(topr==maxsize) {
			System.out.println("右栈什么都没有喔～");
			return 0;
		}
		return data[topr];
	}
	//入栈
	public void push(String stackdir, int e) {  //stackdir分为左栈和右栈
		if(isFull()) {
			System.out.println("嘻嘻嘻栈满啦，不能再入啦～～");
			return ;
		}
		if(stackdir=="左栈") {
			topl+=1;
			data[topl]=e;
			return ;
		}
		if(stackdir=="右栈") {
			topr-=1;
			data[topr]=e;
			return ;
		}
	}	
	//出栈
	public int pop(String stackdir) {
		int result;
		if(isEmpty()) {
			System.out.println("555这里什么都没有，不能再出了～～～");
			return -1;
		}
		if(stackdir=="左栈") {
			result = data[topl--];
			return result;
		}
		if(stackdir=="右栈") {
			result = data[topr++];
			return result;
		}
		return 0;
	}
	//遍历此双栈
	public void stackTraverse() {
		int i=0;
		while(i<=topl) {
			System.out.println(data[i]+" ");
			i++;
		}
		i = topr;
		while(i<maxsize) {
			System.out.println(data[i]+" ");;
			i++;
		}
	}
	public static void main(String[] args) {
		DoubleStack stack = new DoubleStack();
		System.out.println("此时栈为空吗？"+stack.isEmpty());
		stack.push("左栈", 1);
		stack.push("左栈", 2);
		stack.push("左栈", 3);
		stack.push("右栈", 4);
		stack.push("右栈", 5);
		stack.push("右栈", 6);
		System.out.println("此时栈的长度为:"+stack.length());
		System.out.println("我放入了一些元素，此时栈为空吗？"+stack.isEmpty());
		System.out.println("我想看看左栈栈顶是什么:"+stack.getLeftStack());
		System.out.println("我还想看右栈栈顶是什么:"+stack.getRightStack());
		System.out.print("让我看看栈里面都有什么吧：");
		stack.stackTraverse();
		System.out.println("我想弹出一些左栈的元素"+stack.pop("左栈")+stack.pop("左栈"));
		System.out.println("我想弹出一些右栈的元素"+stack.pop("右栈")+stack.pop("右栈"));
		System.out.print("现在栈里都还剩哪些元素呢？:");
		stack.stackTraverse();
	}
}