01-栈

标准库中的栈

• Stack: Stack<Integer> s = new Stack<>();

  push() , pop() , peek()

• JDK官方文档不建议使用Stack实现栈的功能，转而使用Deque接口的ArrayDeque实现栈的功能

  Deque继承自Queue, Stack继承自Vector, Deque即“double ended queue”缩写；

  Deque具备普通队列FIFO功能，同时具备StackLIFO功能；

  ArrayDeque没有容量限制，可以作为栈来使用，效率高于Stack；

  ArrayDeque也可以作为队列来使用，效率相较于基于双向链表的LinkedList也要更好一些；

• 算法题中的栈

  Deque<Integer> stack = new ArrayDequeue<Integer>();
    
  stack.push(i);
  stack.pop();
  stack.peek();
  

---

数组模拟栈

package stack;

import java.util.Scanner;

public class ArrayStackDemo {

	public static void main(String[] args) {
	    ArrayStack stack = new ArrayStack(4);
	    String key = "";
	    boolean loop = true;
	    Scanner scanner = new Scanner(System.in);
	    
	    while(loop) {
	    	System.out.println("show:显示栈");
	    	System.out.println("exit:退出程序");
	    	System.out.println("push:入栈");
	    	System.out.println("pop:出栈");
	    	
	    	key = scanner.next();
	    	switch(key) {
	    	case "show":
	    		stack.list();
	    		break;
	    	case "push":
	    		System.out.println("请输入一个数");
	    		int value = scanner.nextInt();
	    		stack.push(value);
	    		break;
	    	case "pop":
	    		try {
	    			int res = stack.pop();
	    			System.out.printf("出栈的数据为:%d\n",res);
	    		}catch(Exception e){
	    			System.out.println(e.getMessage());
	    		}
	    		break;
	    	case "exit":
	    		scanner.close();
	    		loop = false;
	    		break;
	    	}
	    }
	}

}

class ArrayStack{
	private int maxSize;  //栈的大小
	private int[] stack;  
	private int top = -1;  
	
	//构造器
	public ArrayStack(int maxSize) {
		this.maxSize = maxSize;
		stack = new int[this.maxSize];
	}
	
	//栈满
	public boolean isFull() {
		return top == maxSize - 1;
	}
	
	//栈空
	public boolean isEmpty() {
		return top == -1;
	}
	
	//入栈-push
	public void push(int value) {
		if(isFull()) {
			System.out.println("栈满");
			return;
		}
		top++;
		stack[top] = value;
	}
	
	//出栈-pop
	public int pop() {
		if(isEmpty()) {
			throw new RuntimeException("栈空");
		}
		int value = stack[top];
		top--;
		return value;
	}
	
	//遍历栈,从栈顶开始显示
	public void list() {
		if(isEmpty()) {
			System.out.println("栈空");
			return;
		}
		for(int i = top;i>=0;i--) {
			System.out.printf("stack[%d]=%d\n",i, stack[i]);
		}
	}
}

---

使用栈计算表达式

中缀表达式

package stack;

public class Calculator {

	public static void main(String[] args) {
		String expression = "12*5-9+10";
		ArrayStack2 numStack = new ArrayStack2(10);
		ArrayStack2 operStack = new ArrayStack2(10);
		
		int index = 0; //用于扫描
		int num1 =  0;
		int num2 = 0;
		int oper = 0;
		int res = 0;
		char ch = ' ';
		String keepNum = ""; //用于拼接多位数
		while(true) {
			ch = expression.substring(index, index+1).charAt(0);
			//根据ch进行相应从处理
			if(operStack.isOper(ch)) {//如果是运算符
				if(!operStack.isEmpty()) {
					if(operStack.priority(ch)<=operStack.priority(operStack.peek())) {
						num1 = numStack.pop();
						num2 = numStack.pop();
						oper = operStack.pop();
						res = numStack.cal(num1, num2, oper);
						//运算结果入数栈
						numStack.push(res);
						//当前操作符入符号栈
						operStack.push(ch);
					}else {//当前操作符大于栈顶优先级
						operStack.push(ch);
					}
				}else {
					//为空直接入栈
					operStack.push(ch);
				}
			}else {
				//处理多位数时,不能发现是一个数就立即入栈
				//不断向后扫描,进行拼接,扫描到运算符入栈
				
				keepNum += ch; //这里为字符串拼接
				
				if(index == expression.length()-1) {
					numStack.push(Integer.parseInt(keepNum));
				}else {
				//判断下一个字符是不是数字
				if(operStack.isOper(expression.substring(index+1, index+2).charAt(0))) {
					//如果后一位是运算符，入栈
					numStack.push(Integer.parseInt(keepNum));
					keepNum = "";
				    }
			 	}		
			 }
			//判断是否扫描到字符串最后
			index++;
			if(index == expression.length()) {
				break;
			}
		}
		
		//扫描完毕，按顺序弹出，并进行运算、
		while(true) {
			//如果符号栈为空，则计算完毕，数栈中即为结果
			if(operStack.isEmpty()) {
				break;
			}
			num1 = numStack.pop();
			num2 = numStack.pop();
			oper = operStack.pop();
			res = numStack.cal(num1, num2, oper);
			numStack.push(res);
		}
		System.out.printf("%s=%d",expression,numStack.pop());
	}

}

class ArrayStack2{
	private int maxSize;  //栈的大小
	private int[] stack;  
	private int top = -1;  
	
	//构造器
	public ArrayStack2(int maxSize) {
		this.maxSize = maxSize;
		stack = new int[this.maxSize];
	}
	
	//栈满
	public boolean isFull() {
		return top == maxSize - 1;
	}
	
	//栈空
	public boolean isEmpty() {
		return top == -1;
	}
	
	//入栈-push
	public void push(int value) {
		if(isFull()) {
			System.out.println("栈满");
			return;
		}
		top++;
		stack[top] = value;
	}
	
	//出栈-pop
	public int pop() {
		if(isEmpty()) {
			throw new RuntimeException("栈空");
		}
		int value = stack[top];
		top--;
		return value;
	}
	
	//遍历栈,从栈顶开始显示
	public void list() {
		if(isEmpty()) {
			System.out.println("栈空");
			return;
		}
		for(int i = top;i>=0;i--) {
			System.out.printf("stack[%d]=%d\n",i, stack[i]);
		}
	}
	
	//扩展功能
	//展示栈顶元素
	public int peek() {
		return stack[top];
	}
    
	//返回运算符优先级
	public int priority(int oper) {
		if(oper == '*'||oper=='/')
			return 1;
		else if(oper == '+'||oper == '-')
			return 0;
		else 
			return -1;
	}
	
	//判断是否是运算符
	public boolean isOper(char val) {
		return val == '+'||val == '-'||val == '*'||val == '/';
	}
	
	//计算方法
	public int cal(int num1,int num2,int oper) {
		int res = 0;
		switch(oper) {
		case '+':
			res = num1 + num2;
			break;
		case '-':
			res = num2 - num1;
			break;
		case '*':
			res = num1 * num2;
			break;
		case '/':
			res = num2/num1;
			break;
		}
		return res;
	}
}

---