As front end , Access to algorithms may be less , But we can't rust our brains ~

A subject : Enter two Integer Sequences , The first sequence represents the push order of the stack , Determine whether the second sequence is the pop-up sequence of the stack . Assume that all the numbers of the push stack are not equal .
for example :1,2,3,4,5 Is the push order of a stack , sequence 4,5,3,2,1 Is a pop-up sequence corresponding to the stack , but 4,3,5,1,2 It can't be the pop-up sequence of the stack pressing sequence .

here , I use JS To realize this problem , Array is used to simulate stack operation . The main idea is :

* When judging the first pop-up number , If it happens to be the top element of the stack , Then pop it up directly . Continue from 1 Step to determine the next pop-up number .
* If not , The number in the stack sequence that is not a pop-up number is pushed into the auxiliary stack until the pop-up element is found ( If not , You can exit directly , Description pop-up sequence not possible ).
* If the pop-up sequence exists , Then there are only two possibilities for the next pop-up element :① Appears at the top of the stack ;② Exists in auxiliary stack . Then loop through the two situations until the pop-up stack becomes empty .
* If neither of the above matches , Then the pop-up sequence is not possible .
The code is as follows , There are detailed notes :
/** * Use here JS realization , Using array to simulate stack operation * @param { Order of stack input ( Array representation )} pushOrder * @param
{ Sequence of stack output ( Array representation )} popOrder */ function isPopPossible(pushOrder, popOrder) { var
isPossible= false /** 1. Confirm the validity of the input */ if (pushOrder != null && popOrder != null
&& Array.isArray(pushOrder) && Array.isArray(popOrder)) { /** 2.
Return directly when both are empty true( If both stacks are empty , namely true) */ if (pushOrder.length === 0 && popOrder.
length=== 0) { return true } /** 3. Ensure that the sequence length of two inputs is equal */ if (pushOrder.length ===
popOrder.length) { /** JS Array passed in reference in , To ensure that the original array is not changed , Create a copy of them here */ var pushOrder_copy
= [...pushOrder] var popOrder_copy = [...popOrder] /** This array serves as an auxiliary stack */ var
helpStack= [] /** Get the first pop-up element ( The pop-up sequence is now reduced by one element ) */ var now = popOrder_copy.shift()
/** Push the element whose top is not the first pop-up element into the auxiliary stack */ while (pushOrder_copy.length > 0 && pushOrder_copy[
pushOrder_copy.length - 1] !== now) { helpStack.unshift(pushOrder_copy.pop()) }
/** If all the elements are ejected, the element equivalent to the first one has not been found , Then return directly false */ if (pushOrder_copy.length === 0) {
return false } /** Description found , Then pop up the matching element */ pushOrder_copy.pop() /** 4.
Traverse the remaining pop-up stack elements ( The stack sequence may not be empty here , Auxiliary stack may not be empty , Pop up stack may not be empty ) */ while (popOrder_copy.length > 0) {
/** Get next pop-up element */ now = popOrder_copy.shift() /** If the top of the stack of the push sequence is the pop-up element , Then pop it out of the stack */ if
(pushOrder_copy.length > 0 && pushOrder_copy[pushOrder_copy.length - 1] === now)
{ pushOrder_copy.pop() } else { /** Traversal auxiliary stack , See if the pop-up element is in the auxiliary stack */ while (helpStack.
length> 0) { /** If the element at the top of the auxiliary stack is not a pop-up element , Push it into the stack */ if (helpStack[0] !== now) {
pushOrder_copy.push(helpStack.shift()) } else { /**
The pop-up element was found in the auxiliary stack , The element will be ejected , Jump out of the loop , Judge the next round of pop-up elements */ helpStack.shift() break } } } } /**
Finally, both in stack and out stack are empty , The description matches , Is a possible pop-up sequence */ if(popOrder_copy.length === 0 && pushOrder_copy.
length=== 0) { isPossible = true } } } return isPossible } /** ===== test case ===== */
/** 1. Both are empty */ console.log(isPopPossible([], [])) //true, /** 2. One of them doesn't exist */
console.log(isPopPossible(null, [])) //false /** 3. Number of elements does not match */ console.log(
isPopPossible([1, 2, 3, 4], [1, 2, 3])) //false /** 4. Element mismatch */ console.log(
isPopPossible([1, 2, 3, 4], [1, 2, 3, 5])) //false, /** 5. More routine tests */ console.log
(isPopPossible([1, 2, 3, 4, 5], [4, 5, 3, 2, 1])) //true /** 5. Mismatch */ console.
log(isPopPossible([1, 2, 3, 4, 5], [4, 5, 3, 1, 2])) //false /**
6. The sequence in the stack is empty , All in the auxiliary stack */ console.log(isPopPossible([1, 2, 3, 4, 5], [5, 4, 3, 2, 1]))
//true, /** 7. Input stack and auxiliary stack alternate back and forth */ console.log(isPopPossible([1, 3, 2, 0], [1, 2, 0,
3])) //true

Technology
©2019-2020 Toolsou All rights reserved,
Bitcoin in ten years ,VDS Opportunity or fraud Don't annoy the panda with any cat !「 Kung Fu Panda 」20 It's the year of man 4 blood sort ( one ) bubble sort Random forest R Language implementation java Realize the function of grabbing red packets Python Basic knowledge and notes python To solve the problem of dictionary writing list in CSS architecture design Vue Common features ( one )2021 year 2 Monthly programmer salary statistics , average 15144 element