1栈的简介

package cn.young22.dsa.ch05;

import cn.young22.dsa.ch06.ArrayStack;
import cn.young22.dsa.ch06.LinkedStack;
import cn.young22.dsa.ch06.VectorStack;
/** 测试所实现的
 * 	LinkedStack
 * 	VectorStack
 *  ArrayStack
 * */
public class StackDemo1 {
	public static void main(String[] args){

		// 初始化stringStacks
		// StackInterface stringStack = new LinkedStack<>();
		// 测试ArrayStack
		// StackInterface stringStack = new ArrayStack();
		// 测试 VectorStack
		StackInterface stringStack = new VectorStack<>();
		
		// 向栈中添加几个字符串
		stringStack.push("Jim");
		stringStack.push("Jess");
		stringStack.push("Jill");
		stringStack.push("Jane");
		stringStack.push("Joe");
		
		// 取栈顶元素的值
		String top = stringStack.peek();		//returns "Joe"
		System.out.println(top + " is at the top of the stack"); 
		
		// 删除栈顶元素的值
		top = stringStack.pop();				//returns "Joe"
		System.out.println(top + " is removed from the stack");
		
		// 取栈顶元素的值
		top = stringStack.peek();				//returns "Jane"
		System.out.println(top + " is at the top of the stack");
		
		// 删除栈顶元素的值
		top = stringStack.pop();				//returns "Jane"
		System.out.println(top + " is removed from the stack");
		
	}
}
/**
Output:

Joe is at the top of the stack
Joe is removed from the stack
Jane is at the top of the stack
Jane is removed from the stack
 */
package cn.young22.dsa.ch05;

import cn.young22.dsa.ch06.LinkedStack;

/** 检测表达式是否平衡的类
 * 	在一个中缀表达式中,若括弧成对出现,且无交叉使用,则说表达式是平衡的
 *  若括弧不是成对出现的或括弧有交叉使用,则说该中缀表达式是不平衡的
 *  我们使用栈这样的工具来进队中缀表达式是否平衡进行判断
 * */
public class BalanceChecker {
	/** 检查表达式平衡方法*/
	public static boolean checkBalance(String expression){
		// 创建一个LinkedStack类型的对象,将其赋值给StackInterface类型的遍历openDelimiterStack
		StackInterface openDelimiterStack = new LinkedStack<>();
		
		int characterCount = expression.length();	// 使用字符串的.length方法获得表达式的长度
		boolean isBalanced = true;					// 将表达式初试的平衡标识符设为true
		int index = 0;								// 循环控制下标
		char nextCharacter = ' ';					// 初始化nextCharcter为 ' '
		
		// 当表达式为平衡且下标控制符index小于字符串的长度时,进入循环
		// 若判断出表达式不平衡, 则结束循环
		// 或下标控制符index不小于characterCount,
		// 则说明表达式的括弧没有交叉使用,结束循环
		// 还要进一步判断栈中是否还有字符来判断表达式是否是平衡的
		while(isBalanced && (index < characterCount)){
			// 通过index每次取一个字符进行判断
			nextCharacter = expression.charAt(index);
			// 使用switch case语句进行配对
			switch(nextCharacter){
			case '(': case '[': case '{':
				// 若字符为 ( [ {, 则将该字符压进栈,然后再判断下一个字符
				openDelimiterStack.push(nextCharacter);
				break;
			case ')': case ']': case '}':
				// 若字符为 ) ] }, 则先判断上一个case中的栈是否为空,若为空,则说明表达式是不平衡的
				if(openDelimiterStack.isEmpty()){
					isBalanced = false;
				}
				// 若栈不为空,则将栈中的字符串压出并赋值给一个新变量openDelimiter
				// 使用isPaired方法比较两个字符是否是配对的
				else{
					char openDelimiter = openDelimiterStack.pop();
					isBalanced = isPaired(openDelimiter, nextCharacter);
				}
				break;
			} // end switch
			index++;
		}// end while
		
		// 通过循环处理完所有字符后,再看栈中是否还有字符,若还有字符,说明表达式是不平衡的
		if(!openDelimiterStack.isEmpty()){
			isBalanced = false;
		}
		// 返回表达式是否平衡的结果
		return isBalanced;	
	}
	
