/
ctci-queue-using-two-stacks.js
115 lines (98 loc) · 2.44 KB
/
ctci-queue-using-two-stacks.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// https://www.hackerrank.com/challenges/ctci-queue-using-two-stacks/problem
// In this challenge, you must first implement a queue using two stacks. Then process queries, where each query is one of the following types:
//
// 1 x: Enqueue element into the end of the queue.
// 2: Dequeue the element at the front of the queue.
// 3: Print the element at the front of the queue.
//
// The first line contains a single integer, , the number of queries.
// Each of the next q lines contains a single query in the form described in the problem statement above.
// All queries start with an integer denoting the query type,
// but only query 1 is followed by an additional space-separated value, x, denoting the value to be enqueued.
//
// Given string input =
// 10
// 1 42
// 2
// 1 14
// 3
// 1 28
// 3
// 1 60
// 1 78
// 2
// 2
//
// Output:
// 14
// 14
class Stack {
constructor(stack = []) {
this._stack = stack;
}
push(data) {
this._stack.push(data);
}
pop() {
return this._stack.pop();
}
peek() {
return this._stack[this._stack.length - 1];
}
}
class Queue {
constructor() {
this.tail = null;
this.active = new Stack();
this.placeholder = new Stack();
}
enqueue(data) {
this.active.push(data);
if (!this.tail) this.tail = data;
}
dequeue() {
// if anything in dequeue stack, return pop
if (this.placeholder.peek() !== undefined) {
const data = this.placeholder.pop();
// if dequeue stack is now empty, populate
this._maybePopulate();
this.tail = this.placeholder.peek();
return data;
}
// otherwise, populate dequeue stack, and pop the top.
this._maybePopulate();
const data = this.placeholder.pop();
const tail = this.placeholder.peek();
this.tail = tail;
return data;
}
peek() {
return this.tail;
}
_maybePopulate() {
if (this.placeholder.peek() === undefined) {
while (this.active.peek() !== undefined) {
this.placeholder.push(this.active.pop());
}
}
}
}
function processData(input) {
const queue = new Queue();
const inputArr = input.split('\n');
for (let i = 1; i < inputArr.length; i++) {
const action = inputArr[i][0];
switch (action) {
case '1':
const data = inputArr[i].slice(1).trim();
queue.enqueue(data);
break;
case '2':
queue.dequeue();
break;
case '3':
console.log(queue.peek());
break;
}
}
}