JavaScript 中的非重复堆栈

Non-repeating stack in JavaScript

本文关键字：堆栈 JavaScript      更新时间：2023-09-26

我需要保留一堆 10 个项目(值原语，而不是对象(，其中没有重复的项目。这是我对实现的初步尝试。有什么改进建议吗？

var items = [];
function newItem() {
    return Math.floor(Math.random() * 50);
}
function inArray(arr, val) {
    var in_arr, i;
    in_arr = false;
    i = arr.length;
    if (i < 1) {
        return in_arr;
    }
    do {
        if (arr[i - 1] === val) {
            in_arr = true;
            break;
        }
    } while (--i);
    return in_arr;
}
function addItem() {
    var new_item;
    while (items.length > 9) {
        items.shift();
    }
    do {
        new_item = newItem();
    } while (inArray(items, new_item));
    items.push(new_item);
}

while (items.length > 9) {
    items.shift();
}

可以在没有迭代的情况下编写为

var len = items.length;
if (len > 9) {
    items = items.slice(len - 9);
}

从 JS 1.6 开始，inArray可以写成 array.indexOf(element) != -1 。否则

if (i < 1) {
    return in_arr;
}
do {
    if (arr[i - 1] === val) {
        in_arr = true;
        break;
    }
} while (--i);
return in_arr;

可以更简单地写成

while (i--) {
    if (arr[i] === val) {
        return true;
    }
}
return false;

function inArray(arr, val) {
    return !!~arr.indexOf(val);
}

如果需要，可以使用此垫片

function addItem(item) {
    if (inArray(items, item)) return false;
    if (items.length > 9) items = items.slice(len - 9);
    items.push(item);
    return true;
}

我会像这样重写保留的东西：

function stack10() {
    var items = arguments || [];
    this.addItem = function (item) {
        var len = items.length;
        if (!!~items.indexOf(item)) return;
        if (len > 9) items = items.slice(len - 9);
        items.push(item);
    } 
    this.peek = function() {
        if (items.length === 0) return null;
        return items[items.length-1];
    }
    this.pop = function () {
        return items.pop();
    }
}
var myStack = new stack10();
myStack.addItem(10);
myStack.peek(); // 10
myStack.pop(); // 10
myStack.pop(); // undefined
// default values
var myStack2 = new stack10(1,2,3,4);
myStack2.addItem(10);
myStack2.peek(); // 10
myStack2.pop(); // 10
myStack2.pop(); // 4

为什么不使用堆？您可以执行 O(lg n( 插入和删除而不是 O(n(，并且它仍在原位。

相关文章：