[Data Structure] Stack과 Queue

[2d3k]

1. Stack과 Queue에 대해 설명하시오

2. Stack 2개로 Queue를 구현하는 방법을 설명해주시오.

[2d3k]

1. 스택은 후입선출의 개념으로 가장 마지막에 들어온 데이터가 가장 먼저 나온다. 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고, top으로 정한 곳을 통해서만 접근할 수 있다. 큐는 선입선출의 개념으로 가장 먼저 들어온 데이터가 가장 먼저 나온다. 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양방향에서 이루어진다. 스택의 예시에는 웹 페이지 뒤로가기, 실행 취소 등이 있고, 큐의 예시로는 은행 업무, 서비스센터의 대기 시간 등이 있습니다.

[2d3k]

2. 스택을 큐처럼 먼저 들어온 것이 먼저 나가게 만들어야 된다.

public class Queue {

    private Stack firstBox = new Stack();
    private Stack secondBox = new Stack();

    public void enQueue(Object item) {
        firstBox.add(item);
    }

    public Object deQueue() {

        if (secondBox.isEmpty()) {
            while(!firstBox.isEmpty()) {
                secondBox.push(firstBox.pop());
            }
        }
        return secondBox.pop();
    }

    public static void main(String[] args) {
        Queue queue = new Queue();
        queue.enQueue("A");
        queue.enQueue("B");
        queue.enQueue("C");

        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
    }

}


출력결과
A,B,C

[hyeonayou]

1. 스택의 특징은 TOP으로 정한 곳을 통해서만 삽입 삭제가 가능하며 후입선출 구조를 이루고 큐는 Front, rear로 제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)라고 하며 선입 선출 방식의 구조를 이룬다.

[hyeonayou]

2. 스택1로는 데이터를 입력 받고 스택 2로는 데이터를 pop 한다. 스택2가 비어있다면 스택 1에서 스택2로 데이터를 옮긴다.

import java.util.Stack;

public class Queue<T> {
  Stack<T> stack1 = new Stack<>();
  Stack<T> stack2 = new Stack<>();

  private void moveIfAbsent() {
    if (stack2.size() == 0)
      while (stack1.size() != 0)
        stack2.add(stack1.pop());
  }

  public void add(T t) {
    stack1.add(t);
  }

  public T peek() {
    moveIfAbsent();
    return stack2.peek();
  }

  public T poll() {
    moveIfAbsent();
    return stack2.pop();
  }

  public int size() {
    return stack1.size() + stack2.size();
  }
}