1. 栈和队列的基本操作

队列的基本操作

	/*
	 * 抛出异常 　　		返回特殊值
	 * 插入：add(e)		offer(e)	插入一个元素
	 * 移除：remove()	poll()		移除和返回队列的头
	 * 检查：element()	peek()		返回但不移除队列的头。
	 * 
	 * .isEmpty() 判断是否空
	 * .length() 返回队列长
	 * .clear() 清空队列
	 * .contains(e) 是否包含某一元素
	 */
	public static void main(String args[]){
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        
        showQueue(queue);
        
        //System.out.println("队尾元素：" + queue.fr);
        System.out.println(".toString()结果为：" + queue.toString());
        System.out.println("队首为（不弹出）：" + queue.peek());
        System.out.println("是否包含4：" + queue.contains(4));
        System.out.println("队首为（弹出）：" + queue.poll());
        System.out.println("队首为（弹出）：" + queue.poll());
        System.out.println("添加5：" + queue.offer(5));
        System.out.println("返回队列长" + queue.size());
        
        showQueue(queue);
        
        System.out.println("清空队列");queue.clear();
        System.out.println("返回队列长:" + queue.size());
        System.out.println("队列是否空:" + queue.isEmpty());
	}
	
	public static void showQueue(Queue<Integer> q){
		System.out.print("队列内容为：");
        for(int i : q) {
            System.out.print(i + " ");
        }
        System.out.print("\n");
	}

栈的基本操作

public static void main(String args[]){
		Stack<Integer> stack = new Stack<>();		
		/*
		 * 插入：add(e) 返回true或者false		
		 * 插入：push(e)	返回插入的元素
		 * 移除：pop() 移除和返回栈顶
		 * 检查：peek() 返回但不移除栈顶。
		 * 
		 * .isEmpty() 判断是否空
		 * .length() 返回队列长
		 * .clear() 清空队列
		 * .contains(e) 是否包含某一元素
		 */
		stack.push(1);
		stack.push(2);
		stack.push(3);
				
		showStack(stack);
		
		System.out.println("栈底元素：" + stack.elementAt(stack.size()-1));
		System.out.println(".toString()结果为：" + stack.toString());
		System.out.println("栈顶为（不弹出）：" + stack.peek());
		System.out.println("是否包含4：" + stack.contains(4));
		System.out.println("栈顶为（弹出）：" + stack.pop());
        System.out.println("栈顶为（弹出）：" + stack.pop());
        System.out.println("添加5：" + stack.add(5));
        System.out.println("返回栈长" + stack.size());
        
        showStack(stack);
        
        System.out.println("清空栈"); stack.clear();
        System.out.println("返回栈长:" + stack.size());
        System.out.println("栈是否空:" + stack.isEmpty());
	}
	
	public static void showStack(Stack<Integer> s){
		System.out.print("栈内容为：");
        for(int i : s) {
            System.out.print(i + " ");
        }
        System.out.print("\n");
	}

232. 用栈实现队列

https://leetcode-cn.com/problems/implement-queue-using-stacks/
一遍过

	class MyQueue {
		
		Stack<Integer> stackIn;
		Stack<Integer> stackOut;

	    public MyQueue() {
	    	stackIn = new Stack<>(); // 负责进栈
	        stackOut = new Stack<>(); // 负责出栈
	    }
	    
	    public void push(int x) {//队列尾添加
	    	stackIn.push(x);
	    }
	    
	    public int pop() {//队头弹出
	    	checkstack();
	    	return stackOut.pop();
	    }
	    
	    public int peek() {//队头看一眼
	    	checkstack();
	    	return stackOut.peek();
	    }
	    
	    public boolean empty() {//两个栈都空就是空
	    	return stackIn.empty() && stackOut.empty();
	    }
	    
	    /*
	     * 检查栈2是否为空，不为空则将全部栈1弹入栈2
	     */
	    public void checkstack(){
	    	//如果栈2不为空，则不需要栈1弹入
	    	if(!stackOut.empty()) return;
	    	//如果栈2为空，则将栈1全部倒置弹入
	    	while(!stackIn.empty()){
	    		stackOut.push(stackIn.pop());
	    	}
	    }
	}

225. 用队列实现栈

https://leetcode-cn.com/problems/implement-stack-using-queues/
一遍过