	/** 检查栈中pop出来的字符是否与下一个字符匹配的方法*/
	private static boolean isPaired(char open, char close){
		return(open == '(' && close == ')' ||
				open == '[' && close == ']' ||
				open == '{' && close == '}');
	}// end isPaired
}
package cn.young22.dsa.ch05;

/** 测试BalanceChecker类,
 *  使用一个平衡的表达式和一个不平衡的表达式来测试BalanceChecker类
 * */
public class BalanceCheckerDemo {
	public static void main(String[] args){
		String expression = "a {b [c (d + e)/2 - f] + 1}";
		boolean isBalanced = BalanceChecker.checkBalance(expression);
		
		if(isBalanced){
			System.out.println(expression + " is balanced");
		}else{
			System.out.println(expression + " is not balanced");
		}
		
		String expression1 = "a {b [c (d + e)/2 - f + 1}";
		boolean isBalanced1 = BalanceChecker.checkBalance(expression1);
		if(isBalanced1){
			System.out.println(expression1 + " is balanced");
		}else{
			System.out.println(expression1 + " is not balanced");
		}
	}
}
/*
Output:

a {b [c (d + e)/2 - f] + 1} is balanced
a {b [c (d + e)/2 - f + 1} is not balanced
*/
package cn.young22.dsa.ch05;
/**
 * 一个抽象数据类型栈的接口
 * */
public interface StackInterface {
	/**
	 * 
	* @FunctionName: push
	* @Action: 在栈顶添加一个新元素
	* @param @param newEntry    
	* @ReturnType: void    
	 */
	public void push(T newEntry);
	
	/**
	 * 
	* @FunctionName: pop
	* @Action: 从栈顶删除一个元素 
	* @ReturnType: T    
	* @return 在栈顶的元素
	 */
	public T pop();
	
	/**
	 * 
	* @FunctionName: peek
	* @Action: 检索栈顶元素
	* @ReturnType: T    
	* @return 返回栈顶元素
	 */
	public T peek();
	
	/**
	 * 
	* @FunctionName: isEmpty
	* @Action: 判断栈是否是空的
	* @ReturnType: boolean    
	* @return:若栈空,返回True,否则,返回False
	 */
	public boolean isEmpty();
	
	/**
	 * 
	* @FunctionName: clear
	* @Action: 清楚栈的所有元素 
	* @ReturnType: void    
	* @return
	 */
	public void clear();
}

2栈的顺序实现

package cn.young22.dsa.ch06;

import java.util.Arrays;
import java.util.EmptyStackException;

import cn.young22.dsa.ch05.StackInterface;
/** ArrayStack是用数组实现的栈
 * 	它实现了StackInterface的功能
 * */
public class ArrayStack implements StackInterface{
	private T[] stack;						// 泛型的栈数组
	private int topIndex;					// 记录栈顶位置的变量
	private boolean initialized = false;	// 初始化标识符
	private static final int DEFAULT_CAPACITY = 50;	// 默认栈容量为50
	private static final int MAX_CAPACITY = 10000;	// 最大的栈容量为10000
	
	/** 默认构造器方法,生成一个默认容量的栈对象*/
	public ArrayStack(){
		this(DEFAULT_CAPACITY);
	}// end default constructor
	
	/** 客户指定栈容量的构造方法,根据用户指定的栈容量生成一个栈对象*/
	public ArrayStack(int initialCapacity) {
		// 检查客户指定的栈容量是否是小于最大栈容量的
		checkCapacity(initialCapacity);
		
		// The cast is safe because the new array contains null entries
		@SuppressWarnings("unchecked")
		T[] tempStack = (T[])new Object[initialCapacity];
		stack = tempStack;
		topIndex = -1;
		initialized = true;
	}

// 
	
	/** push方法将客户指定的值加入到栈顶*/
	@Override
	public void push(T newEntry) {
		
		checkInitilization();
		ensureCapacity();
		stack[topIndex + 1] = newEntry;
		topIndex++;
	}
	
