栈与队列能解决哪些经典问题?每个问题都在我主页中可以找到,欢迎大家关注~~
(1)括号匹配问题(栈)
(2)字符串去重问题(栈)
(3) 逆波兰表达式问题(栈)
(4)滑动窗口最大值问题(单调队列)
(5)前K个出现次数最多的元素问题(优先级队列)
(6)栈实现队列
(7)队列实现栈
一.题解
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
class MyQueue {
Stack<Integer> stack1;
Stack<Integer> stack2;
public MyQueue() {
stack1=new Stack<>();
stack2=new Stack<>();
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if(!stack2.isEmpty()){
return stack2.pop();
}
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}
public int peek() {
if(!stack2.isEmpty()){
return stack2.peek();
}
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty()&&stack2.isEmpty();
}
}
二.栈的基础知识
栈最显著特点就是:先进后出
1.Java中栈的常见实现类:
最基础实现:Stack<Integer> stack=new Stack<>();
双端队列实现:Deque<Integer> stack=new LinkedList<>();
2.栈的常用方法
push(x) — 将一个元素放入队列的尾部。
pop() — 从队列首部移除元素。
peek() — 返回队列首部的元素。
empty() — 返回队列是否为空。
三.队列的基础知识
队列最显著特点就是:先进先出
1.Java中队列的常见实现类:
普通队列:Queue<Integer> queue=new LinkedList<>();
双端队列:Deque<Integer> queue=new LinkedList<>();
优先级队列:PriorityQueue<Integer> queue=new PriorityQueue<>();
2.队列的常用方法
add 增加一个元索 如果队列已满,则抛出一个IIIegaISlabEepeplian异常
remove 移除并返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
element 返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
size 元素个数
offer 添加一个元素并返回true 如果队列已满,则返回false
poll 移除并返问队列头部的元素 如果队列为空,则返回null
peek 返回队列头部的元素 如果队列为空,则返回null
put 添加一个元素 如果队列满,则阻塞
take 移除并返回队列头部的元素 如果队列为空,则阻塞
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/116054.html