队列

队列,先进先出,入队enqueue(),出队dequeue()
栈, 后进先出,入栈push(), 出栈()

队列和栈一样,都是一种操作受限的线性表结构

顺序队列:用数组实现的队列
链式队列:用链表实现的队列

队列的实现需要两个指针,head标记队列头,tail标记队尾
栈只需要栈顶指针

队列的代码实现

// 基于数组的队列实现
class ArrayQueue {
    items:string[]
    n:number = 0
    head:number = 0
    tail:number = 0
    constructor(n) {
        if(!(/(^[1-9]\d*$)/).test(n)) {
            throw("ArrayQueue需要接收一个正整数作为初始栈大小")
            return
        }
        this.n = n
        this.tail = n
        this.items.length = n
    }

    // 入队
    enqueue(item:string):boolean {
        // tail === n 代表队列已满
        if (this.tail === this.n) return false
        this.items[tail] = item
        ++this.tail
        return true
    }

    // 出队
    dequeue():string {
        // head === tail 代表队列为空
        if(this.head === this.tail) return null
        const ret = this.items[head]
        ++this.head
        return ret
    }
}
// 随着不停的出栈入栈,head tail会不停后移,
// tail达到末尾时,可能还有空间空间在前面,进行数据搬移(假设JS数组长度不会自动伸长)

enqueue(item:string):boolean {
    // tail === n 表示队尾没空间了
    if(this.tail === this.n) {
        // 如果此时head还在0,代表队首也没空间了
        if(this.head === 0) return false
        // 数据搬移到最前面
        for(let i = this.head; i < this.tail; i++) {
            this.items[i-head] = this.items[i]
        }
        // 更新head 和 tail
        this.tail = this.tail - this.head
        this.head = 0
    }
    this.items[this.tail] = item
    ++this.tail
    return true
}

// 基于链表的队列实现,Author: nameczz
class Node {
    constructor(element) {
        this.element = element
        this.next = null
    }
}

class QueueBasedOnLinkedList {
    constructor() {
        this.head = null
        this.tail = null
    }

    enqueue(value) {
        if (this.head === null) {
            this.head = new Node(value)
            this.tail = this.head
        } else {
            this.tail.next = new Node(value)
            this.tail = this.tail.next
        }
    }

    dequeue() {
        if (this.head !== null) {
            const value = this.head.element
            this.head = this.head.next
            return value
        } else {
            return -1
        }
    }
}
// Test
const newQueue = new QueueBasedOnLinkedList()
// 插入元素
newQueue.enqueue(1)
newQueue.enqueue(2)
newQueue.enqueue(3)
// 获取元素
let res = 0
console.log('-------获取dequeue元素------')
while (res !== -1) {
    res = newQueue.dequeue()
    console.log(res)
}