catalogue

4.1} implement stack with two queues

4.2 implementing stack with a queue

# 1, Bracket matching problem

The title is described as follows:

Solution idea: use the stack to solve the problem. Scan the string. When the left bracket is encountered, directly enter the stack. When the right bracket is scanned, pop up the top element of the stack to check whether it matches. If not, directly false. Otherwise, repeat the above process.

Two boundary problems:

- After scanning the string, if the stack is not empty, it indicates that there are too many left parentheses and no matching right parentheses. It is directly false.
- When scanning the first right parenthesis, it is found that the stack is empty, indicating that the right parenthesis is the first character of the string, and there is no matching left parenthesis. It is directly false.

The code is as follows:

public class Num20 { public boolean isValid(String s) { Stack<Character> stack=new Stack<>(); for (int i = 0; i < s.length(); i++) { char c=s.charAt(i); //Left bracket stack if(c=='{'||c=='['||c=='('){ stack.push(c); }else{ //When the stack is empty, the description has only right parentheses if(stack.isEmpty()){ return false; } //Left bracket out of stack char top=stack.pop(); if(c==')'&&top!='('){ return false; } if (c==']'&&top!='['){ return false; } if(c=='}'&&top!='{'){ return false; } } } //There are extra left parentheses in the stack if(!stack.isEmpty()){ return false; }else { return true; } } }

# 2, Implement a minimum stack

The title is described as follows:

Solution idea: use double stack to solve the problem, where s1 is the stack that actually stores elements and s2 is the stack that stores the current minimum value. When elements are stacked, s1 is stacked in turn. When s2 is stacked, it is necessary to compare the stacked elements with the current stack top element. If the current stacked element is smaller than the stack top element, put the current stacked element into the stack, otherwise put the current stack top element into the stack again, So getMin() -- just take the stack top element of s2 directly.

The code is as follows:

public class MinStack { //Stack s1 of actual storage elements private Stack<Integer> s1=new Stack<>(); //Stack s2 for storing minimum value private Stack<Integer> s2=new Stack<>(); public MinStack() {} public void push(int val) { //Put val into s1 stack first s1.push(val); //Judge whether s2 is empty. When it is empty, val will also be put into s2 stack if(s2.isEmpty()){ s2.push(val); }else{ //If it is not empty, judge the size of val and s2 stack top elements. If val is smaller, enter val, otherwise continue to enter s2 stack top elements if(val<s2.peek()){ s2.push(val); }else{ s2.push(s2.peek()); } } } public void pop() { //Delete the stack top element, s1 and s2 should be deleted s1.pop(); s2.pop(); } public int top() { //Take out the top element of the stack return s1.peek(); } public int getMin() { //The smallest element only needs to remove the s2 stack top element return s2.peek(); } }

# 3, Implement queue with stack

The title is described as follows:

Solution idea: use two stacks to solve the problem. s1 is the stack for actually storing elements and s2 is the auxiliary stack. Each time you add an element, you must ensure that s1 is empty, so that the new element is just at the bottom of the stack.

The code is as follows:

public class MyQueue { //s1 is used to store elements private Stack<Integer> s1=new Stack<>(); //s2 is used as an aid private Stack<Integer> s2=new Stack<>(); public MyQueue() { } public void push(int x) { //Judge whether s1 is empty. When it is empty, add a new element directly. At this time, x is at the bottom of s1 stack if(s1.isEmpty()){ s1.push(x); }else{ //When s1 is not empty, all elements in s1 are sequentially stacked in s2 while(!s1.isEmpty()){ int y=s1.pop(); s2.push(y); } //At this time, s1 is empty, and then add a new element to s1. At this time, x is at the bottom of the stack of s1 s1.push(x); //Pop up the elements in s2 again and then enter s1 stack while(!s2.isEmpty()){ int z=s2.pop(); s1.push(z); } } } public int pop() { return s1.pop(); } public int peek() { return s1.peek(); } public boolean empty() { return s1.isEmpty(); } }

# 4, Implement stack with queue

## 4.1} implement stack with two queues

The title is described as follows:

Problem solving idea: use two queues to solve the problem. q1 is the queue that actually stores elements, and q2 is the auxiliary queue. Ensure that q2 is always empty after adding elements (new elements enter q2 directly), and ensure that new elements are at the end of the queue.

The code is as follows:

public class MyStack { //q1 is used to store elements private Queue<Integer> q1=new LinkedList<>(); //q2 is always empty as an auxiliary private Queue<Integer> q2=new LinkedList<>(); public MyStack() { } public void push(int x) { //The new element joins the team, and at this time, the new element is at the head of the q2 team q2.offer(x); //When q1 is not empty, the elements in q1 are dequeued into q2 while(!q1.isEmpty()){ q2.offer(q1.poll()); } //At this time, q1 is empty and q2 is the queue of storage elements. Exchange the points of q1 and q2. At this time, q2 is empty Queue<Integer> tmp=q1; q1=q2; q2=tmp; } public int pop() { return q1.poll(); } public int top() { return q1.peek(); } public boolean empty() { return q1.isEmpty(); } }

## 4.2 implementing stack with a queue

Problem solving idea: first join the team, then take the previous elements out of the team in turn (ensure that the new elements are at the end of the team), and then join the team in turn.

The code is as follows:

public class MyStackⅡ { private Queue<Integer> queue=new LinkedList<>(); public void push(int x){ //Number of record elements int size=queue.size(); //Add new elements to the team queue.offer(x); //Take the previous elements out of the team and then into the team for (int i = 0; i < size; i++) { queue.offer(queue.poll()); } } public int pop(){ return queue.poll(); } public int top(){ return queue.peek(); } public boolean empty(){ return queue.isEmpty(); } }

# 5, Design cyclic queue

The title is described as follows:

The code is as follows:

/** * Design cyclic queue */ public class MyCircularQueue { //Points to the queue head element of the circular queue private int head; //End of queue element pointing to a circular queue private int tail; //Array of actual storage elements private int[] data; public MyCircularQueue(int k) { //k+1 is because it wastes a space to judge whether the queue is full this.data=new int[k+1]; } public boolean enQueue(int value) { if (isFull()){ return false; }else{ data[tail]=value; tail=(tail+1)%data.length; return true; } } public boolean deQueue() { if (isEmpty()){ return false; }else{ head=(head+1)%data.length; return true; } } public int Front() { if (isEmpty()){ return -1; }else{ return data[head]; } } public int Rear() { if (isEmpty()){ return -1; }else{ //Gets the index of the last element int lastIndex=(tail==0?data.length-1:tail-1); return data[lastIndex]; } } public boolean isEmpty() { return head==tail; } public boolean isFull() { return (tail+1)%data.length==head; } }

# 6, Next larger element

The title is described as follows:

Solution idea: use the monotone stack to solve the problem and maintain a monotone increasing stack (the elements from the top of the stack to the bottom of the stack increase in turn). This problem can only look at nums2. Look backwards from the last element of nums2 to the right, find the next larger element of each element in nums2, and traverse nums2. When the traversal element is larger than the element at the top of the stack, Go out of the stack until the top element is larger than the current element or the stack is empty. When the stack is empty, return - 1, indicating that there is no element at the top of the current stack that is larger than the current element.

The code is as follows:

/** * The monotone stack solves the next larger element problem */ public class Num496_nextGreaterElement { //Monotone stack private Stack<Integer> stack=new Stack<>(); //Store each element in nums2 and their next larger element private Map<Integer,Integer> map=new HashMap<>(); public int[] nextGreaterElement(int[] nums1, int[] nums2) { //Scan nums2 to find the next larger element of each element in nums2 for (int i = nums2.length-1; i >=0 ; i--) { //When the stack is empty and the top element of the stack is smaller than the current element, the elements in the stack are out of the stack, // Until the top element of the stack is larger than the current element or the stack is empty while(!stack.isEmpty()&&stack.peek()<=nums2[i]){ stack.pop(); } int nextGreaterValue=stack.isEmpty()?-1:stack.peek(); //After processing the current element, push the current element onto the stack stack.push(nums2[i]); map.put(nums2[i],nextGreaterValue); } //Scan nums1 and take out the nextGreaterValue corresponding to each element int[] ret=new int[nums1.length]; for (int i = 0; i < nums1.length; i++) { ret[i]=map.get(nums1[i]); } return ret; } }