Home >Web Front-end >JS Tutorial >JavaScript uses recursive method to reverse stack elements

JavaScript uses recursive method to reverse stack elements

零到壹度
零到壹度Original
2018-04-02 09:39:241811browse

Let’s look at an interview question first. The question is as follows: There is a stack, and the elements 1, 2, 3, 4, 5 are pushed into it at once, and the result is [1, 2, 3, 4 ,5], now we can only use recursive method to reverse the elements in the stack, and the result is [5,4,3,2,1]. If there is no question requirement, this would be relatively simple. You can solve the problem directly with arr.reverse(), but it is interesting to only use recursion. As a novice, I have to study it carefully.

##Hands-on analysis

We regard the stack [1, 2, 3, 4, 5] as consisting of two Partially composed: the top element 1 of the stack and the remaining parts [2, 3, 4, 5].

If we can reverse [2, 3, 4, 5] and turn it into [5, 4, 3, 2], and then put the original top element 1 on the stack at the bottom, then the entire The stack is turned upside down and becomes [5, 4, 3, 2, 1].

Next we need to consider two things: First, how to reverse [2, 3, 4, 5] into [5, 4, 3, 2]. We just think of [2, 3, 4, 5] as consisting of two parts: the top element 2 and the remaining part [3, 4, 5].

We only need to reverse [3, 4, 5] first to become [5, 4, 3], and then put the previous top element 2 at the bottom of the stack, which becomes [5 , 4, 3, 2].

As for how to reverse [3, 4, 5]... Many readers may think that this is recursion. That is, every time you try to invert a stack, the top element of the current stack pops out, then inverts the stack composed of remaining elements, and finally puts the previous top element at the bottom of the stack composed of remaining elements. The condition for the end of recursion is that the remaining stack is empty

show a wave of code

//这个函数的作用是把栈中的元素展开
function reverseStack(arr){ 
  if(
  arr.length != 0
    )
  {
   var topItem = arr.pop() 
   reverseStack(arr) pushStack(arr, topItem) 
   } 
   return arr}//这个函数的作用是把函数进行颠倒
   function pushStack(arr, item){   else{    console.log(arr)
    if(arr.length == 0){
     arr.push(item)
   }

Related recommendations:

Inversion Elements in the stack - inversion of the stack

Invert the stack

Implementation of stack transposition

The above is the detailed content of JavaScript uses recursive method to reverse stack elements. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn