Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

Hello everyone, I am quick-frozen fish 🐟, a water front 💦, like the garish 💐, continuous sand sculpture 🌲 Welcome friends to add my wechat: Sudongyuer pull you into the group of my public number: front-end quick-frozen fish progress together, looking forward to growing together with everyone

Preface 🌧 ️

Algorithms are unfamiliar and familiar to the front-end people, and often we don’t value them as much as the back-end engineers do. But in fact, algorithms have an unshakable position for every programmer.

Because the development process is to convert the actual problem into the computer can recognize the instructions, that is, “data structure” said, “design the data structure, in the application of algorithms on the line”.

The quality of writing instructions will directly affect the performance of the program, and instructions are composed of data structure and algorithm, so the design of data structure and algorithm basically determines the quality of the final program.

The title 🦀

232. Implement queues with stacks

Difficulty is simple

You can implement a first-in, first-out queue using only two stacks. Queues should support all the operations that queues normally support (push, POP, peek, empty) :

Implement MyQueue class:

  • void push(int x)Push element X to the end of the queue
  • int pop()Removes and returns elements from the beginning of the queue
  • int peek()Returns the element at the beginning of the queue
  • boolean empty()If the queue is empty, returntrue; Otherwise, returnfalse

Description:

  • You can only use standard stack operations — that is, only push to Top, peek/ Pop from Top, size, and is empty are legal.

  • Your language may not support stacks. You can use a list or a deque to simulate a stack, as long as it’s standard stack operations.

Example 1:

Input: [" MyQueue ", "push" and "push" and "peek", "pop", "empty"] [[], [1], [2], [], [], []] output: [null, null, null, 1, 1, false] MyQueue MyQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return falseCopy the code

Tip:

  • 1 <= x <= 9

  • Push, POP, peek, and Empty are called up to 100 times

  • Assume that all operations are valid (for example, an empty queue does not call pop or PEEK)

Advanced:

  • Can you achieve amortized time for each operationO(1)The queue? In other words, executenThe total time complexity of the operation isO(n), even though one of the operations may take a long time.

🌵

  • This is a simulation problem, does not involve the specific algorithm, is to test the stack and queue grasp degree.
  • Using a stack to model the behavior of a queue, if you use only one stack, it will not work
  • So you need two stacks an input stack and an output stack, and you have to pay attention to the relationship between the input stack and the output stack.

Refer to the diagram in the code catalog

How to solve the problem 🐂

  • The queue feature is FIFOFIFO (first in, first out), while the stack feature is FILOFILO (first in, first out).

  • Knowing both, we need to simulate the characteristics of queues with two stacks, one for queue entry and one for outbound counterstack.

  • When unqueuing exists, the top of the unqueuing stack is the first element to unqueue.

  • If there are no elements in the queue stack, and our requirements are unqueued, we need to import the contents of the queue stack in reverse order, and then pop the top of the stack.

Solution 🔥

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}* /
var mergeTwoLists = function(l1, l2) {
    const res=new ListNode(0);
    let p=res;
    let p1=l1;
    let p2=l2;

    while(p1 && p2){
        if(p1.val<p2.val){
          p.next=p1;
          p1=p1.next;
        }else{
            p.next=p2;
            p2=p2.next
        }
        p=p.next
    }
    if(p1){
        p.next=p1
    }
    if(p2){
        p.next=p2
    }
    return res.next

};
         
Copy the code

Conclusion 🌞

So the “LeetCode” 232- using stack to implement queue ⚡️ is over, there is no shortcut to algorithm, can only write more practice, more summary, the purpose of the article is actually very simple, is to urge myself to complete algorithm practice and summary and output, food is not important, but love 🔥, I hope everyone can like my essay, and I also hope to know more like-minded friends through the article. If you also like to toss, welcome to add my friend, sand sculpture together, together progress.

Making 🤖 : sudongyu

Personal blog 👨💻: Frozen fish blog

Vx 👦 : sudongyuer

Write in the last

Guys, if you like my words, give 🐟🐟 a thumbs up 👍 or follow ➕ to support me the most.