Stack and queue oj questions
[the external chain image transfer fails. The source station may have anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-gqdvgkrh-1644978540376) (E: \ markdown \ note. 1 \ image \ image-20214095416601. PNG)]
[the external chain picture transfer fails, and the source station may have anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-cnnjaut8-1644978540377) (E: \ markdown \ note. 1 \ image \ image-20214095827779. PNG)]
The stack is first in and last out (delete and insert at the top of the stack), so you can use it in some special places, such as printing linked lists in reverse order, etc.
For example, judge the order of data stacked, and convert infix expression to suffix expression (suffix expression is also called inverse Polish expression)
[the transfer of external chain pictures fails. The source station may have anti-theft chain mechanism. It is recommended to save the pictures and upload them directly (img-UdrB9nIw-1644978540377)(E:\MarkDown\note.1\image\image-20220214101536335.png)]
Now it will be converted into a suffix expression and calculated through this expression. So how to convert to suffix expression needs to use stack
For some methods in the stack, you can check the api. The more commonly used ones are peek,pop,push,isEmpty and search
[the external chain picture transfer fails, and the source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-ZWs5OfIl-1644978540378)(E:\MarkDown\note.1\image\image-20220214102623189.png)]
public static void main(String[] args) {
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
System.out.println(stack.pop());//Pop up the top element of the stack and delete 6
System.out.println(stack.pop());//Stack element 5, and pop-up
System.out.println(stack.pop());//Pop up the top element of the stack and delete 4
System.out.println(stack.pop());//Pop up the top element of the stack and delete 3
System.out.println(stack.pop());//Pop up the top element of the stack and delete 2
System.out.println(stack.pop());//Pop up the top element of the stack and delete 1
System.out.println(stack.peek());//Get the top element of the stack, but do not delete 5
System.out.println(stack.peek());//Get the top element of the stack, but do not delete 5
System.out.println(stack.isEmpty());//false
System.out.println(stack.size());
}
Pop in and out of stack
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<>();
int j = 0;
for(int i = 0;i<pushA.length;i++){
stack.push(pushA[i]);
while(!stack.isEmpty() && j<popA.length && popA[j] == stack.peek()){
stack.pop();
j++;
}
}
return stack.isEmpty();
}
}
Inverse Polish evaluation
class Solution {
public int evalRPN(String[] tokens) {
String val = " ";
Stack<Integer> stack = new Stack<>();
for(int i = 0;i<tokens.length;i++){
val = tokens[i];
if(!isOperation(val)){
stack.push(Integer.parseInt(val));
}else{
int num2 = Integer.valueOf(stack.pop());
int num1 = Integer.valueOf(stack.pop());
switch(val){
case "+":
stack.push(num1+num2);
break;
case "-":
stack.push(num1-num2);
break;
case "*":
stack.push(num1*num2);
break;
case "/":
stack.push(num1/num2);
break;
}
}
}
return stack.pop();
}
public boolean isOperation(String x){
if(x.equals("+")||x.equals("-") || x.equals("*") || x.equals("/")){
return true;
}else{
return false;
}
}
}
The above are two problems solved by stack
The default construction method for creating stack objects actually provides 10 spaces for the stack
Realize some basic functions of stack
public class MyStack {
public int[] elem;
public int usedSize;
public MyStack() {
this.elem = new int[5];
}
public void push(int val) {
if(isFull()) {
//Capacity expansion
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[this.usedSize] = val;
this.usedSize++;
}
public boolean isFull() {
return this.usedSize == this.elem.length;
}
public int pop() {
if(isEmpty()) {
throw new RuntimeException("Stack is empty!");
}
int oldVal = this.elem[usedSize-1];
this.usedSize--;
return oldVal;
}
public int peek() {
if(isEmpty()) {
throw new RuntimeException("Stack is empty!");
}
return this.elem[usedSize-1];
}
public boolean isEmpty() {
return this.usedSize == 0;
}
}
[the external link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-q4am2ayo-1644978540378) (E: \ markdown \ note. 1 \ image \ image-20214165021507. PNG)]
Bracket matching problem
class Solution {
public boolean isValid(String s) {
Stack<String> stack = new Stack<>();
int k = 0;
for(int i = 0;i<s.length();i++){
String s1 = s.charAt(i)+"";
if(s1.equals("(") ||s1.equals("{") ||s1.equals("[")){
stack.push(s1);
k++;
}else{
switch(s1){
case ")":
if(!stack.isEmpty() && "(".equals(stack.peek())){
stack.pop();
}else{
return false;
}
break;
case "}":
if(!stack.isEmpty() && "{".equals(stack.peek())){
stack.pop();
}else{
return false;
}
break;
case "]":
if(!stack.isEmpty() && "[".equals(stack.peek())){
stack.pop();
}else{
return false;
}
break;
}
}
}
if(k != 0){
return stack.isEmpty();
}else{
return false;
}
}
}
Realize the minimum stack
//BOGO explains the last part of the section on the stack
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if(!minStack.isEmpty()){
int cur = minStack.peek();
if(val <= cur){
minStack.push(val);
}
}else{
minStack.push(val);
}
}
public void pop() {
int popVal = stack.pop();
if(!minStack.isEmpty()){
int top = minStack.peek();
if(top == popVal){
minStack.pop();
}
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
[the external chain image transfer fails. The source station may have anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-yb46ufDf-1644978540378)(E:\MarkDown\note.1\image\image-20220215102046437.png)]
At the bottom of the LinkedList is a two-way linked list
[the external chain picture transfer fails. The source station may have anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-jd1ftlvz-1644978540379) (E: \ markdown \ note. 1 \ image \ image-20215102439108. PNG)]
public static void main1(String[] args) {
//LinkedList implements Queue and Deque, and the parent class reference points to the child class object, which realizes the upward transformation, but the method
Queue<Integer> queue = new LinkedList<>(); //Ordinary queue: head in, tail in
Deque<Integer> queue2 = new LinkedList<>();//Both ends of the queue
LinkedList<Integer> list = new LinkedList<>();
The upward transformation is explained again here: the methods used by the first two references must be included in the methods of the parent class, so there are fewer methods, while the third does not use upward transformation, and there are more methods. However, if we generally use upward transformation, we don't need so many methods, which is enough for us to use, and we can clearly point out that we just want to use the Queue class.
The queue can also be implemented in the structure of array and linked list. It is better to use the structure of linked list, because if the structure of array is used, the queue is on the head of the array
The efficiency will be relatively low when the data is sent out
[the transfer of external chain pictures fails. The source station may have anti-theft chain mechanism. It is recommended to save the pictures and upload them directly (img-GtiVi14u-1644978540379)(E:\MarkDown\note.1\image\image-20220215104254245.png)]
[the external chain image transfer fails. The source station may have anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-zTEbYqmE-1644978540380)(E:\MarkDown\note.1\image\image-20220215104150567.png)]
[the external chain picture transfer fails, and the source station may have anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-hcj5DVVe-1644978540380)(E:\MarkDown\note.1\image\image-20220215104228313.png)]
public static void main(String[] args) {
MyQueue queue = new MyQueue();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.peek());//1
System.out.println(queue.poll());//1
System.out.println(queue.poll());//2
System.out.println(queue.poll());//3
System.out.println(queue.poll());//
}
public static void main2(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(2);
System.out.println(queue.peek());//1
System.out.println(queue.poll());//1
}
public static void main3(String[] args) {
Deque<Integer> queue2 = new LinkedList<>();
queue2.offerLast(1);//Default queue tail
queue2.offerFirst(2);
//2 1
System.out.println(queue2.peekFirst());//2
System.out.println(queue2.peekLast());//1
}
[the transfer of external chain pictures fails. The source station may have anti-theft chain mechanism. It is recommended to save the pictures and upload them directly (img-injrnh9j-1644978540380) (E: \ markdown \ note. 1 \ image \ image-202202151043222288. PNG)]
The above figure shows that the two-way linked list can realize ordinary queue, double ended queue and two-way linked list.
Next, a single linked list is used to implement the queue (a two-way linked list can also be used)
But if you join the team in the single linked list, the time complexity is O(1), but the time complexity of leaving the team is O(N), so you add a tail pointer
[the external link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-ewgpbetx-1644978540381) (E: \ markdown \ note. 1 \ image \ image-20215105731210. PNG)]
class Node{
public int val;
public Node next;
public Node(int val) {
this.val = val;
}
}
public class MyQueue {
public Node head;
public Node last;
public void offer(int val){
Node node = new Node(val);
if(head == null){
head = node;
last = node;
}else{
last.next = node;
last = last.next;
}
}
/**
* Out of the team
*/
public int poll(){
if(isEmpty()){
throw new RuntimeException("The queue is empty, unable to get out of the queue");
}
int oldVal = this.head.val;
this.head = head.next;
return oldVal;
}
public boolean isEmpty(){
return head == null;
}
public int peek(){
if(isEmpty()) {
throw new RuntimeException("The queue is empty, unable to get out of the queue");
}
return head.val;
}
}
Circular queue
[the external link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-zlSCVl3Y-1644978540381)(E:\MarkDown\note.1\image\image-20220215150157410.png)]
[the external chain picture transfer fails, and the source station may have anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-HEnzBkPw-1644978540381)(E:\MarkDown\note.1\image\image-20220215150248268.png)]
[the external link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-mtvJTb0R-1644978540382)(E:\MarkDown\note.1\image\image-20220215150255601.png)]
[the transfer of external chain pictures fails. The source station may have anti-theft chain mechanism. It is recommended to save the pictures and upload them directly (img-mMwt4QNq-1644978540382)(E:\MarkDown\note.1\image\image-20220215150359937.png)]
Design cyclic queue
class MyCircularQueue {
public int front;
public int rear;
public int[] elem;
public MyCircularQueue(int k) {
this.elem = new int[k+1]; //Here is the third method, which wastes a space, but you have to create another space, otherwise you won't be satisfied oj
}
/**
* Join the team
* @param value
* @return
*/
public boolean enQueue(int value) {
if(isFull()){
return false;
}
elem[rear] = value;
rear = (rear+1) % elem.length; //Every time you join the team, rear needs + +, but when you are length-1s, you have to add it and it will become subscript 0. At this time
//Using this formula
return true;
}
/**
* Out of the team
* @param
* @return
*/
public boolean deQueue() {
if(isEmpty()){
return false;
}
//It's the same every time you get out of the team. When you get out of the front to length-1, you should get out of the front + +. At this time, you need to get out to the subscript 0, but at this time, the front + + becomes length
//So we still have to use this formula
front = (front+1) % elem.length;
return true;
}
/**
* Get the team head element
* @return
*/
public int Front() {
if(isEmpty()){
return -1;
}
return elem[front];
}
public int Rear() {
if(isEmpty()){
return -1;
}
int index = -1;
//Return the element at the end of the queue (the way to waste a space). Your last element should be the position of rear-1, but when you are rear = 0, you should be the value of the length-1 subscript, which is also to judge
if(rear == 0 ){
index = elem.length-1;
}else{
index = rear-1;
}
return elem[index];
}
public boolean isEmpty() {
return rear == front;
}
public boolean isFull() {
//Is the next front of the rear a waste of space, so one space must be empty, and the front and rear are sandwiched in the middle, which is slow. It is recommended to refer to the third figure above for understanding
if((rear+1) %elem.length == front){
return true;
}else{
return false;
}
}
}
Use two queues to implement a stack
Use two queues to implement a stack
class MyStack {
//This problem also uses two queues. Now put the data into the queue that is not empty (if both are empty, specify one first). When the elements are out, put the elements out of the stack that are not empty into the empty stack, but only size-1. The last one makes us want to come out of the stack, so we don't put it into the second stack, but directly come out. Then, the output elements of the stack are realized. In the case of peek, it can also be put into the second stack, and then return the last put data
//Use two queues to implement the stack
private Queue<Integer> qu1;
private Queue<Integer> qu2;
public MyStack() {
qu1 = new LinkedList<>();
qu2 = new LinkedList<>();
}
public void push(int x) {
if(!qu1.isEmpty()){
qu1.offer(x);
}else if(!qu2.isEmpty()){
qu2.offer(x);
}else{
qu1.offer(x);
}
}
public int pop() {
if(empty()){
return -1;
}
if(!qu1.isEmpty()){
int size = qu1.size();
int val = -1;
for(int i = 0;i<size-1;i++){
val = qu1.poll();
qu2.offer(val);
}
return qu1.poll();
}
if(!qu2.isEmpty()){
int size = qu2.size();
int val = -1;
for(int i = 0;i<size-1;i++){
val = qu2.poll();
qu1.offer(val);
}
return qu2.poll();
}
return -1;
}
public int top() {
if(empty()){
return -1;
}
if(!qu1.isEmpty()){
int size = qu1.size();
int val = -1;
for(int i = 0;i<size;i++){
val = qu1.poll();
qu2.offer(val);
}
return val;
}
if(!qu2.isEmpty()){
int size = qu2.size();
int val = -1;
for(int i = 0;i<size;i++){
val = qu2.poll();
qu1.offer(val);
}
return val;
}
return -1;
}
public boolean empty() {
return qu1.isEmpty() && qu2.isEmpty();
}
}
Implement queue with stack
class MyQueue {
//The basic idea is to put all the data into stack 1. First judge whether stack 2 is empty. If it is empty, don't put it. In fact, at first I didn't understand why to judge whether stack 2 is empty. Later, a debugging found that if you don't have this condition, stack 2 is an element. If you continue to put it in, the element at the top of your stack is the following element, The front element hasn't been released yet, so you have to make sure that the front element is out before you can continue to put the back element
Stack<Integer> stack1 ;
Stack<Integer> stack2 ;
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if(empty()){
return -1;
}
while(!stack1.isEmpty()){
int val = stack1.pop();
stack2.push(val);
}
return stack2.pop();
}
public int peek() {
if(empty()){
return -1;
}
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
int val = stack1.pop();
stack2.push(val);
}
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}
push and pop are used for the entry and exit elements of the stack
The entry and exit elements of the queue are some of the screenshots above offer and poll
Double ended queue
deque refers to a queue that allows both ends to enter and leave the queue. deque is the abbreviation of "double ended queue".
That means that elements can be out of the team and in the team from the head of the team, or out of the team and in the team from the end of the team
public int peek() {
if(empty()){
return -1;
}
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
int val = stack1.pop();
stack2.push(val);
}
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}
------ ==The entry and exit elements of the stack are push,pop== ==The entry and exit elements of the queue are offer,poll There are screenshots above== ## Double ended queue Double ended queue( deque)It refers to a queue that allows both ends to enter and leave the queue, deque Yes“ double ended queue" Short for. That means that elements can be out of the team and in the team from the head of the team, or out of the team and in the team from the end of the team [External chain picture transfer...(img-OXYXZq08-1644978540382)]