欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

js版数据结构_03循环队列队列

程序员文章站 2022-06-06 20:45:17
...

js版数据结构_03循环队列队列

写在前面,虽然代码在编写中测试均已实现。但小白水平有限。未免有考虑不周

在本篇博文你会了解到:

  • 循环队列
  • 队列相关应用:回文检查

1. 循环队列的实现

js版数据结构_03循环队列队列
所谓循环队列,不过是普通队列的一种变种。它将普通队列的首尾进行连接使其构成逻辑上的环形结构,因为队列的大小是固定的所以可以更简单防止伪溢出的发生。

下面来看实现吧(还是老样子,私有成员变量课第一章,还是主要写思想)
实现以下功能:

  • isEmpty 判空
  • isFull 判满
  • put(e)队尾插
  • poll()队头取

这里我采用的此循环队列的判满条件为:它里面还空余一个位置。即本来最大位置是放5个我设置它放4个即为满。主要目的是防止和判空等条件

class SqQueue {
            constructor() {
                this.front = 0;
                this.rear = 0;
                this.items = {};
                this.MAX = 5; //这里我们人为规定此循环队列的长度为5
            }

            // 向队尾新加元素
            put(e) {
                // 先判满
                if (this.isFull()) {
                    return "full";
                } else {
                    this.items[this.rear] = e;
                    this.rear = (this.rear + 1) % this.MAX;//因为是个环所以不允许它有大于等于5的存在。环的指针下标在0-4.poll中同理
                }
            }
            // 从对头取出元素
            poll() {
                    // 先判空
                    if (this.isEmpty()) {
                        console.log(11);
                        return undefined;
                    } else {
                        const res = this.items[this.front];
                        delete this.items[this.front];
                        this.front = (this.front + 1) % this.MAX;
                        return res;
                    }
                }
                // 判空
            isEmpty() {
                    return this.front === this.rear;
                }
                // 判满
            isFull() {
                // 采用的是此循环队列仅空余一个为满
                return this.front == ((this.rear + 1) % this.MAX);
            }
        }

//部分测试代码:
        let q = new SqQueue();
        q.put(1);
        q.put(2);
        q.put(3);
        q.put(4);
        console.log(q.poll());
        console.log(q.poll());
        console.log(q.poll());
        q.put(2);
        q.put(3);
        q.put(4);
        console.log(q.poll());
        console.log(q.poll());
        console.log(q.poll());
        console.log(q.poll());
        q.put(4);
        console.log(q);

应用:回文检查器

什么是回文:回文是正反都能读通的单词、词组、数或一系列字符的序列,例如 madam 或 racecar。
检查回文的算法有很多,最简单的恐怕就是就是将这个回文串方向输出一下,再和原字符串做个比较即可。按理说用最简单的是栈了(这里不考虑使用倒循环),但是这里看看使用双端队列会不会比用栈简单。
实现
双端队列的类上一篇有,这里便直接用了
双端队列的类


	        class Queue {
            constructor() {
                this.count = 0; //用于记录队列内的元素个数,也是用作指向队尾的指针
                this.lowesCount = 0; //用于追踪对头元素的指针
                this.items = {}; //用于存储队列元素的数据结构,当然也可以使用数组,但是使用对象获取元素更加高效
            }

            size() {
                // 你要搞清楚有元素时这个this.count是指向的队尾的后一个,放的时候可是先放,再让它加的1
                return this.count - this.lowesCount;
            }
            addFront(e) {
                if (this.isEmpty()) {
                    this.addBack(e)
                } else {
                    // 搞清楚现在谁指着队头呢
                    this.lowesCount--;
                    this.items[this.lowesCount] = e;
                }

            }
            addBack(e) {
                this.items[this.count] = e;
                this.count++
            }
            removeFront() {
                // 先判非空
                if (this.isEmpty()) {
                    return undefined;
                } else {
                    const result = this.items[this.lowesCount];
                    delete this.items[this.lowesCount];
                    // 指针后移
                    this.lowesCount++;
                    return result;
                }
            }
            removeBack() {
                if (this.isEmpty()) {
                    return undefined;
                } else {
                    // 谁指向队尾呢,this.count指向的是队尾的下一个
                    let result = this.items[this.count - 1];
                    delete this.items[this.count - 1];
                    this.count--;
                    return result;
                }
            }
            isEmpty() {
                // 什么时候为空呢,这里希望你有写c的数据结构的基础,为空时队头队尾指针指向同一地方
                return this.count === this.lowesCount;
            }
        }
        
       

实现回文检查方法:

 function anagrams(s) {
            // 对字符串做一些预处理
            if (s === undefined || s === null || (s !== null && s.length == 0)) {
                return false;
            }
            // 字母全变小写并去除空格,trim不可去除内部的
            s = s.toLocaleLowerCase().split(" ").join("");
            let q = new Queue();
            let flag = true;
            // 搞一个双端队列的实例
            // 回文入队
            for (let i = 0; i < s.length; i++) {
                q.addBack(s.charAt(i));
            }
            // 两端出队的同时进行比较
            while (q.size() > 1 && flag) {
                let l = q.removeBack();
                let r = q.removeFront();
                if (l !== r) {
                    flag = false;
                }
            }
            // q.size==1时肯定是个回文,就一个字符不用比较了就
            return flag;
        }