Stack을 활용해서 Queue만들기

Stack을 활용해서 Queue를 만들고,  Queue를 활용해서 Stack을 만들기 위해서는 우선 Stack과 Queue에 대한 이해가 필요하다.

큐

큐는 한쪽 끝에서 삽입, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.

삭제 연산은 프론트에서, 삽입 연산은 리어(rear)에서만 이루어지며, 삭제 연산을 디큐(dnQueue) 삽입 연산 인큐(enQueue)라고 한다.

큐는 선입선출의 구조를 가진다.

BFS(넓이 우선 탐색)를 할 때 사용한다.

 

스택

스택은 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고 top으로 정한 곳을 통해서만 접근가능하다.

스택은 후입선출의 구조를 가진다.

DFS(깊이 우선 탐색)를 할 때 사용한다.

 

여기서 핵심은, 큐는 선입 선출의 구조를, 스택은 후입 선출의 구조를 갖는다는 것이다.

 

스택을 활용해서 큐만들기

스택을 활용해서 큐를 만들기 위해서는 두개의 스택이 필요하다.

편의상 첫번째 스택을 s1, 두번째 스택을 s2라고 하겠다.

 

• enqueue 구현 방법
  • enqueue의 구현방법은 간단하다.  s1에 push를 해서 데이터를 저장하면된다.
• dequeue 구현 방법
  • s2가 비어있다면, s1을 pop하고 그 데이터를 s2에 push한다,

이 상태에서 s2.pop을 하면 스택은 후입선출의 구조이기 때문에 가장 최근의 데이터(enqueue했을 때 가장 처음에 들어온 데이터)가 가장 먼저 출력되어 선입 선출의 구조를 만들어낼 수 있다.

 

코드

import java.util.Stack;

public class test1<T> {
  Stack<T> s1 = new Stack<>();
  Stack<T> s2 = new Stack<>();

  private void check() {
    if (s2.size() == 0)
      while (s1.size() != 0)
        s2.push(s1.pop());
  }

  public void enqueue(T t) {
    s1.push(t);
  }

  public T dequeue() {
	check();
	return s2.pop();
  }
}

 

다음 게시글에서는 Queue를 활용해서 Stack을 만드는 방법을 다루겠다.