栈和队列的部分OJ题目

╰半橙微兮° 2022-11-13 00:46 174阅读 0赞

### 栈和队列的部分OJ题目 ###

*  括号问题
 *  用队列实现栈
 *  用栈实现队列
 *  最小栈
 *  设计循环队列
 *  棒球比赛
 *  剑指 Offer 31. 栈的压入、弹出序列

# 括号问题 #

1.  有效的括号 [链接][Link 1]  
    给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串 s ，判断字符串是否有效。  
    有效字符串需满足：  
    左括号必须用相同类型的右括号闭合。  
    左括号必须以正确的顺序闭合。

示例 1：  
输入：s = “()”  
输出：true  
示例 2：  
输入：s = “()\[\]\{\}”  
输出：true  
示例 3：  
输入：s = “(\]”  
输出：false

思路：  
将左括号放入栈中，然后如果遇到有括号且相匹配就从栈中删除，最后栈中应该为空。

class Solution { 
        public boolean isValid(String s) { 
            char[] array = s.toCharArray();
            Stack<Character> stack = new Stack<>();
            for (char ch : array) { 
                if (ch == '(' || ch == '[' || ch == '{') { 
                    stack.push(ch);
                } else if (ch == ')') { 
                    if (stack.isEmpty()) { 
                        return false;
                    }
                    if (stack.peek() == '(') { 
                        stack.pop();
                    } else { 
                        return false;
                    }
                } else if (ch == ']') { 
                    if (stack.isEmpty()) { 
                        return false;
                    }
                    if (stack.peek() == '[') { 
                        stack.pop();
                    } else { 
                        return false;
                    }
                } else { 
                    if (stack.isEmpty()) { 
                        return false;
                    }
                    if (stack.peek() == '{') { 
                        stack.pop();
                    } else { 
                        return false;
                    }
                }
            }
            return stack.size() == 0;
        }
    }

# 用队列实现栈 #

1.  用队列实现栈 [链接][Link 2]  
    请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：  
void push(int x) 将元素 x 压入栈顶。  
int pop() 移除并返回栈顶元素。  
int top() 返回栈顶元素。  
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

思路：  
删除和查看栈顶元素就从队列中把前面元素拿出，然后再放进去。

class MyStack { 
    
        private Queue<Integer> queue = new LinkedList<>();
    
        /** * Initialize your data structure here. */
        public MyStack() { 
        }
    
        /** * Push element x onto stack. */
        public void push(int x) { 
            queue.offer(x);
        }
    
        /** * Removes the element on top of the stack and returns that element. */
        public int pop() { 
            int size = queue.size();
            for (int i = 0; i < size - 1; i++) { 
                Integer remove = queue.remove();
                queue.add(remove);
            }
            return queue.remove();
        }
    
        /** * Get the top element. */
        public int top() { 
            int size = queue.size();
            for (int i = 0; i < size - 1; i++) { 
                Integer remove = queue.remove();
                queue.add(remove);
            }
            Integer ret = queue.remove();
            queue.add(ret);
            return ret;
        }
    
        /** * Returns whether the stack is empty. */
        public boolean empty() { 
            return queue.size() == 0;
        }
    }

# 用栈实现队列 #

1.  用栈实现队列 [链接][Link 3]  
    请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：  
void push(int x) 将元素 x 推到队列的末尾  
int pop() 从队列的开头移除并返回元素  
int peek() 返回队列开头的元素  
boolean empty() 如果队列为空，返回 true ；否则，返回 false

思路：两个栈，第一个入栈，然后把第一个栈中元素在放入第二个栈中，出栈的话，从第二个栈出。

class MyQueue { 
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
    
        /** * Initialize your data structure here. */
        public MyQueue() { 
        }
    
        /** * Push element x to the back of queue. */
        public void push(int x) { 
            stack2.push(x);
        }
    
        /** * Removes the element from in front of queue and returns that element. */
        public int pop() { 
            if (stack1.isEmpty()) { 
                while (!stack2.isEmpty()) { 
                    stack1.push(stack2.pop());
                }
            }
            return stack1.pop();
        }
    
        /** * Get the front element. */
        public int peek() { 
            if (stack1.isEmpty()) { 
                while (!stack2.isEmpty()) { 
                    stack1.push(stack2.pop());
                }
            }
            return stack1.peek();
        }
    
        /** * Returns whether the queue is empty. */
        public boolean empty() { 
            return stack1.size() == 0 && stack2.size() == 0;
        }
    }

# 最小栈 #

1.  最小栈 [链接][Link 4]  
    设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。  
pop() —— 删除栈顶的元素。  
top() —— 获取栈顶元素。  
getMin() —— 检索栈中的最小元素。

思路：  
两个栈，第一个存本来元素，第二个放当前最小元素。

class MinStack { 
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
    
        /** * initialize your data structure here. */
        public MinStack() { 
    
        }
    
        public void push(int val) { 
            stack1.push(val);
            if (stack2.isEmpty()) { 
                stack2.push(val);
            } else { 
                if (stack2.peek() > val) { 
                    stack2.push(val);
                } else { 
                    stack2.push(stack2.peek());
                }
            }
        }
    