	/** pop方法删除栈顶元素
	 *  先检查栈是否正常初始化,若未正常初始化,则抛出异常
	 *  然后再检查栈是否为空,若栈空,则抛出异常
	 *  若栈对象初始化成功且栈不为空,则删除栈顶元素
	 * */
	@Override
	public T pop() {
		checkInitilization();
		if(isEmpty()){
			throw new EmptyStackException();
		}else{
			T top = stack[topIndex];
			stack[topIndex] = null;
			topIndex--;
			return top;
		}
	}
	
	/** 获取栈顶元素的值
	 *  与pop方法类似,先要检查栈对象是否初始化成功和栈是否为空
	 *  当栈初始化成功且不为空时,返回栈顶元素的值
	 * */
	@Override
	public T peek() {
		checkInitilization();
		if(isEmpty()){
			throw new EmptyStackException();
		}else{
			return stack[topIndex];
		}
	}
	
	/** 查看栈是否为空*/
	@Override
	public boolean isEmpty() {
		return topIndex < 0;
	}
	
	/** 清除栈中的所有元素*/
	@Override
	public void clear() {
		// 当栈不为空时,则一直pop出栈顶元素
		while(!isEmpty()){
			pop();
		}
	}
	
	/**
	 * 
	* @FunctionName: checkCapacity
	* @Action: 检测客户端所要的容量是否大于最大容量值
	* @param @param desiredCapacity    
	 */
	private void checkCapacity(int desiredCapacity){
		if(desiredCapacity > MAX_CAPACITY){
			throw new IllegalStateException("Attempt to create a bag whose capacity"+
					" exceeds allowed maximu of" + 
					MAX_CAPACITY);
		}
	}
	
	/**
	 * 
	* @FunctionName: checkInitilization
	* @Action: 检测对象是否被正常初始化
	* @ReturnType: void    
	* @return
	 */
	private void checkInitilization(){
		if(!initialized){
			throw new SecurityException("ArrayBag object is not initialized properly");
		}
	}
	
	/**
	 * 
	* @FunctionName: ensureCapacity
	* @Action: 保证栈有足够的容量 
	* @ReturnType: void    
	 */
	private void ensureCapacity(){
		if(topIndex >= stack.length - 1){
			int newLength = 2 * stack.length;
			checkCapacity(newLength);
			stack = Arrays.copyOf(stack, newLength);
		}// end if
	}// end ensureCapacity
	
}

3栈的链式实现

package cn.young22.dsa.ch06;

import java.util.EmptyStackException;

import cn.young22.dsa.ch05.StackInterface;
import jdk.nashorn.internal.objects.annotations.Getter;
import jdk.nashorn.internal.objects.annotations.Setter;
/**	
 * 	LinkedStack实现了StackInterface的所有方法
 * 	使用链表实现了栈
 * 
 * */
public class LinkedStack implements StackInterface{
	
	private Node topNode;	// 头结点的引用
	
	/** 默认构造方法,将头结点初始化为null*/
	public LinkedStack(){
		topNode = null;
	}// end of default constructor
	
	/** 头结点*/
	private class Node{
		private T 	data; // Entry in stack
		private Node next; // link to the next node
		
		/** 结点的构造方法,仅用data域初始化结点*/
		private Node(T dataPortion){
			this(dataPortion, null);
		}
		
		/** 结点的构造方法,用data和next两个域初始化结点*/
		private Node(T dataPortion, Node linkPortion){
			data = dataPortion;
			next = linkPortion;
		}
		
		@Getter
		private T getData(){
			return data;
		}
		
		@Setter
		private void setData(T newData){
			data = newData;
		}
		
		@Getter
		private Node getNextNode(){
			return next;
		}
		
		@Setter
		private void setNextNode(Node nextNode){
			next = nextNode;
		}
	}// end Node
	
	/** push方法,将客户给的新值加到栈顶*/
	@Override
	public void push(T newEntry) {
		Node newNode = new Node(newEntry, topNode);
		topNode = newNode;
	}

	/** pop方法,将栈顶元素删除*/
	@Override
	public T pop() {
		// 取得栈顶元素的引用
		T top = peek();
		
		// 断言topNode不为空结点
		assert (topNode != null);
		// 将topNode的引用指向它的下一个结点
		topNode = topNode.getNextNode();
		
		// 返回top结点的引用
		return top;
	}

