[Java] Stack 2개로 Queue 처럼 사용하기

java - Stack 2개로 Queue 구현하기

- 사실 Stack 2개로 Queue 처럼 구현할 일이 있는지는 잘 모르겠다... (그냥 Queue를 사용하면 되는 부분)

  하지만 상황에 따라 Stack을 Queue 방식으로 구현해야 할 수도 있고, 필자의 기준에서는 신박한 내용이었기에 구현과 포스팅을 해보려    한다.

 

- 자료구조에서 Stack, Queue 라는 개념을 한번쯤은 들어봤을 것이다! 간단하게 얘기하자면

Stack : 선입후출(FILO),  처음에 넣은 요소가 제일 마지막에 나오는 것이고

Queue : 선입선출(FIFO), 처음에 넣은 요소가 처음으로 나오는 것이다.

 

---

방법

목표 : 숫자 1,2,3,4 를 차례로 추가하고 1,2,3,4 순서대로 출력하는 것.

 

1. Stack이 A,B 2개가 있다고 가정하자.

2. Stack A는 추가, B는 출력의 용도라고 생각하면 쉬울것 같다.

3. 먼저 숫자 1, 2를 Add -> (A : 1,2   B: empty)

4. Pop() -> (A : empty   B: 2   출력: 1)

 

4번까지 보았을 때 이해가 된 사람들이 분명 있을 것이다.

*출력을 했을 때 Stack A에 요소들이 Stack B로 이동을 하게 되는것이다. 

즉 Stack B 에는 2, 1 이 순서대로 들어가게 되고 맨위에 있는 1이 출력이 되는 방식인것이다.

 

*여기서 만약 Stack B에 요소가 적재되어있고 A에 요소가 존재한다면? 

간단하게 Stack B의 내용을 pop 후에 Stack A의 내용을 B 로 옮기면 되는 것이다. 

 

그림을 간단하게 그려보는것도 이해하는것에 좋은것 같다.

---

Code

package stack_queue;

import java.util.Stack;

/************
 * @info : 2개의 stack으로 queue 표현하기
 * @name : StackQueue
 * @version : 1.0.0
 * @Description :
 ************/
public class StackQueue {

    // Stack OF Queue - queue 처럼 작동하는 Stack
    private static class StackOfQueue {
        Stack inStack;
        Stack outStack;

        // Constructor
        StackOfQueue() {
            this.inStack = new Stack();
            this.outStack= new Stack();
        }

        //stack add()
        private void addStack(int num) {
            inStack.add(num);
        }

        // stack pop()
        private int outQueue() {
            // 2번째 stack이 empty 상태라면?
            if(outStack.isEmpty()) {
                // 1번 stack이 empty 가 아닐때 까지 반복.
                while(!inStack.isEmpty()){
                    outStack.add(inStack.pop());
                }
            }
            return (int)outStack.pop();
        }
    }

    public static void main(String[] args) {
        StackOfQueue queue = new StackOfQueue();

        queue.addStack(1);
        System.out.println("first: "+ queue.outQueue());

        queue.addStack(2);
        queue.addStack(3);
        System.out.println("second: "+ queue.outQueue());
        System.out.println("third: "+ queue.outQueue());
    }
}

 

결과

- 의도 했던 대로 숫자 1,2,3을 순서대로 출력이 된것을 확인 할 수 있다. 

---

참고 및 출처: https://limkydev.tistory.com/185