preface

I give you two stacks how do you implement a queue, and I give you two queues how do you implement a stack.

In this article, I will share with you the solutions and implementation process of these two problems, and welcome interested developers to read this article.

Problem analysis

Let’s take a look at the stack and queue features:

  • Stack: The element added first is last out
  • Queue: The first element added is the first to exit

For a more detailed explanation of stacks and queues, please refer to my other article: Data Structures: Stacks and queues

Now that we have the theoretical basis of stacks and queues, we can use their properties to analyze the problem. Let’s first look at how stacks can be used to implement queues:

  • We only know two stacks, and identify them: stack 1 and stack 2
  • When we queue, we put the element on stack 1.
  • When performing the queue operation:
    • Push the elements of stack 1 onto stack 2
    • The top element of stack 2 goes off the stack

In the above idea, we use stack 1 to store the elements, and we know that the rule of the stack is first in, last out, so we push the elements of stack 1 onto stack 2, and then push the elements of stack 2 off the stack, which conforms to the characteristics of the queue.

Next, let’s see how stacks are implemented using queues:

  • Similarly, we know that we have two queues and identify them: queue 1, queue 2
  • When a push operation is performed, the element is put into queue 1
  • When a stack operation is performed:
    • If queue 2 is empty, we put the element from queue 1 into queue 2 except for the first element
    • If queue 2 is not empty, we put the elements of queue 2 into queue 1
    • The element in queue 1 is queued

In this way, we put all the elements in queue 1, and when we unstack, we keep only the first element in queue 1, put all the other elements in queue 2, then put the elements in queue 2 back in queue 1, and finally unqueue the elements in queue 1. After our flip, we just fit the characteristics of the stack.

The implementation code

Through the above analysis, we have implementation approach, then we will be the above ideas into specific code, the following code will be introduced before we write good queue and stack in the implementation of the code, developers please click I don’t know the other two articles: array implementation and object implementation stack, queue, and the realization of the deque

Stack implementation queue

  • Create the StacksAndQueues class file to declare the variables needed to solve the problems in this article
// Stack and queue related operations
import Stack from ".. /.. /StackTest/lib/Stack.ts";
import Queue from ".. /.. /QueueTest/lib/Queue.ts";

export default class StacksAndQueues {
    private firstStacks: Stack;
    private secondStacks: Stack;
    private firstQueues: Queue;
    private secondQueues: Queue;

    constructor() {
        this.firstStacks = new Stack();
        this.secondStacks = new Stack();
        this.firstQueues = new Queue();
        this.secondQueues = newQueue(); }}Copy the code
  • Implement the queue function
    / / team
    enqueue(key: string | number) :void {
        / / 1 stack
        this.firstStacks.push(key);
    }
Copy the code
  • Implement the queue function
    / / out of the team
    dequeue() {
        if (this.secondStacks.isEmpty()) {
            while (!this.firstStacks.isEmpty()) {
                this.secondStacks.push(this.firstStacks.pop()); }}if (!this.secondStacks.isEmpty()) {
            / / two stacks
            return this.secondStacks.pop();
        }
        return null;
    }
Copy the code

Let’s use an example to verify that the above code works:

import StacksAndQueues from "./lib/StacksAndQueues.ts";

// Implement queue with stack
const stacksAndQueues = new StacksAndQueues();
stacksAndQueues.enqueue(3);
stacksAndQueues.enqueue(9);
stacksAndQueues.enqueue(12);
console.log("A team", stacksAndQueues.dequeue());
console.log("A team", stacksAndQueues.dequeue());
console.log("A team", stacksAndQueues.dequeue());
Copy the code

Queue implementation stack

  • Implement the push function
    / / into the stack
    stackPush(key: string | number) {
        / / team 1
        this.firstQueues.enqueue(key);
    }
Copy the code
  • Implement the stack function
    / / out of the stack
    stackPop() {
        if (this.firstQueues.isEmpty()) {
            return null;
        }
        // Queue 2 is empty
        if (this.secondQueues.isEmpty()) {
            while (this.firstQueues.size() ! =1) {
                // Put the elements of queue 1 into queue 2 except for the elements at the end
                this.secondQueues.enqueue(this.firstQueues.dequeue()); }}// Queue 2 is not empty
        while (!this.secondQueues.isEmpty()) {
            // Put the elements of queue 2 into queue 1
            this.firstQueues.enqueue(this.secondQueues.dequeue());
        }
        // Queue 1 exits queue 1
        return this.firstQueues.dequeue();
    }
Copy the code

Let’s use an example to verify that the above code works:

// Queue implementation stack
stacksAndQueues.stackPush(3);
stacksAndQueues.stackPush(9);
stacksAndQueues.stackPush(12);
console.log("The stack", stacksAndQueues.stackPop());
console.log("The stack", stacksAndQueues.stackPop());
console.log("The stack", stacksAndQueues.stackPop());
Copy the code

The code address

The complete address of the implementation code is as follows:

  • StacksAndQueues.ts

Write in the last

  • If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
  • This article was first published in nuggets. Reprint is prohibited without permission 💌