public class StackDemo { public static void main(String args[]) { // Creating an empty Stack Stack<Integer> stack = new Stack<Integer>(); // Use add() method to add elements stack.push(10); stack.push(15); stack.push(30); stack.push(20); stack.push(5); // Displaying the Stack System.out.println("Initial Stack: " + stack); // Removing elements using pop() method System.out.println("Popped element: " + stack.pop()); System.out.println("Popped element: " + stack.pop()); // Displaying the Stack after pop operation System.out.println("Stack after pop operation " + stack); } }
Output:
1 2 3 4
Initial Stack: [10, 15, 30, 20, 5] Popped element: 5 Popped element: 20 Stack after pop operation [10, 15, 30]
stack.isEmpty()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
import java.util.Stack; public class StackExample { public static void main(String[] args) { // Create a new stack Stack<Integer> stack = new Stack<>(); // Push elements onto the stack stack.push(1); stack.push(2); stack.push(3); stack.push(4); // Pop elements from the stack while(!stack.isEmpty()) { System.out.println(stack.pop()); } } }
add() - Inserts the specified element into the queue. If the task is successful, add() returns true, if not it throws an exception.
offer() - Inserts the specified element into the queue. If the task is successful, offer() returns true, if not it returns false.
element() - Returns the head of the queue. Throws an exception if the queue is empty.
peek() - Returns the head of the queue. Returns null if the queue is empty.
remove() - Returns and removes the head of the queue. Throws an exception if the queue is empty. poll() - Returns and removes the head of the queue. Returns null if the queue is empty.
// Push elements onto the stack stack.push("First"); stack.push("Second"); stack.push("Third");
// Check if the stack contains a specific element StringelementToCheck="Second"; booleancontainsElement= stack.contains(elementToCheck);
if (containsElement) { System.out.println("The stack contains " + elementToCheck); } else { System.out.println("The stack does not contain " + elementToCheck); } } }
Deque:
Deque deque = new LinkedList<>();
addFirst addLast
removeFirst removeLast
getFirst getLast
deque.size( ) deque.isEmpty()
In Java, a Deque (Double-Ended Queue) is an interface that provides various methods to perform basic operations on a double-ended queue, which allows you to add and remove elements from both ends (front and rear) of the queue. The LinkedList class is a commonly used implementation of the Deque interface. Here are some basic operations you can perform with a Deque in Java:
Adding Elements:
addFirst(E e) or offerFirst(E e): Adds an element to the front of the deque.
addLast(E e) or offerLast(E e): Adds an element to the end (rear) of the deque.
1 2 3
Deque<Integer> deque = new LinkedList<>(); deque.addFirst(1); deque.addLast(2);
Removing Elements: !!!!
removeFirst() or pollFirst(): Removes and returns the element at the front of the deque. Returns null if the deque is empty (for pollFirst).
removeLast() or pollLast(): Removes and returns the element at the end (rear) of the deque. Returns null if the deque is empty (for pollLast).
1 2
int front = deque.removeFirst(); int rear = deque.pollLast();
**Accessing Elements: **!!!
getFirst() or peekFirst(): Returns the element at the front of the deque without removing it. Returns null if the deque is empty (for peekFirst).
getLast() or peekLast(): Returns the element at the end (rear) of the deque without removing it. Returns null if the deque is empty (for peekLast).
1 2
int front = deque.getFirst(); int rear = deque.peekLast();
Size and Empty Checks:
size(): Returns the number of elements in the deque.
isEmpty(): Checks if the deque is empty.
1 2
int size = deque.size(); boolean isEmpty = deque.isEmpty();
Iteration:
You can iterate over the elements in a deque using an enhanced for loop or an iterator.
1 2 3 4 5 6 7 8 9
for (Integer element : deque) { System.out.println(element); }
Iterator<Integer> iterator = deque.iterator(); while (iterator.hasNext()) { Integer element = iterator.next(); System.out.println(element); }
These are some of the basic operations you can perform on a Deque in Java. Depending on your needs, you can choose the appropriate methods to manipulate the double-ended queue as a stack, queue, or both.
// Java program to demonstrate the working // of a Deque in Java import java.util.*; publicclassDequeExample { publicstaticvoidmain(String[] args) { Deque<String> deque = newLinkedList<String>(); // We can add elements to the queue // in various ways // Add at the last deque.add("Element 1 (Tail)"); // Add at the first deque.addFirst("Element 2 (Head)"); // Add at the last deque.addLast("Element 3 (Tail)"); // Add at the first deque.push("Element 4 (Head)"); // Add at the last deque.offer("Element 5 (Tail)"); // Add at the first deque.offerFirst("Element 6 (Head)"); System.out.println(deque + "\n"); // We can remove the first element // or the last element. deque.removeFirst(); deque.removeLast(); System.out.println("Deque after removing " + "first and last: " + deque); } }
Output
1 2 3
[Element 6 (Head), Element 4 (Head), Element 2 (Head), Element 1 (Tail), Element 3 (Tail), Element 5 (Tail)]
Deque after removing first and last: [Element 4 (Head), Element 2 (Head), Element 1 (Tail), Element 3 (Tail)]
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() { clearStack(); return stackOut.pop(); } public int peek() { clearStack(); return stackOut.peek(); } public boolean empty() { return stackIn.isEmpty() && stackOut.isEmpty(); } //notice！！！！！ private void clearStack(){ // double stacks, inmotating queue //在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。 if(stackOut.isEmpty()) { //important!!! stackout 全部搬空了以后再进数据，不然顺序会乱 while(!stackIn.isEmpty()){ //important //make sure stackIn is always emtpy, everytime there's new element added to the stack it will be added to stackOut imediately stackOut.push(stackIn.pop()); } }
// use two queues: i feel like this method is harder to think class MyStack { Queue<Integer> que1; Queue<Integer> que2;
public MyStack() { que1 = new LinkedList<>(); que2 = new LinkedList<>(); } public void push(int x) { //que2 would always be empty at the end que2.add(x); while(!que1.isEmpty()){ que2.add(que1.poll()); } Queue<Integer> temp; temp = que1; que1=que2; que2 = temp; } public int pop() { return que1.poll(); } public int top() { return que1.peek(); } public boolean empty() { return que1.isEmpty(); } }
You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two !adjacent! and equal letters and removing them.
We repeatedly make duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.
// everytime i run this version there's a bug I dont know why
class Solution { public int evalRPN(String[] tokens) { Deque<Integer> que = new LinkedList<>(); char c; int res =0; for(int i = 0; i < tokens.length; i++){ c = tokens[i].charAt(0); if(Character.isDigit(c)){ que.push(c - '0'); }else{ int a = que.pop(); int b = que.pop(); if(c == '+'){ res = a + b; }else if(c == '-'){ res = b - a; }else if(c == '*'){ res = a * b; }else { res = b / a; } que.push(res); } } return que.pop(); } }
// right:
//leetcode class Solution { public int evalRPN(String[] tokens) { Deque<Integer> stack = new LinkedList(); for (String s : tokens) { if ("+".equals(s)) { // leetcode 内置jdk的问题，不能使用==判断字符串是否相等 stack.push(stack.pop() + stack.pop()); // 注意 - 和/ 需要特殊处理 } else if ("-".equals(s)) { stack.push(-stack.pop() + stack.pop()); //!!!!!!!!!!!!!! } else if ("*".equals(s)) { stack.push(stack.pop() * stack.pop()); } else if ("/".equals(s)) { //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!secon int temp1 = stack.pop(); int temp2 = stack.pop(); stack.push(temp2 / temp1); } else { stack.push(Integer.valueOf(s)); } } return stack.pop(); } }
//my + chatgpt: class Solution { public int evalRPN(String[] tokens) { Deque<Integer> stack = new LinkedList<>(); for (String token : tokens) { if (isNumeric(token)) { stack.push(Integer.parseInt(token)); } else { int a = stack.pop(); int b = stack.pop(); int res = 0; if(token.equals("+")){ res = a+b; } if(token.equals("-")){ res = b-a; } if(token.equals("*")){ res= a*b; } if(token.equals("/")){ res=b/a; } stack.push(res); } } return stack.pop(); }
class Solution { public int evalRPN(String[] tokens) { int res = 0; Deque<Integer> dq = new LinkedList<>(); for(String s : tokens){ if(s.equals("+")){ int num1 = dq.getLast(); int num2 = dq.getLast(); dq.removeLast(); dq.removeLast(); res = num1 + num2; dq.addLast(res); }else if(s.equals("-")){ int num1 = dq.getLast(); int num2 = dq.getLast(); dq.removeLast(); dq.removeLast(); res = num2 - num1; dq.addLast(res); }else if(s.equals("*")){ int num1 = dq.getLast(); int num2 = dq.getLast(); dq.removeLast(); dq.removeLast(); res = num2 * num1; dq.addLast(res); }else if(s.equals("/")){ int num1 = dq.getLast(); int num2 = dq.getLast(); dq.removeLast(); dq.removeLast(); res = num2 / num1; dq.addLast(res);
// right version: class Solution { public int evalRPN(String[] tokens) { Deque<Integer> dq = new LinkedList<>(); for (String s : tokens) { if (s.equals("+")) { int num1 = dq.removeLast(); int num2 = dq.removeLast(); int res = num2 + num1; dq.addLast(res); } else if (s.equals("-")) { int num1 = dq.removeLast(); int num2 = dq.removeLast(); int res = num2 - num1; // Corrected the order of operands here dq.addLast(res); } else if (s.equals("*")) { int num1 = dq.removeLast(); int num2 = dq.removeLast(); int res = num2 * num1; dq.addLast(res); } else if (s.equals("/")) { int num1 = dq.removeLast(); int num2 = dq.removeLast(); int res = num2 / num1; // Corrected the order of operands here dq.addLast(res); } else { dq.addLast(Integer.parseInt(s)); } } return dq.getFirst(); } }
In both code blocks, the goal is to perform division on the two most recent elements from the Deque (num1 and num2) and then add the result back to the Deque. However, the difference lies in the order of retrieving and removing those elements from the Deque. Here’s a step-by-step explanation:
Code Block 1:
1 2 3 4 5 6
javaCopy codeint num1 = dq.getLast(); // Retrieve the last element int num2 = dq.getLast(); // Retrieve the second-to-last element dq.removeLast(); // Remove the last element dq.removeLast(); // Remove the second-to-last element res = num2 / num1; // Perform division dq.addLast(res); // Add the result back to the Deque
Code Block 2:
1 2 3 4
javaCopy codeint num1 = dq.removeLast(); // Remove and retrieve the last element int num2 = dq.removeLast(); // Remove and retrieve the second-to-last element int res = num2 / num1; // Perform division dq.addLast(res); // Add the result back to the Deque
In both cases, the division operation is the same, but here’s the key difference:
Code Block 1: It first retrieves the elements (num1 and num2) and then removes them from the Deque. This means that even if an exception occurred during the division (e.g., division by zero), the elements would have already been removed from the Deque, potentially altering its state.
Code Block 2: It directly uses removeLast() to both retrieve and remove the elements. This ensures that the elements are removed from the Deque after the division is performed. If an exception occurred during the division, the Deque would remain unchanged.
In terms of functionality, both code blocks perform the same division operation. However, Code Block 2 is safer because it preserves the integrity of the Deque even in the presence of exceptions during the division operation.
// use an array to save numbers into different bucket whose index is the frequency public class Solution { public List<Integer> topKFrequent(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<>(); for(int n: nums){ map.put(n, map.getOrDefault(n,0)+1); } // corner case: if there is only one number in nums, we need the bucket has index 1. List<Integer>[] bucket = new List[nums.length+1]; //!!!! this is an array for(int n:map.keySet()){ int freq = map.get(n); if(bucket[freq]==null) bucket[freq] = new LinkedList<>(); bucket[freq].add(n); } List<Integer> res = new LinkedList<>(); for(int i=bucket.length-1; i>0 && k>0; --i){ if(bucket[i]!=null){ List<Integer> list = bucket[i]; res.addAll(list); k-= list.size(); } } return res; } }
List<Integer>[] is an array where each element is of type List<Integer>. Each element in the array can hold a reference to a list of integers (List<Integer>).\javaCopy code
1 2 3 4
LinkedList.addAll vs. add
LinkedList<Integer> list1 = new LinkedList<>(); list1.add(1); list1.add(2); LinkedList<Integer> list2 = new LinkedList<>(); list2.add(3); list2.add(4); list1.addAll(list2); // Merges list2 into list1
A PriorityQueue in Java is an implementation of a priority queue data structure. It is part of the Java Collections Framework and is used to store elements in a way that allows for efficient retrieval of the element with the highest (or lowest) priority based on a specified comparator or the natural ordering of the elements.
Here are key points about PriorityQueue:
Priority Ordering: Elements in a PriorityQueue are stored in a way that maintains a priority order. The element with the highest priority (according to the specified comparator or natural ordering) is always at the front of the queue.
Adding Elements: You can add elements to a PriorityQueue using the add or offer methods. When you add elements, they are placed in their appropriate position based on their priority.
1 2 3 4
PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.add(3); pq.add(1); pq.add(2);
After these operations, the pq will contain [1, 3, 2], where 1 has the highest priority.
Removing Elements: You can remove the element with the highest priority using the poll method, which removes and returns the top element.
1
int highestPriority = pq.poll(); // Removes and returns the highest priority element (1 in this case)
Peeking: You can examine the element with the highest priority without removing it using the peek method.
1
int highestPriority = pq.peek(); // Returns the highest priority element without removing it (1 in this case)
Custom Comparators: You can define custom comparators to specify how elements are prioritized. Alternatively, if elements implement the Comparable interface, they will be ordered based on their natural ordering.
1
PriorityQueue<String> customPq = new PriorityQueue<>(Comparator.reverseOrder()); // Creates a descending order priority queue
Performance: The PriorityQueue implementation typically provides efficient add, poll, and peek operations. These operations have logarithmic time complexity.
PriorityQueue is commonly used in various algorithms and data structures, such as Dijkstra’s algorithm for finding the shortest path in a graph, Prim’s algorithm for minimum spanning trees, and more, where elements need to be processed in a certain order based on their priorities.
In a PriorityQueue in Java, by default, the first element you remove using the poll() method is the element with the smallest priority, not necessarily the largest. The default behavior is to prioritize elements based on their natural ordering (if they implement the Comparable interface) or based on a specified comparator that you can provide when creating the PriorityQueue.
So, after you remove the first element with poll(), the next element you remove will be the one with the next smallest priority, and so on, until the queue is empty.
Here’s an example of a PriorityQueue that prioritizes elements in ascending order (smallest element first):
1 2 3 4 5 6 7 8
PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.add(3); pq.add(1); pq.add(2);
int smallest = pq.poll(); // Removes and returns the smallest element (1) int nextSmallest = pq.poll(); // Removes and returns the next smallest element (2) int last = pq.poll(); // Removes and returns the last element (3)
If you want to prioritize elements in descending order (largest element first), you can create a PriorityQueue with a custom comparator:
PriorityQueue<Integer> descendingPq = new PriorityQueue<>(Collections.reverseOrder()); descendingPq.add(3); descendingPq.add(1); descendingPq.add(2);
int largest = descendingPq.poll(); // Removes and returns the largest element (3) int nextLargest = descendingPq.poll(); // Removes and returns the next largest element (2) int smallest = descendingPq.poll(); // Removes and returns the smallest element (1)
import java.util.*;
PriorityQueue<Integer> descendingPq = new PriorityQueue<>((a, b) -> b - a); descendingPq.add(3); descendingPq.add(1); descendingPq.add(2);
int largest = descendingPq.poll(); // Removes and returns the largest element (3) int nextLargest = descendingPq.poll(); // Removes and returns the next largest element (2) int smallest = descendingPq.poll(); // Removes and returns the smallest element (1)
In this case, with the Collections.reverseOrder() comparator, the PriorityQueue prioritizes elements in descending order.
java List
When it comes to using the common methods provided by the List interface, such as add, remove, get, and others, the syntax for ArrayList and LinkedList is the same. This is because both ArrayList and LinkedList are implementations of the List interface, so they share the same method signatures.
Here’s an example of some common methods with the same syntax for both ArrayList and LinkedList:
classMinStack { Stack<Integer> stack1; Stack<Integer> min; // used to store the min value for the stack1, if you cant understand use draw it. publicMinStack() { stack1 = newStack<Integer>(); min = newStack<Integer>(); } publicvoidpush(int val) { stack1.push(val); if(min.isEmpty() || val <= min.peek()) min.push(val); // notice here is <= not < } publicvoidpop() { intpopped= stack1.pop(); if(popped == min.peek()) min.pop(); } publicinttop() { return stack1.peek(); } publicintgetMin() { return min.peek(); } }
/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */
class Solution { public boolean checkValidString(String s) { Stack<Integer> open = new Stack<>(); //!!! it's Stack<Integer> not character Stack<Integer> star = new Stack<>();
for (int i = 0; i < s.length(); i++) { if(s.charAt(i) == '(') {open.push(i);} else if(s.charAt(i) == '*') {star.push(i);} else { if(!open.isEmpty()) {open.pop();} // found matched '('with')' else if (!star.isEmpty()) {star.pop();} // match '*' with ')' else return false; // cannot find match } }
// checking leftover on 2 stack while(!open.isEmpty()) { // we can have '*' leftover, but 'open' must run out if(star.isEmpty()) {return false;} // '(' leftover else if (open.peek()<star.peek()){open.pop(); star.pop();} // '*'index > '(' index, matched else {return false;} // open>top, corner case } return true; } }
A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.
For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.
A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty valid parentheses strings.
Given a valid parentheses string s, consider its primitive decomposition: s = P1 + P2 + ... + Pk, where Pi are primitive valid parentheses strings.
Return safter removing the outermost parentheses of every primitive string in the primitive decomposition ofs.
Example 1:
1 2 3 4 5
Input: s = "(()())(())" Output: "()()()" Explanation: The input string is "(()())(())", with primitive decomposition "(()())" + "(())". After removing outer parentheses of each part, this is "()()" + "()" = "()()()".
You are given a 0-indexed string expression of the form "<num1>+<num2>" where <num1> and <num2> represent positive integers.
Add a pair of parentheses to expression such that after the addition of parentheses, expression is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of '+' and the right parenthesis must be added to the right of '+'.
Return expressionafter adding a pair of parentheses such thatexpressionevaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.
The input has been generated such that the original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.
Example 1:
1 2 3 4 5
Input: expression = "247+38" Output: "2(47+38)" Explanation: The expression evaluates to 2 * (47 + 38) = 2 * 85 = 170. Note that "2(4)7+38" is invalid because the right parenthesis must be to the right of the '+'. It can be shown that 170 is the smallest possible value.
class Solution { public String minimizeResult(String expression) { String[] sp = expression.split("\\+"); String left = sp[0]; String right = sp[1]; int min = Integer.MAX_VALUE; String result = "(" + expression + ")"; for(int i=0; i<left.length(); i++) { //Index at which we add `(` for left int leftMul = left.substring(0, i).equals("") ? 1 : Integer.parseInt(left.substring(0,i)); int leftNum = Integer.parseInt(left.substring(i)); for(int j=1; j<=right.length(); j++) { //Index at which we add `)` for right int rightMul = right.substring(j).equals("") ? 1 : Integer.parseInt(right.substring(j)); int rightNum = Integer.parseInt(right.substring(0,j)); int sum = leftMul * (leftNum + rightNum) * rightMul; if(sum < min) { min = sum; result = left.substring(0, i) + "(" + left.substring(i) + "+" + right.substring(0, j) + ")" + right.substring(j); } } } return result; } }
The school cafeteria offers circular and square sandwiches at lunch break, referred to by numbers 0 and 1 respectively. All students stand in a queue. Each student either prefers square or circular sandwiches.
The number of sandwiches in the cafeteria is equal to the number of students. The sandwiches are placed in a stack. At each step:
If the student at the front of the queue prefers the sandwich on the top of the stack, they will take it and leave the queue.
Otherwise, they will leave it and go to the queue’s end.
This continues until none of the queue students want to take the top sandwich and are thus unable to eat.
You are given two integer arrays students and sandwiches where sandwiches[i] is the type of the ith sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the jth student in the initial queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.
Example 1:
1 2 3 4 5 6 7 8 9 10 11 12
Input: students = [1,1,0,0], sandwiches = [0,1,0,1] Output: 0 Explanation: - Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1]. - Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1]. - Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1]. - Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0]. - Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1]. - Front student leaves the top sandwich and returns to the end of the line making students = [0,1]. - Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1]. - Front student takes the top sandwich and leaves the line making students = [] and sandwiches = []. Hence all students are able to eat.
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
