Code01-栈

洛谷 P2947

package luogu;

import java.util.ArrayDeque;
import java.util.Scanner;
import java.util.Stack;

public class P2947 {

	public static void main(String[] args) {
		int n = 0;
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		int h[] = new int[n+1];
		int l[] = new int[n+1];
		for(int i = 1;i<=n;i++) {
			h[i] = scanner.nextInt();
		}
		
		//Stack<Integer> s = new Stack<>();
		ArrayDeque<Integer> s = new ArrayDeque<>(); //效率高
		
		for(int j = n;j>=1;j--) {
			while(!s.isEmpty()&&h[j]>=h[s.peek()]) {
				s.pop();
			}
			if(s.isEmpty()) {
				l[j] = 0;
			}else {
				l[j] = s.peek();
			}
			s.push(j);
		}
	
		for(int i = 1;i<=n;i++) {
			System.out.printf("%d\n",l[i]);
		}
	}

}

思路：

单调栈，从输入数组的最后一个元素开始，把对应下标压入栈中；

当前元素大于等于栈顶元素时，弹出栈顶元素，直到小于栈顶元素或栈空为止；

栈空则当前元素无仰望，不空则其仰望为此时栈顶下标对应元素

注意：

ArrayDeque用时比Stack少，使用Stack有两个例子RE，换用后通过

---

POJ 1363

package POJ;

import java.util.ArrayDeque;
import java.util.Scanner;

public class POJ_1363 {

	public static void main(String[] args) {
		int n;
		int i,j;
		int mid;
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		while(n!=0) {
			int b[] = new int[n];
			b[0] = scanner.nextInt();
			ArrayDeque<Integer> s = new ArrayDeque<>();
			while(b[0]!=0) {
				for(i = 1;i<n;i++) {
					b[i] = scanner.nextInt();
				}
				i = j = 0;
				s.push(++i);
				while(i<=n&&j<n) { //i：顺序数组下标; j:输入数组下标
					if(s.isEmpty())s.push(++i);
					else{
						mid = s.peek();
						if(mid!=b[j])s.push(++i);
						else {
							s.pop();
							++j;
						}
					}
				}
				if(j>=n) {
					System.out.println("Yes");
				}else{
					System.out.println("No");
				}
				b[0] = scanner.nextInt();
			}
			n = scanner.nextInt();
		}
	}
}

基本的栈问题，主要为输入格式的应对方法;

POJ 不支持ArrayDeque。

---

POJ 2106

package POJ;

import java.util.Scanner;

public class POJ_2106_02 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int cnt = 0;
		while(scanner.hasNext()) {  //JAVA中：EOF结尾的处理方式
			ArrayStack numStack = new ArrayStack(1000);
			ArrayStack operStack = new ArrayStack(1000);
			
			int index = 0;
			int num1 = 0;
			int num2 = 0;
			int oper = 0;
			int res = 0;
			char ch = ' ';
			cnt ++;
			String expression = scanner.nextLine();
			while(true) {
				while(true) {
					ch = expression.substring(index,index+1).charAt(0);
					if(ch!=' ')break;
					index++;
					if(index >= expression.length())break;
				}
				if(operStack.isOper(ch)) {
					if(!operStack.isEmpty()) {
						if(ch == '!'||ch == '(') {  // 将取非符号直接压入符号栈，否则"!!F"为例，会出现取不出数字的情况
							operStack.push(ch);
						}
						else if(operStack.peek() == '('&&ch!=')') {
							operStack.push(ch);
						}else {
							if((ch!=')')&&(operStack.priority(ch)>operStack.priority(operStack.peek()))) {
								operStack.push(ch);
							}else {
								int mid = 0;
								if(ch != ')') {
									while(true) {  //符号栈弹出直到栈顶优先级小于当前符号优先级
										if(!operStack.isEmpty()&&(operStack.peek() == '('))break;
										if(operStack.isEmpty())break;
										if((operStack.priority(ch)>operStack.priority(operStack.peek())))break;
										mid = operStack.pop();
										num2 = numStack.pop();
										if(mid!='!')
											num1 = numStack.pop();
										res = numStack.cal(num1, num2, mid);
										numStack.push(res);					
									}
									operStack.push(ch);
								}else {
									while(true){
										mid = operStack.pop();
										if(mid == '(')
											break;
										num2 = numStack.pop();
										if(mid != '!')
											num1 = numStack.pop();
										res = numStack.cal(num1, num2, mid);
										numStack.push(res);
									}
								}
							}
						}
					}else {
						operStack.push(ch);
					}
				}else {
					if(ch == 'V') {
						numStack.push(1);
					}else if(ch == 'F'){
						numStack.push(0);
					}
				}
				index++;
				if(index >= expression.length())
					break;
			}
			
			while(true) {
				if(operStack.isEmpty())
					break;
				oper = operStack.pop();
				num2 = numStack.pop();
				if(oper!='!')
					num1 = numStack.pop();
				res = numStack.cal(num1, num2, oper);
				numStack.push(res);
			}
			char r = ' ';
			int realRes = 0;
			realRes = numStack.pop();
			if(realRes == 1)r = 'V';
			else if(realRes == 0)r = 'F';
			System.out.printf("Expression %d: %c\n", cnt,r);
		}
	}

}

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;
	}
	
	public void push(int value) {
		top++;
		stack[top] = value;
	}
	
	public int pop() {
		int value = stack[top];
		top --;
		return value;
	}
	
	public int peek() {
		return stack[top];
	}
	
	public int priority(int oper) {
		if(oper == '!')
			return 1;
		else if(oper == '&')
			return 0;
		else return -1;
	}
	
	public boolean isOper(char val) {
		return val == '!'||val == '&' ||val == '|'||val == '('||val == ')';
	}
	
	public int cal(int num1,int num2,int oper) {
		int res = 0;
		switch(oper) {
		case '&':
			res = ((num1 == 1)&&(num2 == 1))?1:0;
			break;
		case '|':
			res = ((num1 == 1)||(num2 == 1))?1:0;
			break;
		case '!':
			res = (num2 == 0)?1:0;
			break;
		}
		return res;
	}
}

思路：

标准的引入括号的使用栈计算中缀表达式，在此基础上添加了单目运算符取非；

注意：

取非符号应直接压入到操作符栈；

引入括号后一些处理上的细节问题，例如：

• 判断是否为符号要加入左右括号；
• 比较运算符优先级大小时，遇到”(“要停止,要识别当前操作符不是”)”；
• 若当前操作符为”)”,则栈顶是”(“时不应直接入栈；

---