Stack과 Queue 뿌시기

🤓오늘의 공부 주제: Stack과 Queue🤓

Q. Stack은 어떤 자료 구조인가?

A. Stack은 후입선출 LIFO(Last In First Out)의 자료구조. 시간복잡도는 push O(1) , pop O(1). 활용 예시는 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS) 등

Q. Stack 두 개를 이용하여 Queue를 구현

A. queue의 enqueue()를 구현할 때 첫 번째 stack을 사용하고, dequeue()를 구현할 때 두 번째 stack을 사용하면 queue를 구현.
편의상 enqueue()에 사용할 stack을 instack이라고 부르고 dequeue()에 사용할 stack을 outstack.

1. enqueue() :: instack에 push()를 하여 데이터를 저장합니다.

2. dequeue() ::

   1. 만약 outstack이 비어 있다면 instack.pop() 을 하고 outstack.push()를 하여 instack에서 outstack으로 모든 데이터를 옮겨 넣습니다. 이 결과로 가장 먼저 왔던 데이터는 outstack의 top에 위치하게 된다.
   2. outstack.pop()을 하면 가장먼저 왔던 데이터가 가정 먼저 추출된다.(FIFO)

   import java.util.Stack;
   
   class Queue<T> {
       private Stack<T> instack;
       private Stack<T> outstack;
   
       public Queue() {
           instack = new Stack<>();
           outstack = new Stack<>();
       }
   
       public void enqueue(T element) {
           instack.push(element);
       }
   
       public T dequeue() {
           if (outstack.isEmpty()) {
               while (!instack.isEmpty()) {
                   outstack.push(instack.pop());
               }
           }
           return outstack.pop();
       }
   
       public static void main(String[] args) {
           Queue<Integer> queue = new Queue<>();
   
           queue.enqueue(1);
           queue.enqueue(2);
           queue.enqueue(3);
   
           System.out.println(queue.dequeue()); // Output: 1
           System.out.println(queue.dequeue()); // Output: 2
           System.out.println(queue.dequeue()); // Output: 3
       }
   }

```

Q. Queue 두 개를 이용하여 Stack을 구현

편의상 push()에 사용할 queue는 q1이라고 부르고 pop()에 사용할 queue를 q2.

1. push() :: q1으로 enqueue()를 하여 데이터를 저장합니다.

2. pop() ::

   1. q1에 저장된 데이터의 갯수가 1 이하로 남을 때까지 dequeue()를 한 후, 추출된 데이터를 q2에 enqueue()합니다. 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이터는 q2로 옮겨진다.
   2. q1에 남아 있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환한다.(LIFO)
   3. 다음에 진행될 pop()을 위와 같은 알고리즘으로 진행하기 위해 q1과 q2의 이름을 swap한다.

    import java.util.LinkedList;
    import java.util.Queue;
   
    class Stack<T> {
        private Queue<T> q1;
        private Queue<T> q2;
   
        public Stack() {
            q1 = new LinkedList<>();
            q2 = new LinkedList<>();
        }
   
        public void push(T element) {
            q1.offer(element);
        }
   
        public T pop() {
            while (q1.size() > 1) {
                q2.offer(q1.poll());
            }
   
            Queue<T> temp = q1;
            q1 = q2;
            q2 = temp;
   
            return q2.poll();
        }
   
        public static void main(String[] args) {
            Stack<Integer> stack = new Stack<>();
   
            stack.push(1);
            stack.push(2);
            stack.push(3);
   
            System.out.println(stack.pop()); // Output: 3
            System.out.println(stack.pop()); // Output: 2
            System.out.println(stack.pop()); // Output: 1
        }
    }
   
   		```

Q. Queue vs priority queue를 비교

Queue 자료구조는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out) 구조로 저장하는 형식. 이와 다르게 우선순위큐(priority queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옵니다.

Queue의 operation 시간복잡도는 enqueue O(1), dequeue O(1)이고,

Priority queue는 push O(logn) , pop O(logn) 입니다

1. push() :: q1으로 enqueue()를 하여 데이터를 저장합니다.
2. pop() ::
   1. q1에 저장된 데이터의 갯수가 1 이하로 남을 때까지 dequeue()를 한 후, 추출된 데이터를 q2에 enqueue()합니다. 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이터는 q2로 옮겨진다.
   2. q1에 남아 있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환한다.(LIFO)
   3. 다음에 진행될 pop()을 위와 같은 알고리즘으로 진행하기 위해 q1과 q2의 이름을 swap한다.

출처 : 인프런 - 기출로 대비하는 개발자 전공면접 [CS 완전정복]