스택과 큐에 대해서 설명해 주세요.

• 스택과 큐 모두 선형 자료구조로, 배열과 연결 리스트를 사용해 구현할 수 있다.

• 스택과 큐의 가장 큰 차이점은 스택은 후입선출(LIFO) 방식, 큐는 선입선출(FIFO)의 방식으로 사용되는 것이다.

꼬리 질문

스택으로 큐를 만들 수 있는가?

스택 2개로 큐를 만들 수 있다.

1. 메인 스택과 서브 스택을 만든다.

2. 메인 스택에 데이터를 모두 push

   • 큐에서 Dequeue를 하려면 메인 스택의 데이터를 모두 pop해서 서브 스택에 push한다.

   • 그러면 메인 스택의 데이터들의 순서가 뒤집히게 되고, 이때 서브 스택에서 pop하면 Dequeue와 같은 효과가 된다.

3. 큐의 Enqueue를 하려면 메인 스택에 데이터를 그대로 push

정리하면 Dequeue 연산을 할 때 반대편 비어있는 스택에 모든 데이터를 옮겨 역방향으로 만든 다음, 옮겨진 스택에서 pop을 하면 스택 2개로 큐를 구현할 수 있다.

큐로 스택을 만들 수 있는가?

큐 2개로 스택을 만들 수 있다.

• 메인 큐에서 데이터를 하나씩 넣을 때 기존 메인 큐에 들어있던 데이터를 pop해서 서브 큐에 push한다.

• 서브 큐에 데이터가 들어오면 기존에 있던 데이터를 pop해서 메인 큐에 push 한다.

• 모든 데이터에 대해 반복한다.

• 메인 큐에서 하나씩 pop을 하면 스택과 같은 형태로 데이터를 뽑을 수 있다.