Non-repeating stack in JavaScript

Question

I need to keep a stack of 10 items (value primitives, not objects) where no item is repeated. Here's my initial stab at an implementation. Any suggestions for improvements?

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);
}

I don't like the use of new_item and newItem in the same method to mean quite different things. — Douglas
– Douglas, Commented Dec 29, 2011 at 19:21
Have you used indexOf before? I think it could replace your inArray method. — Douglas
– Douglas, Commented Dec 29, 2011 at 19:23
@Douglas: Not all browsers support it. By that I mean it doesn't work on IE < 9. — gen_Eric
– gen_Eric, Commented Dec 29, 2011 at 19:26
Good point - though then it is a trade off between using the implementation on that page, or your own one. — Douglas
– Douglas, Commented Dec 29, 2011 at 20:13

Amadan · Accepted Answer · 2011-12-29 19:28:56Z

5

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

can be written without iteration as

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

Since JS 1.6, inArray can be written as array.indexOf(element) != -1. Otherwise,

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

can be written more simply as

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

edited Dec 29, 2011 at 19:28

answered Dec 29, 2011 at 19:23

Amadan

200k23 gold badges253 silver badges321 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Deleteman Over a year ago

Using indexOf for arrays won't work for older versions of IE (as you put it, because of the JS version), but can easily be added by prototyping it into the Array object.

gen_Eric Over a year ago

@Deleteman: As seen here: developer.mozilla.org/en/JavaScript/Reference/Global_Objects/…

Joe · Accepted Answer · 2011-12-29 19:38:12Z

3

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

with this shim if needed

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

I would rewrite the hold thing like this:

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

edited Dec 29, 2011 at 19:38

answered Dec 29, 2011 at 19:24

Joe

82.9k18 gold badges130 silver badges147 bronze badges

4 Comments

Andrew Hedges Over a year ago

slice returns a copy of the array, so you have to assign it back to items, otherwise, this looks good.

Amadan Over a year ago

Haha, never seen !!~ for != -1 yet! Not as efficient, but damn compact... jsperf.com/bangbangwave

Amadan Over a year ago

What @AndrewHedges said; also, you never defined len in addItem.

Joe Over a year ago

@Amadan, thanks. I updated. I think your solution is more complete/friendly anyways.

jzila · Accepted Answer · 2011-12-29 19:28:03Z

-1

Why not use a heap? You can do O(lg n) insert and removal instead of O(n), and it's still in-place.

answered Dec 29, 2011 at 19:28

jzila

7354 silver badges12 bronze badges

6 Comments

cHao Over a year ago

Because a heap is not a stack? Because stuff needs to retain its order? Because O(log N) and O(N) don't matter so much when N <= 10?

jzila Over a year ago

@cHao: He was asking for suggested improvements. You can modify a heap such that you can maintain stack ordering. I suggested the use of a heap since search and insertion are sub-linear, unlike the provided solution. You're right that big-O doesn't matter when N is small, but yet again: this is about suggested improvements, not necessarily giving "The Right Answer". Additionally, if someone has this same question and searches for it, but with large N, using a heap is a legitimate way of getting around the linear constraints of the provided solution.

cHao Over a year ago

You can't modify a heap such that it retains properties of a stack, and still call it a heap. The two data structures are fundamentally different; stacks are by definition LIFO, and heaps are by definition...not. It'd be like using a hash table as a stack. Sure, you could shoehorn a stack into it (and insertion and removal would even be O(1)!), but in the process you'd be taking away everything that makes it a hash table.

Andrew Hedges Over a year ago

For my use case, order is important.

cHao Over a year ago

Plus, the constraints of the problem make O(log N) all but impossible anyway -- attempting to add X would require searching the collection for X, making adding an element O(N) at best. You can compare items by insertion order or by value, but doing both would require two heaps.

|

Collectives™ on Stack Overflow

Non-repeating stack in JavaScript

3 Answers 3

2 Comments

4 Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

4 Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related