	/** peek方法,获取栈顶元素的值
	 *  若栈为空,则抛出空栈异常
	 *  否则,返回栈顶元素的值
	 * */
	@Override
	public T peek() {
		if(isEmpty()){
			throw new EmptyStackException();
		}else{
			return topNode.getData();
		}	
	}
	
	/** isEmpty方法,判断栈是否为空*/
	@Override
	public boolean isEmpty() {
		return topNode == null;
	}

	/** clear方法,将栈清空*/
	@Override
	public void clear() {
		// 将栈顶的引用赋值为null即删除了所有的节点
		topNode = null;
	}
	
	

}

4使用java.util.Vector实现栈

package cn.young22.dsa.ch06;

import java.util.EmptyStackException;
import java.util.Vector;

import cn.young22.dsa.ch05.StackInterface;

/**
 * 	调用Vector类来实现栈的功能
 *  VectorStack实现了所有StackInterface的功能
 * */
public class VectorStack implements StackInterface {

	private Vector stack;						// 初始化一个Vector泛型的栈stack
	private boolean initialized = false;			// 将对象初始化标识符设为false
	private static final int DEFAULT_CAPACITY = 50;	// 将栈顶默认容量设为50
	private static final int MAX_CAPACITY = 10000;	// 将栈的最大容量设为10000
	
	/** 默认构造方法,生成一个默认容量的VectorStack对象*/
	public VectorStack(){
		this(DEFAULT_CAPACITY);
	}
	
	/** 栈的构造方法,根据用户给定栈容量生成栈*/
	public VectorStack(int initialCapacity){
		// 检查用户给定容量是否超过栈容量的最大值
		checkCapacity(initialCapacity);
		// 若未超过栈容量的最大值则使用Vector类构造一个给定容量的栈
		stack = new Vector<>(initialCapacity);
		// 将对象初始化标识符设置为true
		initialized = true;
	}
	
	/** push方法,用来将用户给定的值添加到栈顶*/
	@Override
	public void push(T newEntry) {
		// 检查栈对象是否初始化成功
		checkInitilization();
		// 若成功,则调用Vector的add方法,将给定的值加到栈顶
		stack.add(newEntry);
	}
	
	/** pop方法,删除栈顶元素*/
	@Override
	public T pop() {
		// 检查栈对象是否初始化成功
		checkInitilization();
		// 若栈为空,则抛出栈空异常
		if(isEmpty()){
			throw new EmptyStackException();
		}
		// 若栈不为空,移除栈顶元素
		else{
			return stack.remove(stack.size() - 1);
		}
	}
	
	/** peek方法,获取栈顶元素的值*/
	@Override
	public T peek() {
		// 检查栈对象是否初始化成功
		checkInitilization();
		// 若栈空,则抛出栈空异常
		if(isEmpty()){
			throw new EmptyStackException();
		}
		// 若栈不为空,则返回栈顶元素(对于Vector来说,是Vector的最后一个元素)
		else{
			return stack.lastElement();
		}
	}
	
	/** 判断栈空*/
	@Override
	public boolean isEmpty() {
		// 调用Vector的isEmpty()方法可以得到栈是否为空的结果
		return stack.isEmpty();
	}
	
	/** 清除栈*/
	@Override
	public void clear() {
		// 调用Vector的clear()方法可以清除栈
		stack.clear();
	}
	
	/**
	 * 
	* @FunctionName: checkCapacity
	* @Action: 检测客户端所要的容量是否大于最大容量值
	* @param @param desiredCapacity    
	 */
	private void checkCapacity(int desiredCapacity){
		// 若客户需求的栈容量大于最大的栈容量,抛出异常
		if(desiredCapacity > MAX_CAPACITY){
			throw new IllegalStateException("Attempt to create a bag whose capacity"+
					" exceeds allowed maximu of" + 
					MAX_CAPACITY);
		}
	}
	
	/**
	 * 
	* @FunctionName: checkInitilization
	* @Action: 检测对象是否被正常初始化
	* @ReturnType: void    
	* @return
	 */
	private void checkInitilization(){
		// 若对象未正常初始化,抛出异常
		if(!initialized){
			throw new SecurityException("ArrayBag object is not initialized properly");
		}
	}

}

5栈实现的算法效率分析

Leave a Reply

Your email address will not be published. Required fields are marked *