stack

chenweijie · chenweijie · commit 6dda9c690aa1 · 2020-10-26T23:28:07.000+08:00
diff --git a/src/main/java/com/chen/algorithm/study/test703/ObjectPriorityQueue.java b/src/main/java/com/chen/algorithm/study/test703/ObjectPriorityQueue.java
@@ -26,7 +26,7 @@ public int add(int num) {
 
         if (queue.size() < limit) {
             queue.offer(num);
-        } else if (queue.peek() > num) {
+        } else if (queue.peek() < num) {
             queue.poll();
             queue.offer(num);
         }
diff --git a/src/main/java/com/chen/algorithm/znn/stack/test225/MyStack.java b/src/main/java/com/chen/algorithm/znn/stack/test225/MyStack.java
@@ -0,0 +1,43 @@
+package com.chen.algorithm.znn.stack.test225;
+
+import java.util.LinkedList;
+import java.util.Queue;
+
+/**
+ * @Auther: zhunn
+ * @Date: 2020/10/26 22:20
+ * @Description: 用两个队列实现一个栈, 官方解法
+ */
+public class MyStack {
+
+    private Queue<Integer> q1;
+    private Queue<Integer> q2;
+
+    public MyStack() {
+        q1 = new LinkedList<>();
+        q2 = new LinkedList<>();
+    }
+
+    public void push(int value) {
+        q2.offer(value);
+        while (!q1.isEmpty()) {
+            q2.offer(q1.poll());
+        }
+
+        Queue<Integer> temp = q1;
+        q1 = q2;
+        q2 = temp;
+    }
+
+    public int pop() {
+        return q1.poll();
+    }
+
+    public int top() {
+        return q1.peek();
+    }
+
+    public boolean empty() {
+        return q1.isEmpty();
+    }
+}
diff --git a/src/main/java/com/chen/algorithm/znn/stack/test225/Solution.java b/src/main/java/com/chen/algorithm/znn/stack/test225/Solution.java
@@ -0,0 +1,41 @@
+package com.chen.algorithm.znn.stack.test225;
+
+import java.util.LinkedList;
+import java.util.Queue;
+
+/**
+ * @Auther: zhunn
+ * @Date: 2020/10/26 21:20
+ * @Description: 用两个队列实现一个栈
+ */
+public class Solution {
+
+    private Queue<Integer> q1 = new LinkedList<>();
+    private Queue<Integer> q2 = new LinkedList<>();
+    private int top;
+
+    public void push(Integer value) {
+        q1.add(value);
+        top = value;
+    }
+
+    public int pop() {
+        while (q1.size() > 1) {
+            q2.add(q1.peek());
+            top = q1.remove();
+        }
+        int result = q1.remove();
+        Queue<Integer> temp = q1;
+        q1 = q2;
+        q2 = temp;
+        return result;
+    }
+
+    public int top() {
+        return top;
+    }
+
+    public boolean empty() {
+        return q1.isEmpty() && q2.isEmpty();
+    }
+}
diff --git a/src/main/java/com/chen/algorithm/znn/stack/test703/Solution.java b/src/main/java/com/chen/algorithm/znn/stack/test703/Solution.java
@@ -0,0 +1,47 @@
+package com.chen.algorithm.znn.stack.test703;
+
+import org.junit.Test;
+
+import java.util.PriorityQueue;
+
+/**
+ * @Auther: zhunn
+ * @Date: 2020/10/26 16:55
+ * @Description: 求数组中的第K个最大元素：1-暴力；2-优先级队列
+ */
+public class Solution {
+
+    class KthLargest {
+        private PriorityQueue<Integer> queue;
+        private int limit;
+
+        public KthLargest(int size, int[] nums) {
+            this.limit = size;
+            queue = new PriorityQueue<>(limit);
+            for (int num : nums) {
+                add(num);
+            }
+        }
+
+        public int add(int num) {
+
+            if (queue.size() < limit) {
+                queue.offer(num);
+            } else if (queue.peek() < num) {
+                queue.poll();
+                queue.offer(num);
+            }
+
+            return queue.peek();
+        }
+    }
+
+
+    @Test
+    public void testCase() {
+        int[] n = {3, 2, 3, 1, 2, 4, 5, 5, 6};
+        KthLargest kthLargest = new KthLargest(2, n);
+        System.out.println(kthLargest.add(3));
+
+    }
+}

Original file line number	Diff line number	Diff line change
`@@ -26,7 +26,7 @@ public int add(int num) {`
`26`	`26`
`27`	`27`	`if (queue.size() < limit) {`
`28`	`28`	`queue.offer(num);`
`29`		`- } else if (queue.peek() > num) {`
	`29`	`+ } else if (queue.peek() < num) {`
`30`	`30`	`queue.poll();`
`31`	`31`	`queue.offer(num);`
`32`	`32`	`}`