        public void pop() { 
            stack1.pop();
            stack2.pop();
        }
    
        public int top() { 
            return stack1.peek();
        }
    
        public int getMin() { 
            return stack2.peek();
        }
    }

# 设计循环队列 #

1.  设计循环队列 [链接][Link 5]  
    设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。  
Front: 从队首获取元素。如果队列为空，返回 -1 。  
Rear: 获取队尾元素。如果队列为空，返回 -1 。  
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。  
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。  
isEmpty(): 检查循环队列是否为空。  
isFull(): 检查循环队列是否已满。

思路：  
主要注意： Index + array.length ± 1) % array.length的问题

class MyCircularQueue { 
    
        private int[] array;
        private int frontIndex;
        private int rearIndex;
        private int size;
    
        public MyCircularQueue(int k) { 
            array = new int[k];
            frontIndex = 0;
            rearIndex = 0;
            size = 0;
        }
    
        public boolean enQueue(int value) { 
            if (size == array.length) { 
                return false;
            }
            array[rearIndex] = value;
            rearIndex = (rearIndex + 1) % array.length;
            size++;
            return true;
    
        }
    
        public boolean deQueue() { 
            if (size == 0) { 
                return false;
            }
    
            frontIndex = (frontIndex + 1) % array.length;
            size--;
            return true;
        }
    
        public int Front() { 
            if (size == 0) { 
                return -1;
            }
            return array[frontIndex];
        }
    
        public int Rear() { 
            if (size == 0) { 
                return -1;
            }
            int i = (rearIndex + array.length - 1) % array.length;
            return array[i];
        }
    
        public boolean isEmpty() { 
            return size == 0;
        }
    
        public boolean isFull() { 
            return size == array.length;
        }
    }

# 棒球比赛 #

1.  棒球比赛 [链接][Link 6]  
    你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。

比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops\[i\] 是你需要记录的第 i 项操作，ops 遵循下述规则：

整数 x - 表示本回合新获得分数 x  
“+” - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。  
“D” - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。  
“C” - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。  
请你返回记录中所有得分的总和。

思路：  
定义两个栈，一个存分数，一个存之前的分数，方便计算前几次成绩的和。

class Solution { 
        public int calPoints(String[] ops) { 
            Stack<Integer> stack1 = new Stack<>();
            Stack<Integer> stack2 = new Stack<>();
    
            for (String s : ops) { 
                switch (s) { 
                    case "+":
                        Integer p1 = stack2.pop();
                        Integer p2 = stack2.pop();
                        stack1.push(p1 + p2);
                        stack2.push(p2);
                        stack2.push(p1);
                        stack2.push(p1 + p2);
    
                        break;
                    case "D":
                        Integer i = stack1.peek();
                        stack1.push(i * 2);
                        stack2.push(i * 2);
                        break;
                    case "C":
                        stack1.pop();
                        stack2.pop();
                        break;
                    default:
                        stack1.push(Integer.parseInt(s));
                        stack2.push(Integer.parseInt(s));
                }
            }
            int sum = 0;
    
            for (Integer e : stack1) { 
                sum += e;
            }
            return sum;
        }
    }

# 剑指 Offer 31. 栈的压入、弹出序列 #

剑指 Offer 31. 栈的压入、弹出序列 [链接][Link 7]  
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 \{1,2,3,4,5\} 是某栈的压栈序列，序列 \{4,5,3,2,1\} 是该压栈序列对应的一个弹出序列，但 \{4,3,5,1,2\} 就不可能是该压栈序列的弹出序列。

思路：将数组变换成链表方便操作。  
然后遍历popedList，如果不等就将pushedList放入栈中，最后，栈中为空。

class Solution { 
        private List<Integer> intList(int[]arr){ 
            List<Integer> list=new ArrayList<>();
            for(int e:arr){ 
                list.add(e);
            }
            return list;
        }
        public boolean validateStackSequences(int[] pushed, int[] popped) { 
            List<Integer> pushedList=intList(pushed);
            List<Integer> poppedList=intList(popped);
        
            Stack<Integer> stack = new Stack<>();
            for(int e:poppedList){ 
                if(!stack.isEmpty()&&stack.peek()==e){ 
                    stack.pop();
                    continue;
                }
    
                while(true){ 
                    if(pushedList.isEmpty()){ 
                        return false;
                    }
                    int f =pushedList.remove(0);
                    if(f==e){ 
                        break;
                    }
                    stack.push(f);
                }
            }
            return stack.isEmpty();
        }
    }

[Link 1]: https://leetcode-cn.com/problems/valid-parentheses/
[Link 2]: https://leetcode-cn.com/problems/implement-stack-using-queues/
[Link 3]: https://leetcode-cn.com/problems/implement-queue-using-stacks/
[Link 4]: https://leetcode-cn.com/problems/min-stack/
[Link 5]: https://leetcode-cn.com/problems/design-circular-queue/
[Link 6]: https://leetcode-cn.com/problems/baseball-game/
[Link 7]: https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/