Java数据结构和算法（四）——栈详解编程语言

package com.ys.datastructure; 
 
public class MyStack { 
	private int[] array; 
	private int maxSize; 
	private int top; 
	 
	public MyStack(int size){ 
		this.maxSize = size; 
		array = new int[size]; 
		top = -1; 
	} 
	 
	//压入数据 
	public void push(int value){ 
		if(top < maxSize-1){ 
			array[++top] = value; 
		} 
	} 
	 
	//弹出栈顶数据 
	public int pop(){ 
		return array[top--]; 
	} 
	 
	//访问栈顶数据 
	public int peek(){ 
		return array[top]; 
	} 
	 
	//判断栈是否为空 
	public boolean isEmpty(){ 
		return (top == -1); 
	} 
	 
	//判断栈是否满了 
	public boolean isFull(){ 
		return (top == maxSize-1); 
	} 
	 
 
} 

package com.ys.test; 
 
import com.ys.datastructure.MyStack; 
 
public class MyStackTest { 
	public static void main(String[] args) { 
		MyStack stack = new MyStack(3); 
		stack.push(1); 
		stack.push(2); 
		stack.push(3); 
		System.out.println(stack.peek()); 
		while(!stack.isEmpty()){ 
			System.out.println(stack.pop()); 
		} 
		 
	} 
 
} 

package com.ys.datastructure; 
 
import java.util.Arrays; 
import java.util.EmptyStackException; 
 
public class ArrayStack { 
	//存储元素的数组,声明为Object类型能存储任意类型的数据 
	private Object[] elementData; 
	//指向栈顶的指针 
	private int top; 
	//栈的总容量 
	private int size; 
	 
	 
	//默认构造一个容量为10的栈 
	public ArrayStack(){ 
		this.elementData = new Object[10]; 
		this.top = -1; 
		this.size = 10; 
	} 
	 
	public ArrayStack(int initialCapacity){ 
		if(initialCapacity < 0){ 
			throw new IllegalArgumentException("栈初始容量不能小于0: "+initialCapacity); 
		} 
		this.elementData = new Object[initialCapacity]; 
		this.top = -1; 
		this.size = initialCapacity; 
	} 
	 
	 
	//压入元素 
	public Object push(Object item){ 
		//是否需要扩容 
		isGrow(top+1); 
		elementData[++top] = item; 
		return item; 
	} 
	 
	//弹出栈顶元素 
	public Object pop(){ 
		Object obj = peek(); 
		remove(top); 
		return obj; 
	} 
	 
	//获取栈顶元素 
	public Object peek(){ 
		if(top == -1){ 
			throw new EmptyStackException(); 
		} 
		return elementData[top]; 
	} 
	//判断栈是否为空 
	public boolean isEmpty(){ 
		return (top == -1); 
	} 
	 
	//删除栈顶元素 
	public void remove(int top){ 
		//栈顶元素置为null 
		elementData[top] = null; 
		this.top--; 
	} 
	 
	/** 
	 * 是否需要扩容，如果需要，则扩大一倍并返回true，不需要则返回false 
	 * @param minCapacity 
	 * @return 
	 */ 
	public boolean isGrow(int minCapacity){ 
		int oldCapacity = size; 
		//如果当前元素压入栈之后总容量大于前面定义的容量，则需要扩容 
		if(minCapacity >= oldCapacity){ 
			//定义扩大之后栈的总容量 
			int newCapacity = 0; 
			//栈容量扩大两倍(左移一位)看是否超过int类型所表示的最大范围 
			if((oldCapacity<<1) - Integer.MAX_VALUE >0){ 
				newCapacity = Integer.MAX_VALUE; 
			}else{ 
				newCapacity = (oldCapacity<<1);//左移一位，相当于*2 
			} 
			this.size = newCapacity; 
			int[] newArray = new int[size]; 
			elementData = Arrays.copyOf(elementData, size); 
			return true; 
		}else{ 
			return false; 
		} 
	} 
	 
	 
 
} 

//测试自定义栈类 ArrayStack 
//创建容量为3的栈，然后添加4个元素，3个int，1个String. 
@Test 
public void testArrayStack(){ 
	ArrayStack stack = new ArrayStack(3); 
	stack.push(1); 
	//System.out.println(stack.peek()); 
	stack.push(2); 
	stack.push(3); 
	stack.push("abc"); 
	System.out.println(stack.peek()); 
	stack.pop(); 
	stack.pop(); 
	stack.pop(); 
	System.out.println(stack.peek()); 
} 

//进行字符串反转 
@Test 
public void testStringReversal(){ 
	ArrayStack stack = new ArrayStack(); 
	String str = "how are you"; 
	char[] cha = str.toCharArray(); 
	for(char c : cha){ 
		stack.push(c); 
	} 
	while(!stack.isEmpty()){ 
		System.out.print(stack.pop()); 
	} 
} 

//分隔符匹配 
//遇到左边分隔符了就push进栈，遇到右边分隔符了就pop出栈，看出栈的分隔符是否和这个有分隔符匹配 
@Test 
public void testMatch(){ 
	ArrayStack stack = new ArrayStack(3); 
	String str = "12<a[b{c}]>"; 
	char[] cha = str.toCharArray(); 
	for(char c : cha){ 
		switch (c) { 
		case '{': 
		case '[': 
		case '<': 
			stack.push(c); 
			break; 
		case '}': 
		case ']': 
		case '>': 
			if(!stack.isEmpty()){ 
				char ch = stack.pop().toString().toCharArray()[0]; 
				if(c=='}' && ch != '{' 
					|| c==']' && ch != '[' 
					|| c==')' && ch != '('){ 
					System.out.println("Error:"+ch+"-"+c); 
				} 
			} 
			break; 
		default: 
			break; 
		} 
	} 
}