EXERCISE · AlgoCasts
Queue from stacks
Implement a Queue datastructure using two stacks. *Do not* create an array inside of the 'Queue' class. Queue should implement the methods 'add', 'remove', and 'peek'.
Directions
Implement a Queue datastructure using two stacks. *Do not* create an array inside of the 'Queue' class. Queue should implement the methods 'add', 'remove', and 'peek'. For a reminder on what each method does, look back at the Queue exercise.
Examples#
const q = new Queue(); q.add(1); q.add(2); q.peek(); // returns 1 q.remove(); // returns 1 q.remove(); // returns 2Try it first#
Copy the stub, make the 5 tests pass on your machine, then open the solution. The reveal is remembered per page in this browser.
const Stack = require('./stack'); class Queue {} module.exports = Queue;Solution#
const Stack = require('./stack'); class Queue { constructor() { this.first = new Stack(); this.second = new Stack(); } add(record) { this.first.push(record); } remove() { while (this.first.peek()) { this.second.push(this.first.pop()); } const record = this.second.pop(); while (this.second.peek()) { this.first.push(this.second.pop()); } return record; } peek() { while (this.first.peek()) { this.second.push(this.first.pop()); } const record = this.second.peek(); while (this.second.peek()) { this.first.push(this.second.pop()); } return record; }} module.exports = Queue;const Queue = require('./index'); test('Queue is a class', () => { expect(typeof Queue.prototype.constructor).toEqual('function');}); test('can add elements to a queue', () => { const q = new Queue(); expect(() => { q.add(1); }).not.toThrow();}); test('can remove elements from a queue', () => { const q = new Queue(); expect(() => { q.add(1); q.remove(); }).not.toThrow();}); test('Order of elements is maintained', () => { const q = new Queue(); q.add(1); q.add(2); q.add(3); expect(q.remove()).toEqual(1); expect(q.remove()).toEqual(2); expect(q.remove()).toEqual(3); expect(q.remove()).toEqual(undefined);}); test('peek returns, but does not remove, the first value', () => { const q = new Queue(); q.add(1); q.add(2); expect(q.peek()).toEqual(1); expect(q.peek()).toEqual(1); expect(q.remove()).toEqual(1); expect(q.remove()).toEqual(2);}); class Stack { constructor() { this.data = []; } push(record) { this.data.push(record); } pop() { return this.data.pop(); } peek() { return this.data[this.data.length - 1]; }} module.exports = Stack; Verbatim from the repo at 30cf7634. Alternate tabs are the commented-out solutions with the leading // removed and nothing else changed. Run the tests locally with npx jest qfroms inside the fork.
See also