关于队列在Java中常见的实现类LinkedList
queue的常见用法
232. 用栈实现队列
Java中栈stack
Stack<Object> stackIn = new Stack<>();//进入栈Stack<Object> stackOut = new Stack<>();//弹出栈
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() {//pop和peek都需要这个相同的思路,//都需要先判断出栈是否为空,否则,把入栈的所有元素拿到出栈里面if (stackOut.isEmpty()) {while (!stackIn.isEmpty()) {Integer pop = stackIn.pop();stackOut.push(pop);}}return stackOut.pop();}public int peek() {if (stackOut.isEmpty()) {while (!stackIn.isEmpty()) {Integer pop = stackIn.pop();stackOut.push(pop);}}return stackOut.peek();}public boolean empty() {return (stackIn.isEmpty() && stackOut.isEmpty());}}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/
225. 用队列实现栈
这一题不能仿照上一题,因为队列两个颠倒以后还是原本的顺序,根本原因在于队列是先进先出,栈还是先进后出
这里使用两个队列其中queue2仅仅是一个辅助队列
官方视频:题解
class MyStack {
Queue<Integer> queueIn;
Queue<Integer> queue1;
Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
//queue2先存下进来的元素,因为如果直接让q1存,这个元素就变成最后的了
queue2.offer(x);
//在q1不是空的情况下我们把q1的所有元素追加到q2上,
//这样我们就做到了让最开始的元素也就是queue2.offer(x);这个变成了第一个
//接着我们交换q1和q2即可
while (!queue1.isEmpty()){
queue2.offer(queue1.poll());
}
//交换两个队列
Queue<Integer> temp;
temp = queue1;
queue1 = queue2;
queue2 = temp;
}
public int pop() {
return queue1.poll();
}
public int top() {
return queue1.peek();
}
public boolean empty() {
return queue1.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
使用一个队列的方法labuladong
20. 有效的括号
先进的括号后匹配 符合栈先进后出的数据结构
class Solution {
public boolean isValid(String s) {
Deque<Character> queue = new LinkedList<>();
char ch;
for (int i = 0; i < s.length(); i++) {
ch = s.charAt(i);
if (ch == '('){
queue.push(')');
}else if (ch == '{'){
queue.push('}');
}else if (ch == '['){
queue.push(']');
}else if (!queue.isEmpty() && queue.peek() == ch){
queue.pop();
}else {
return false;
}
}
return queue.isEmpty();
}
}
class Solution {
public boolean isValid(String s) {
Deque<Character> queue = new LinkedList<>();
char ch;
for (int i = 0; i < s.length(); i++) {
ch = s.charAt(i);
if (ch == '('|| ch=='[' || ch == '{'){
queue.push(ch);
}else {//是右半部分
if (!queue.isEmpty() && leftOf(ch) == queue.peek()){
queue.pop();
}else {
return false;
}
}
}
return queue.isEmpty();
}
private char leftOf(char ch){
if (ch == ']') return '[';
if (ch == '}') return '{';
return '(';
}
}
1047. 删除字符串中的所有相邻重复项
使用栈
class Solution {
public String removeDuplicates(String s) {
Deque<Character> queue = new LinkedList<>();
ArrayList<String> result = new ArrayList<>();
char ch;
for (int i = 0; i < s.length(); i++) {
ch = s.charAt(i);
if (queue.isEmpty() || queue.peek() != ch){
queue.push(ch);;
}else {
queue.pop();
}
}
String str = "";
//剩余的元素即为不重复的元素
while (!queue.isEmpty()) {
str = queue.pop() + str;
}
return str;
}
}
使用栈(使用字符串作为栈)
栈在本质上只是一个多加限制的数组
class Solution {
public String removeDuplicates(String s) {
// 将 res 当做栈
StringBuffer res = new StringBuffer();
// top为 res 的长度
int top = -1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 当 top > 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--
if (top >= 0 && res.charAt(top) == c) {
res.deleteCharAt(top);
top--;
// 否则，将该字符 入栈，同时top++
} else {
res.append(c);
top++;
}
}
return res.toString();
}
}
使用双指针
class Solution {
public String removeDuplicates(String s) {
char[] ch = s.toCharArray();
int fast = 0;
int slow = 0;
while(fast < s.length()){
// 直接用fast指针覆盖slow指针的值
ch[slow] = ch[fast];
// 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
if(slow > 0 && ch[slow] == ch[slow - 1]){
slow--;
}else{
slow++;
}
fast++;
}
return new String(ch,0,slow);
}
}
150. 逆波兰表达式求值
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> queue = new LinkedList<>();
//Deque<String> numbers = new LinkedList<>();
for (String token : tokens) {
if (token.equals("/") || token.equals( "*") || token.equals("+") || token.equals("-")){
Integer num1 = queue.poll();
//queue.poll();
Integer num2 = queue.poll();
if (token.equals("/") ){
int temp = num2/num1;
queue.push(temp);
}else if (token.equals( "*")){
int temp = num1*num2;
queue.push(temp);
}else if (token.equals("-")){
int temp = num2-num1;
queue.push(temp);
}else {
int temp = num2+num1;
queue.push(temp);
}
}else {
queue.push(Integer.valueOf(token));
}
}
return queue.peek();
}
}
239. 滑动窗口最大值—-不会
class Solution {
/* 单调队列的实现 */
class MonotonicQueue {
LinkedList<Integer> q = new LinkedList<>();
public void push(int n) {
// 将小于 n 的元素全部删除
while (!q.isEmpty() && q.getLast() < n) {
q.pollLast();
}
// 然后将 n 加入尾部
q.addLast(n);
}
public int max() {
return q.getFirst();
}
public void pop(int n) {
if (n == q.getFirst()) {
q.pollFirst();
}
}
}
/* 解题函数的实现 */
int[] maxSlidingWindow(int[] nums, int k) {
MonotonicQueue window = new MonotonicQueue();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i < k - 1) {
//先填满窗口的前 k - 1
window.push(nums[i]);
} else {
// 窗口向前滑动，加入新数字
window.push(nums[i]);
// 记录当前窗口的最大值
res.add(window.max());
// 移出旧数字
window.pop(nums[i - k + 1]);
}
}
// 需要转成 int[] 数组再返回
int[] arr = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
arr[i] = res.get(i);
}
return arr;
}
}
347. 前 K 个高频元素
// 借助 HashMap 数据结构
public int[] topKFrequent(int[] nums, int k) {
int[] res = new int[k]; // 结果数组
Map<Integer, Integer> map = new HashMap();
// 统计数组中各元素出现的次数
for(int num : nums){
if(map.containsKey(num)){
map.put(num, map.get(num) + 1);
}else{
map.put(num, 1);
}
}
int maxTimes = 0; // 出现最多的元素的出现次数
// 找出出现次数最多的元素出现的次数
for(Map.Entry<Integer, Integer> entry : map.entrySet()){
if(entry.getValue() > maxTimes){
maxTimes = entry.getValue();
}
}
// 按出现次数从大到小添加到结果数组
while(k > 0){
for(Map.Entry<Integer, Integer> entry : map.entrySet()){
if(entry.getValue() == maxTimes){
res[k - 1] = entry.getKey();
k--;
}
}
maxTimes--;
}
return res;
}
若有收获，就点个赞吧
0 人点赞
