栈

定义：

插入和删除都发生在同一端的有序列表，操作这端称为栈顶，先插入的元素会被最后移除，栈的特点是先进后出

栈操作：

push（）向栈中推入元素

pop()从栈中移除元素

下溢：从空栈中弹出元素；

上溢：向满栈中推入元素；

栈的运用：

1.符号或标签匹配问题

2.中缀表示法转换为后缀表示法

3.求后缀表达式的值，

4.函数调用 

5.浏览器的回退机制

6.树的遍历充当辅助数据结构

实现：

⑴数组

package com.dong.stack;
/**
 * 栈实现
 * 
 * @author liuD
 */
public class ArticleResource {
//使用简单的数组实现。
	static class ArrayStack{
		int top;
		int capacity;
		int array[];
	}
	public ArrayStack createStack() {
		ArrayStack stack = new ArrayStack();
		if(stack == null) return null;
		stack.capacity = 1;
		stack.top = -1;
		stack.array = new int [stack.capacity];
		if(stack.array == null)
			return null;
		return stack;
	}
	public boolean isEmptyStack(ArrayStack stack) {
		return (stack.top == -1);
	}
	public boolean isFullStack(ArrayStack stack) {
		return (stack.top == stack.capacity - 1);
	}
	public void push(ArrayStack stack,int value) {
		if(isFullStack(stack))
			System.out.println("Stack overflow");
		stack.array[stack.top+1]  = value;
	}
	public int pop(ArrayStack stack) {
		if(isEmptyStack(stack)) {
			System.out.println("Stack overflow");
			return 0;
		}
		else
			return (stack.array[stack.top]);
	}
	public void delete(ArrayStack stack) {
		if(stack != null) {
			if(stack.array != null)
				stack.array = null;
			stack = null;
		}
	}
}

⑵链表

package com.dong.stack;
/**
 * 栈实现
 * 
 * @author liuD
 */
public class ArticleResource {
//使用链表实现
	static class LinkStack {
		int data;
		LinkStack next;
	}
	
	LinkStack createLinkStack() {
		return null;
	}
	//注意这里的插入是从前端插入，最先插入的元素在链表的后面。
	public void LinkPush(int data,LinkStack top) {
		LinkStack temp = new LinkStack();
		if(temp != null)
			return ;
		temp.data = data;
		temp.next = top;
		top = temp;
	}
	public boolean IsEmptyLinkStack(LinkStack top) {
		return  (top==null);
	}
	public int POPLinkStack(LinkStack top) {
		int data;
		LinkStack temp;
		if(IsEmptyLinkStack(top))
			return Integer.MIN_VALUE;
		temp = top;
		top = top.next;
		data = temp.data;
		return data;
	}
	
}