Leetcode232（用栈实现队列）
package stack_queue;
import java.util.Stack;
public class Leetcode232 {
public static void main(String[] args) {
MyQueue myQueue = new MyQueue();
myQueue.push(1);
myQueue.push(2);
System.out.print(myQueue.peek());
System.out.print(myQueue.peek());
System.out.print(myQueue.isEmpty());
}
}
class MyQueue{
Stack<Integer> stackIn;
Stack<Integer> stackOut;
//初始化
public MyQueue() {
this.stackIn = new Stack<>();
this.stackOut = new Stack<>();
}
public void push(int x) {
stackIn.push(x);
}
public boolean isEmpty() {
return stackIn.empty()&&stackOut.empty();
}
public int pop() {
dumpStackIn();
return stackOut.pop();
}
public int peek() {
dumpStackIn();
return stackOut.peek();
}
private void dumpStackIn() {
if(!stackOut.empty())return; //如果出栈不为空则什么都不做
while(!stackIn.empty()) {
stackOut.push(stackIn.pop());
}
}
}
?Leetcode235（队列实现栈）
package stack_queue;
import java.util.LinkedList;
import java.util.Queue;
public class Leetcode235 {
public static void main(String[] agrs) {
Stack02 stack = new Stack02();
stack.push(1);
stack.push(2);
stack.pop();
stack.push(3);
stack.push(4);
stack.pop();
System.out.print(stack.peek());
}
}
//单队列实现栈
class Stack02{
Queue<Integer> queue;
public Stack02() {
this.queue = new LinkedList<>();
}
public boolean isEmpty() {
return queue.isEmpty();
}
public void push(int x) {
queue.offer(x);
int size = queue.size();
size--;
while(size-->0) {
queue.offer(queue.poll());
}
}
public void pop() {
queue.poll();
}
public int peek() {
return queue.peek();
}
}
//双队列实现栈
class Stack{
Queue<Integer> queue1;
Queue<Integer> queue2;
public Stack() {
this.queue1 = new LinkedList<>();
this.queue2 = new LinkedList<>();
}
public void push(int x) {
queue2.offer(x);
while(!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> queueTemp;
queueTemp = queue1;
queue1 = queue2;
queue2 = queueTemp;
}
public int pop() {
return queue1.poll();
}
public int top() {
return queue1.peek();
}
public boolean empty() {
return queue1.isEmpty();
}
}
Leetcode20（有效括号）
package stack_queue;
import java.util.Stack;
public class Leetcode20 {
public static void main(String[] args) {
System.out.print(matchWay("("));
}
public static boolean matchWay(String str) {
Stack<Character> stack = new Stack<>();
for(int i =0;i<str.length();i++) {
char ch = str.charAt(i);
if(ch =='(') {
stack.push(')');
}else if(ch == '[') {
stack.push(']');
}else if(ch == '{') {
stack.push('}');
}else if(stack.empty()||ch!=stack.peek()) {
return false;
}else {
stack.pop();
}
}
return stack.empty();
}
}
Leetcode1047（删除字符串中的所有相邻重复项）
package stack_queue;
import java.util.Stack;
public class Leetcode1047 {
public static void main(String[] args) {
System.out.print(match("aacbbcca"));
}
//stack方法
public static String match(String str) {
Stack<Character> stack = new Stack();
for(int i =0;i<str.length();i++) {
char chars = str.charAt(i);
if(stack.empty()||stack.peek()!=chars) {
stack.push(chars);
}else {
stack.pop();
}
}
String str02 = " ";
while(!stack.empty()) {
str02 = stack.pop()+str02;
}
return str02;
}
//字符串作栈
public static String match02(String str) {
StringBuilder strBulider = new StringBuilder();
int top = -1;
for(int i=0;i<str.length();i++) {
char c = s.charAt(i);
if(top>=0&&strBulider.charAt(top)==c) {
strBulider.deleteCharAt(top);
top--;
}else {
strBulider.append(c);
top++;
}
}
return strBulider.toString();
}
}
Leetcode150（逆波兰表达式求值）
package stack_queue;
import java.util.Stack;
public class Leetcode150 {
public static void main(String[] args) {
String[] strs = {"2", "1", "+", "3", "*"};
System.out.print(compucter(strs));
}
public static int compucter(String[] strs) {
Stack<Integer> stack = new Stack();
for(int i = 0;i<strs.length;i++) {
if("+".equals(strs[i])) {
stack.push(stack.pop()+stack.pop());
}else if("-".equals(strs[i])) {
stack.push(-stack.pop()+stack.pop());
}else if("*".equals(strs[i])) {
stack.push(stack.pop()*stack.pop());
}else if("/".equals(strs[i])) {
int temp1 = stack.pop();
int temp2 = stack.pop();
stack.push(temp2/temp1);
}else {
stack.push(Integer.valueOf(strs[i]));
}
}
return stack.pop();
}
}
Leetcode239（滑动窗口最大值）
package stack_queue;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
public class Leetcode239 {
public static void main(String[] args) {
int[] nums = {1,3,-1,-3,5,3,6,7};
nums = maxSlidingWindow(nums,3);
System.out.print(Arrays.toString(nums));
}
public static int[] maxSlidingWindow(int[] nums,int k) {
int count = 0;
int len = nums.length-k+1;
int[] res = new int[len];
Queue que = new Queue();
for(int i = 0;i<k;i++) {
que.add(nums[i]);
}
res[count++] = que.peek();
for(int i = k;i<nums.length;i++) {
que.poll(nums[i-k]);
que.add(nums[i]);
res[count++] = que.peek();
}
return res;
}
}
class Queue{
Deque<Integer> que = new LinkedList<>();
public void poll(int val) {
if(!que.isEmpty()&&que.peek()==val) {
que.poll();
}
}
public void add(int val) {
while(!que.isEmpty()&&que.peek()<val) {
que.poll();
}
que.add(val);
}
public int peek() {
return que.peek();
}
}
Leetcode347（前k个高频元素，小顶堆）
package stack_queue;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
public class Leetcode347 {
public static void main(String[] args) {
int[] nums = new int[] {1,2,1,4,4,4,2,3,6};
System.out.print(Solusion(nums,2));
}
public static List<Integer> Solusion(int[] nums,int k){
final Map<Integer,Integer> hashMap = new HashMap<>();
for(int i:nums) {
hashMap.put(i,hashMap.getOrDefault(i,0)+1);
}
PriorityQueue<Integer> pq = new PriorityQueue<>(k,new Comparator<Integer>() {
@Override
public int compare(Integer a,Integer b) {
return hashMap.get(a)-hashMap.get(b);
}
});
int size = 0;
for(int j:hashMap.keySet()) {
if(size<k) {
pq.offer(j);
size++;
}else if(hashMap.get(pq.peek())<hashMap.get(j)) {
pq.poll();
pq.add(j);
}
}
List<Integer> list = new ArrayList<>();
while(!pq.isEmpty()) {
list.add(pq.poll());
}
return list;
}
//小顶堆 前k个高频率
public static List<Integer> topKMax(int[] nums,int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(k);
for(int i=0;i<nums.length;i++) {
if(i<k) {
pq.offer(nums[i]);
}else if(pq.peek()<nums[i]) {
pq.poll();
pq.add(nums[i]);
}
}
List<Integer> list = new ArrayList<>();
while(!pq.isEmpty()) {
list.add(pq.poll());
}
return list;
}
//大顶堆 前k个小频率
public static List<Integer> topKMin(int[] nums,int k){
PriorityQueue<Integer> pq = new PriorityQueue<>(k,new Comparator<Integer>() {
@Override
public int compare(Integer a,Integer b) {
return b-a;
}
});
for(int i=0;i<nums.length;i++) {
if(i<k) {
pq.offer(nums[i]);
}else if(pq.peek()>nums[i]) {
pq.poll();
pq.add(nums[i]);
}
}
List<Integer> list = new ArrayList<>();
while(!pq.isEmpty()) {
list.add(pq.poll());
}
return list;
}
}
?