用两个队列
用一个队列

	class MyStack {

		Queue<Integer> q1;
		Queue<Integer> q2;
		
	    public MyStack() {
	    	q1 = new LinkedList<>();
	    	q2 = new LinkedList<>();
	    }
	    
	    public void push(int x) {//新元素压入q1
	    	q1.offer(x);
	    }
	    
	    public int pop() {//将q1中除了最后一个元素都先弹入q2，只留一个元素然后弹出(移除)
	    	leftOne();
	    	int ansnum = q1.poll();
	    	backTo();
	    	return ansnum;
	    }
	    
	    public int top() {//将q1中除了最后一个元素都先弹入q2，只留一个元素然后展示（不移除）
	    	leftOne();
	    	int ansnum = q1.peek();
	    	q2.offer(q1.poll());
	    	backTo();
	    	return ansnum;
	    }
	    
	    public boolean empty() {
	    	return q1.isEmpty();
	    }
	    
	    public void leftOne(){//将q1中的元素只留最后一个，剩下的弹入q2
	    	while(q1.size() != 1){
	    		q2.offer(q1.poll());
	    	}
//			System.out.println(q1.toString());
//			System.out.println(q2.toString());
	    }
	    public void backTo(){//将q2的元素返回q1
	    	while(!q2.isEmpty()){
	    		q1.offer(q2.poll());
	    	}	    	
	    }
	    
	}

	class MyStack {

		Queue<Integer> q;
		
	    public MyStack() {
	    	q = new LinkedList<>();
	    }
	    
	    public void push(int x) {//添加
	    	q.offer(x);
	    }
	    
	    public int pop() {//移除
	    	for(int i=0; i<q.size()-1; i++){//除队尾的元素，都重新插入
	    		q.offer(q.poll());
	    	}
	    	return q.poll();
	    }
	    
	    public int top() {//不移除
	    	for(int i=0; i<q.size()-1; i++){//除队尾的元素，都重新插入
	    		q.offer(q.poll());
	    	}
	    	int ansnum = q.peek();
	    	q.offer(q.poll());
	    	return ansnum;
	    }
	    
	    public boolean empty() {
	    	return q.isEmpty();
	    }
	}

2. 栈的经典题目

20. 有效的括号

https://leetcode-cn.com/problems/valid-parentheses/
一遍过

	/*
	 * 执行用时：1 ms, 在所有 Java 提交中击败了98.80%的用户
	 * 内存消耗：39.4 MB, 在所有 Java 提交中击败了31.07%的用户
	 */
	public boolean isValid2(String s) {
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            //碰到左括号，就把相应的右括号入栈
            if (ch == '(') {
                deque.push(')');
            }else if (ch == '{') {
                deque.push('}');
            }else if (ch == '[') {
                deque.push(']');
            } else if (deque.isEmpty() || deque.peek() != ch) {
                return false;
            }else {//如果是右括号判断是否和栈顶元素匹配
                deque.pop();
            }
        }
        //最后判断栈中元素是否匹配
        return deque.isEmpty();
    }
	
	
	/*
	 * 执行用时：2 ms, 在所有 Java 提交中击败了54.24%的用户
	 * 内存消耗：39 MB, 在所有 Java 提交中击败了54.65%的用户
	 */
	public boolean isValid(String s) {
		if(s == null) return true;
		
		Stack<Character> stack = new Stack<>();
		for(int i=0; i<s.length(); i++){
			if(s.charAt(i) == '(') stack.add('(');
			if(s.charAt(i) == '{') stack.add('{');
			if(s.charAt(i) == '[') stack.add('[');
			
			if(s.charAt(i) == ')'){
				if(stack.empty() || stack.peek() != '('){
					return false;
				}else stack.pop();
			}
			
			if(s.charAt(i) == ']'){
				if(stack.empty() || stack.peek() != '['){
					return false;
				}else stack.pop();
			}
			
			if(s.charAt(i) == '}'){
				if(stack.empty() || stack.peek() != '{'){
					return false;
				}else stack.pop();
			}
		}
		
		if(!stack.empty()) return false;
		
		return true;
	}

150. 逆波兰表达式求值

https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/

java字符串判断相等不能用== ，要用.equals
字符串转int：Integer.valueOf(e)
除法和减法注意谁是被除数谁是被减数

/*
	 * 执行用时：8 ms, 在所有 Java 提交中击败了9.86%的用户
	 * 内存消耗：40.9 MB, 在所有 Java 提交中击败了37.77%的用户
	 */
	public int evalRPN(String[] tokens) {
		Stack<Integer> stack = new Stack<>();
		
		for(int i=0; i<tokens.length; i++){
			if("+".equals(tokens[i])) {//不能等号，要用equals
				stack.push(stack.pop() + stack.pop());
			}else if("-".equals(tokens[i])) {
				stack.push(-stack.pop() + stack.pop());
			}else if("*".equals(tokens[i])) {
				stack.push(stack.pop() * stack.pop());
			}else if("/".equals(tokens[i])) {
				//写法1：
				int p1 = stack.pop();
                int p2 = stack.pop();
                stack.push(p2/p1);
                
                //写法2：
                //stack.push(stack.pop() / stack.pop()); //为什么不对？
			}else {
				stack.push(Integer.valueOf(tokens[i]));//string 转换为int
			}
		}		
		return stack.peek();
	}

3. 队列的经典题目

239. 滑动窗口最大值（未完成）

https://leetcode-cn.com/problems/sliding-window-maximum/
单调队列

	/*
	 * 52 / 61 个通过测试用例，暴力超时
	 */
	public int[] maxSlidingWindow(int[] nums, int k) {
		int n = nums.length - k + 1; //nums.length=8, k=3
		int[] ans = new int[n];
		for(int i=0; i<=nums.length - k; i++){
			ans[i] = findmax(nums, i, i+k-1);
		}	
		return ans;
	}
	
	public int findmax(int[] nums, int i, int j){
		System.out.print("i:" + i + ", j:" + j);
		int ans = nums[i];
		while(i<=j){
			if(nums[i] > ans) ans = nums[i];
			i++;
		}
		return ans;
	}