链表实现队列

栈结构

定义

• 允许插入和删除的一端称为栈顶，另一端称为栈底
• 不含任何数据元素的栈称为空栈
• 后进先出的数据结构

代码实现

   class Stack{
       constructor() {
           this.stack = []
       }
       put(element){         //进栈
           this.stack.push(element)
       }
       pop() {             //出栈
           this.stack.pop()
       }
   }
   
   //调用
   let stack = new Stack()
   stack.put(1)
   stack.put(2)
   stack.pop()
   console.log(stack.stack)

单向链表

定义

• 链表中的元素不是连续放置的
• 每个元素由一个存储元素本身的节点和指向下一个元素的引用组成
• 添加或移动元素的时候不需要移动其它元素

用列表实现队列

/**
 * @description 用链表实现队列
 * @author 
 */

interface IListNode {
    value: number
    next: IListNode | null
}

export class MyQueue {
    private head: IListNode | null = null
    private tail: IListNode | null = null
    private len = 0

    /**
     * 入队，在 tail 位置
     * @param n number
     */
    add(n: number) {
        const newNode: IListNode = {
            value: n,
            next: null,
        }

        // 处理 head
        if (this.head == null) {
            this.head = newNode
        }

        // 处理 tail
        const tailNode = this.tail
        if (tailNode) {
            tailNode.next = newNode
        }
        this.tail = newNode

        // 记录长度
        this.len++
    }

    /**
     * 出队，在 head 位置
     */
    delete(): number | null {
        const headNode = this.head
        if (headNode == null) return null
        if (this.len <= 0) return null

        // 取值
        const value = headNode.value

        // 处理 head
        this.head = headNode.next

        // 记录长度
        this.len--

        return value
    }

    get length(): number {
        // length 要单独存储，不能遍历链表来获取（否则时间复杂度太高 O(n)）
        return this.len
    }
}

// // 功能测试
// const q = new MyQueue()
// q.add(100)
// q.add(200)
// q.add(300)
// console.info('length1', q.length)
// console.log(q.delete())
// console.info('length2', q.length)
// console.log(q.delete())
// console.info('length3', q.length)
// console.log(q.delete())
// console.info('length4', q.length)
// console.log(q.delete())
// console.info('length5', q.length)

// // 性能测试
// const q1 = new MyQueue()
// console.time('queue with list')
// for (let i = 0; i < 10 * 10000; i++) {
//     q1.add(i)
// }
// for (let i = 0; i < 10 * 10000; i++) {
//     q1.delete()
// }
// console.timeEnd('queue with list') // 17ms

// const q2 = []
// console.time('queue with array')
// for (let i = 0; i < 10 * 10000; i++) {
//     q2.push(i) // 入队
// }
// for (let i = 0; i < 10 * 10000; i++) {
//     q2.shift() // 出队
// }
// console.timeEnd('queue with array') // 431ms

单元测试

import { MyQueue } from './queue-with-list'

describe('链表实现队列', () => {
    it('add and length', () => {
        const q = new MyQueue()
        expect(q.length).toBe(0)

        q.add(100)
        q.add(200)
        q.add(300)
        expect(q.length).toBe(3)
    })
    it('delete', () => {
        const q = new MyQueue()
        expect(q.delete()).toBeNull()

        q.add(100)
        q.add(200)
        q.add(300)
        expect(q.delete()).toBe(100)
        expect(q.delete()).toBe(200)
        expect(q.delete()).toBe(300)
        expect(q.delete()).toBeNull()
    })
})

实际开发中

在实际开发中，如果我们队数据结构的要求不是特别高，一般会采用一个无限制的数组模拟队列，使用数组的push方法和shift方法来实现出栈和入栈，通过判断数组的长度来判断其是否为空。比较简便。

export class Queue {
    constructor() {
        this._arr = [];
    }

    toString(){
        return this._arr.toString();
    }

    // 入队
    push(data){
        return this._arr.push(data);
    }

    // 出队
    pop(){
        return this._arr.shift();
    }

    // 获取队头
    head(){
        return this._arr.length ? this._arr[0] : null;
    }

    // 获取队尾
    rear(){
        return this._arr.length ? this._arr[this._arr.length-1] : null;
    }

    // 判断是否为空
    isEmpty(){
        return !!this._arr.length;
    }
}