代码随想录——栈与队列

题目来自：https://www.programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

文章目录

1. 栈和队列的基本操作

队列的基本操作栈的基本操作232. 用栈实现队列225. 用队列实现栈 2. 栈的经典题目

20. 有效的括号150. 逆波兰表达式求值 3. 队列的经典题目

239. 滑动窗口最大值（未完成）347. 前 K 个高频元素（未完成）

1. 栈和队列的基本操作队列的基本操作

	
	public static void main(String args[]){
		Queue 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 q){
		System.out.print("队列内容为：");
        for(int i : q) {
            System.out.print(i + " ");
        }
        System.out.print("n");
	}

栈的基本操作

public static void main(String args[]){
		Stack stack = new Stack<>();		
		
		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 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 stackIn;
		Stack 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();
	    }
	    
	    
	    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 q1;
		Queue 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 q;
		
	    public MyStack() {
	    	q = new linkedList<>();
	    }
	    
	    public void push(int x) {//添加
	    	q.offer(x);
	    }
	    
	    public int pop() {//移除
	    	for(int i=0; i 
2. 栈的经典题目 
20. 有效的括号 
https://leetcode-cn.com/problems/valid-parentheses/
 一遍过 
	
	public boolean isValid2(String s) {
        Deque 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();
    }
	
	
	
	public boolean isValid(String s) {
		if(s == null) return true;
		
		Stack stack = new Stack<>();
		for(int i=0; i 
150. 逆波兰表达式求值 
https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/ 
java字符串判断相等不能用== ，要用.equals字符串转int：Integer.valueOf(e)除法和减法注意谁是被除数谁是被减数 
	public int evalRPN(String[] tokens) {
		Stack stack = new Stack<>();
		
		for(int i=0; i 
3. 队列的经典题目 
239. 滑动窗口最大值（未完成） 
https://leetcode-cn.com/problems/sliding-window-maximum/
 单调队列 
	
	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;
	}
 
347. 前 K 个高频元素（未完成） 
https://leetcode-cn.com/problems/top-k-frequent-elements/
 优先队列

代码随想录——栈与队列

Java相关栏目本月热门文章