栈和队列：容器适配器，不提供迭代器
232、用栈实现队列
class MyQueue {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public MyQueue() {
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int peek() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
public boolean empty() {
if(stack1.isEmpty() && stack2.isEmpty()){
return true;
}
return false;
}
}
/**
* 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、用队列实现栈
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;//用来备份栈的数据（除栈顶）
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
// 方法一：较为繁琐
// public void push(int x) {
// while(queue1.size() > 0){
// queue2.offer(queue1.poll());
// }
// while(queue2.size() > 0){
// queue1.offer(queue2.poll());
// }
// queue1.offer(x);
// }
// public int pop() {
// while(queue1.size() > 1){
// queue2.offer(queue1.poll());
// }
// int temp = queue1.poll();
// while(queue2.size() > 0){
// queue1.offer(queue2.poll());
// }
// return temp;
// }
// public int top() {
// while(queue1.size() > 1){
// queue2.offer(queue1.poll());
// }
// int temp = queue1.peek();
// while(queue1.size() > 0){
// queue2.offer(queue1.poll());
// }
// while(queue2.size() > 0){
// queue1.offer(queue2.poll());
// }
// return temp;
// }
// public boolean empty() {
// return queue1.isEmpty() && queue2.isEmpty();
// }
// 方法二：参考代码随想录
// public void push(int x) {
// queue2.offer(x);
// while(!queue1.isEmpty()){
// queue2.offer(queue1.poll());
// }
// Queue<Integer> temp = new LinkedList<>();
// queue1 = queue2;
// queue2 = temp;
// }
// public int pop() {
// return queue1.poll();
// }
// public int top() {
// return queue1.peek();
// }
// public boolean empty() {
// return queue1.isEmpty() && queue2.isEmpty();
// }
// 方法三：用单队列实现
public void push(int x) {
if(queue1.isEmpty()){
queue1.offer(x);
}else{
int count = queue1.size();
queue1.offer(x);
while(count > 0){
queue1.offer(queue1.poll());
count--;
}
}
}
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();
*/
20、有效的括号
class Solution {
public boolean isValid(String s) {
// 方法一：用字符串
// String s1 = "";
// if(s.length()%2 == 1){
// return false;
// }
// for(int i = 0; i < s.length(); i++){
// if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){
// s1 = s1 + s.charAt(i);
// }else if(s1.length() == 0){
// return false;
// }else if((s.charAt(i) == ']') && (s1.charAt(s1.length()-1) == '[')){
// s1 = s1.substring(0,s1.length() - 1);
// }else if((s.charAt(i) == '}') && (s1.charAt(s1.length()-1) == '{')){
// s1 = s1.substring(0,s1.length() - 1);
// }else if((s.charAt(i) == ')') && (s1.charAt(s1.length()-1) == '(')){
// s1 = s1.substring(0,s1.length() - 1);
// }else{
// return false;
// }
// }
// if(s1.length() == 0){
// return true;
// }else{
// return false;
// }
// 方法二：用栈
Stack<Character> stack = new Stack<>();
char[] arr = s.toCharArray();
for(int i = 0; i < arr.length; i++){
if(arr[i] == '(' || arr[i] == '[' || arr[i] == '{'){
stack.push(arr[i]);
}else if(arr[i] == ')'){
if(stack.isEmpty() || stack.pop() != '('){
return false;
}
}else if(arr[i] == ']'){
if(stack.isEmpty() ||stack.pop() != '['){
return false;
}
}else if(arr[i] == '}'){
if(stack.isEmpty() ||stack.pop() != '{'){
return false;
}
}
}
return stack.isEmpty();
}
}
1047、删除字符串中的所有相邻重复项
class Solution {
public String removeDuplicates(String s) {
// 方法一：用栈
char[] arr = s.toCharArray();
Stack<Character> stack = new Stack<>();
for(int i = 0; i < arr.length; i++){
if(stack.isEmpty()){
stack.push(arr[i]);
}else if(stack.peek() == arr[i]){
stack.pop();
}else{
stack.push(arr[i]);
}
}
String str = "";
while(!stack.isEmpty()){
str = stack.pop() + str;
}
return str;
// // 方法二：双线队列
// char[] arr = s.toCharArray();
// ArrayDeque<Character> arraydeque = new ArrayDeque<>();
// for(int i = 0; i < arr.length; i++){
// if(arraydeque.isEmpty()){
// arraydeque.push(arr[i]);
// }else if(arraydeque.peek() == arr[i]){
// arraydeque.pop();
// }else{
// arraydeque.push(arr[i]);
// }
// }
// String str = "";
// while(!arraydeque.isEmpty()){
// str = arraydeque.pop() + str;
// }
// return str;
}
}
150、逆波兰表达式求值
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < tokens.length; i++){
if(tokens[i].equals("+")){
stack.push(stack.pop() + stack.pop());
}else if(tokens[i].equals("-")){
stack.push(-stack.pop() + stack.pop());
}else if(tokens[i].equals("*")){
stack.push(stack.pop() * stack.pop());
}else if(tokens[i].equals("/")){
int divisor = stack.pop();
int dividend = stack.pop();
int temp = dividend/divisor;
stack.push(temp);
}else{
stack.push(Integer.valueOf(tokens[i]));
}
}
return stack.pop();
}
}
239、滑动窗口最大值
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 1){
return nums;
}
int[] arr = new int[nums.length - k + 1];
int index = 0;
ArrayDeque<Integer> deque = new ArrayDeque<>();
for(int i = 0; i < nums.length; i++){
if(deque.isEmpty()){
deque.offer(i);
if(i >= k - 1){
arr[index++] = nums[deque.peek()];
}
continue;
}
if(deque.size() >= k || deque.peek() < i - k + 1){
deque.poll();
}
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){
deque.pollLast();
}
deque.offer(i);
if(i >= k - 1){
arr[index++] = nums[deque.peek()];
}
}
return arr;
}
}
347、前 K 个高频元素
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int i: nums){
map.put(i, map.getOrDefault(i, 0) + 1);
}
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] m, int[] n){
return m[1] - n[1];
}
});
for(Map.Entry<Integer, Integer> entry: map.entrySet()){
if(pq.size() < k){
pq.add(new int[]{entry.getKey(), entry.getValue()});
}else{
if(pq.peek()[1] < entry.getValue()){
pq.poll();
pq.add(new int[]{entry.getKey(), entry.getValue()});
}
}
}
int[] arr = new int[k];
for(int i = 0; i < arr.length; i++){
arr[i] = pq.poll()[0];
}
return arr;
}
}