LeetCode 문제 중 난이도 Easy인 Implement Queue using Stacks이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.
문제해석
스택의 오퍼레이션을 이용하여 큐의 다음 오퍼레이션들을 구현하라.
push(x) -- 큐의 마지막에 x를 삽입
pop() -- 큐의 맨앞의 요소를 제거
peek() -- 맨앞의 요소를 가져옴
empty() -- 큐가 비었는지 여부를 리턴
스택(Stack)은 LIFO(Last-In, First-Out), 큐(Queue)는 FIFO(First-In, First-Out)의 구조를 가졌다. 스택과 큐를 잘 모른다면 아래 포스팅을 참고한다.
스택으로 큐를 구현하려면, ① 넣을때부터 FIFO로 넣던지 ② 넣을때는 LIFO로 넣고 꺼낼때 FIFO로 꺼내면 된다.
① FIFO처럼 저장하는 방법은 마지막으로 넣는 요소를 스택의 가장 아래(bottom)에 저장하는 것이다. 그러면 스택에서 꺼낼때, 먼저 저장된 요소가 먼저 꺼내진다(FIFO). 코드로 나타내면 아래와 같다.
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 | class MyQueue { Stack<Integer> myqueue = new Stack<Integer>(); public MyQueue() { } public void push(int x) { Stack<Integer> temp = new Stack<Integer>(); //myqueue에 있는 요소들을 temp으로 옮겨담는다 while(!myqueue.isEmpty()){ temp.push(myqueue.pop()); } //temp의 맨 위에 x를 삽입한다 temp.push(x); //myqueue에 다시 옮겨담는다(가장 마지막에 넣은 x가 temp의 가장 아래로 가게됨) while(!temp.isEmpty()){ myqueue.push(temp.pop()); } } public int pop() { return myqueue.pop(); } public int peek() { return myqueue.peek(); } public boolean empty() { return myqueue.isEmpty(); } } | cs |
② 넣을때는 LIFO로 넣고 꺼낼때 FIFO처럼 꺼내는 방법은 저장할때는 그냥 스택의 맨 위(top)에 저장한다. 꺼낼때에는 스택의 맨 마지막에 있는 요소를 불러온다. 코드로 나타내면 아래와 같다.
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 | class MyQueue { Stack<Integer> myqueue = new Stack<Integer>(); public MyQueue() { } public void push(int x) { myqueue.push(x); } public int pop() { Stack<Integer> temp = new Stack<Integer>(); //myqueue의 요소들을 전부 temp에 옮겨담는다 while(!myqueue.isEmpty()){ temp.push(myqueue.pop()); } //temp의 가장 위에있는 요소를 꺼낸다 int top = temp.pop(); //원래대로 myqueue에 옮겨담는다 while(!temp.isEmpty()){ myqueue.push(temp.pop()); } return top; } public int peek() { Stack<Integer> temp = new Stack<Integer>(); while(!myqueue.isEmpty()){ temp.push(myqueue.pop()); } int top = temp.peek(); while(!temp.isEmpty()){ myqueue.push(temp.pop()); } return top; } public boolean empty() { return myqueue.isEmpty(); } } | cs |
'코딩문제(LeetCode) > Easy' 카테고리의 다른 글
| [코딩연습] Occurrences After Bigram 바이그램 뒤에 나타나는 문자열 (2) | 2019.06.10 |
|---|---|
| [코딩연습] Flipping an Image 이미지 뒤집기 (0) | 2019.05.22 |
| [코딩연습] LeetCode Lemonade Change 거스름돈 나눠주기 (0) | 2019.05.12 |
| [LeetCode] Student Attendance Record I 출석기록 (0) | 2019.05.09 |
| [코딩연습] Remove Outermost Parentheses 바깥 괄호 제거하기 (0) | 2019.05.05 |
