오늘은 스택으로 큐를 구현하는 문제를 살펴보겠습니다.
스택은 LIFO - Last In First Out 방식이다.
간단하게 설명하면 책상 위에 책을 하나씩 쌓아두고 위에서부터 하나씩 집어서 읽는 것이다.
- 나중에 쌓은(제일 위에 있는) 책을 먼저 집어서 읽는 방식
큐는 FIFO - First In First Out 방식이다.
간단하게 설명하면 카페에서 한 줄로 서서 주문을 하는 것이다.
스택과 큐에 대한 설명과 코드는 이 블로그의 글을 참조하고, 오늘은 스택으로 큐를 구현해 보겠습니다.
문제
스택을 사용하여 큐를 구현하여라
- enqueue
- dequeue
- peek
- length
- isEmpty
힌트
스택으로 큐를 구현하기 위해서는 스택을 두 개 사용하여야 한다.
하나는 inStack(enqueue시 쌓이는 스택), 다른 하나는 outStack(dequeue시 꺼내는 스택)
설명
Enqueue
- outStack이 비어있는지 확인하고, outStack에 data가 있다면, inStack으로 옮겨준다.
- outStack이 비어있다면, inStack에 데이터를 넣는다.
Dequeue
- inStack이 비어있는지 확인하고, inStack에 data가 있다면, outStack으로 옮겨준다.
- inStack이 비어있다면, outStack에서 data를 뽑는다.
Enqueue 설명
stack을 두개를 만든다.
하나는 Enqueue할 때 사용하는 inStack, 다른 하나는 Dequeue할 때 사용하는 outStack.
outStack이 비어있다면, inStack에 데이터를 넣는다.
inStack이 비어있는지 확인하고, inStack에 data가 있다면, outStack으로 옮겨주고 data를 inStack으로 넣는다.
Dequeue 설명
inStack이 비어있는지 확인하고, inStack에 data가 있다면, outStack으로 옮겨준다.
inStack이 비어있다면, outStack에서 data를 뽑는다.
코드
javascript 로 구현
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
|
const stack = () => {
let stackArray = [];
return {
push(item) {
stackArray.push(item);
},
pop() {
return stackArray.pop();
},
peek() {
return stackArray[stackArray.length - 1];
},
get length() {
return stackArray.length;
},
isEmpty() {
return stackArray.length === 0;
},
}
}
const queue = () => {
const inStack = stack();
const outStack = stack();
return {
enqueue(item) {
if(!outStack.isEmpty()) {
while(!outStack.isEmpty()) {
inStack.push(outStack.pop());
}
}
inStack.push(item);
},
dequeue() {
if(!inStack.isEmpty()) {
while(!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
return outStack.pop();
},
peek() {
if(!inStack.isEmpty()) {
while(!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
return outStack.peek();
},
get length() {
if(!inStack.isEmpty()) {
while(!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
return outStack.length;
},
isEmpty() {
return this.length === 0;
}
}
}
const q = queue();
console.log(q.isEmpty())
q.enqueue(1)
console.log(q.peek())
q.enqueue(2)
q.enqueue(3)
console.log(q.peek())
q.enqueue(4);
console.log(q.dequeue());
console.log(q.isEmpty())
console.log(q.dequeue());
|
결과
1
2
3
4
5
6
|
true
1
1
1
false
2
|
Related Posts