Структуры данных: Стэк и очередь (stack and queue)

12

Stack

function Stack() {
    this.stack = [];
}

Stack.prototype.push = function(value) {
    this.stack.push(value);
};

Stack.prototype.pop = function() {
    return this.stack.pop();
};

Stack.prototype.peek = function() {
    return this.stack[this.stack.length - 1];
};

let stack = new Stack();

stack.push(1);
stack.push(2);
stack.peek();
stack.pop();

Stack variant 2

function Stack(capacity) {
    this._capacity = capacity || Infinity;
    this._storage = {};
    this._count = 0;
}

Stack.prototype.push = function(value) {
    if(this._count < this._capacity) {
        this._storage[this._count++] = value;
        return this._count;
    }
    return `Максимальный размер уже достигнут. 
    Удалите элемент прежде чем добавлять новый`;
};

Stack.prototype.pop = function() {
    var value = this._storage[--this._count];
    delete this._storage[this.count];
    if(this._count < 0) {this._count = 0}
    return value;
};

Stack.prototype.peek = function() {
    return this._storage[this._count-1];
}

Stack.prototype.count = function() {
    return this._count;
}

//Test
var myStack = new Stack(3);
console.log(myStack.push('a'), 'should be 1');
console.log(myStack.push('b'), 'should be 2');
console.log(myStack.push('c'), 'should be 3');
console.log(myStack.push('d'), 'Max capacity error');
console.log(myStack.pop(), 'should be c');
console.log(myStack.count(), 'should be 2');
console.log(myStack.peek(), 'should be b');
console.log(myStack.count(), 'should be 2');

Min stack

function MinStack(capacity) {
    this._capacity = capacity;
    this._storage = {};
    this._count = 0;
    this._min = new Stack();
}

MinStack.prototype.push = function () {
    if(this._count < this._capacity) {
        if(this._min.peek() < value) {
            this._min.push(this._min.peek());
        } else {
            this._min.push(value);
        }
        this._storage[this._count++] = value;
        return this._count;
    }
    return 'Максимальный размер достигнут';
};

MinStack.prototype.pop = function () {
    this._min.pop();
    var value = this._storage[--this._count];
    delete this._storage[this._count];
    if(this._count < 0) {
        this._count = 0;
    }
    return value;
};

MinStack.prototype.peek = function() {
    return this._storage[this._count-1];
};

MinStack.prototype.count = function() {
    return this._count;
};

MinStack.prototype.min = function() {
    return this._min.peek();
}

Stack из строки

/*
Interface: Stack
1.Constructor Function
    - Storage
2.Methods
    -push(value) - adds value to the front, returns size of stack
    -pop() - remove value from front, returns value
    -size() - returns size of stack as an integer
*/

//Constructor stack from string
var Stack = function() {
    this.storage = '';
}

Stack.prototype.push = function(val){
    // this.storage += `, ${val}`;
    this.storage = this.storage.concat('***', val);
};
Stack.prototype.pop = function(){
    let str = this.storage.slice(this.storage.lastIndexOf('***') + 3);
    this.storage = this.storage.substring(0, this.storage.lastIndexOf('***'));
    return str;
};
Stack.prototype.size = function(){
    return this.storage.length;
};

var myWeeklyMenu = new Stack();
myWeeklyMenu.push('RedBeans');

Queue

function Queue() {
    this.queue = [];
}

Queue.prototype.enqueue = function(value) {
    this.queue.push(value);
};

Queue.prototype.dequeue = function () {
    return this.queue.shift();
};

Queue.prototype.peek = function() {
    return this.queue[0];
};


let queue = new Queue();


queue.enqueue(1);
queue.enqueue(2);
queue.peek();
queue.dequeue();

Queue with two stacks

function Queue(capacity) {
    this._capacity = capacity || Infinity;
    this._storage = {};
    this._head = 0;
    this._tail = 0;
}

Queue.prototype.enqueue = function(value) {
    if(this.count() < this._capacity) {
        this._storage[this._tail++] = value;
        return this.count();
    }
    return 'Максимальная очередь достигнута';
}

Queue.prototype.dequeue = function () {
    var element = this._storage[this._head];
    delete this._storage[this._head];
    if(this._head < this._tail) this._head++;
    return element;
}

Queue.prototype.peek = function() {
    return this._storage[this._head];
}
//O(1)
Queue.prototype.count = function() {
    return this._tail - this._head;
}
//O(n)
Queue.prototype.contains = function(value) {
    for (let i = this._head; i < this._tail; i++) {
        if(this._storage[i] === value) return i - this._head + 1;
    }
    return null;
}
//O(n)
Queue.prototype.until = function(value) {
for (let i = this._head; i < this._tail; i++) {
    if(this._storage[i] === value) return i - this._head + 1
}
return null;
}

//TEST
var myQueue = new Queue(3);
console.log(myQueue.enqueue('a'), 'should be 1');
console.log(myQueue.enqueue('b'), 'should be 2');
console.log(myQueue.enqueue('c'), 'should be 3');
console.log(myQueue.enqueue('d'), 'Max count error');
console.log(myQueue.dequeue(), 'should be a');
console.log(myQueue.count(), 'should be 2');
console.log(myQueue.peek(), 'Should be b');
console.log(myQueue.count(), 'should be 2');
console.log(myQueue.contains('b'), 'should be true');
console.log(myQueue.contains('d'), 'should be false');
console.log(myQueue._storage, myQueue._head);
console.log(myQueue.until('b'), 'should be 1');
console.log(myQueue.until('c'), 'should be 2');
console.log(myQueue.until('d'), 'should be null');

You might also like More from author

Leave A Reply

Your email address will not be published.