Stack & Queue

스택과 큐는 흔히 LIFO, FIFO로 알려져있는 자료구조이다.

Stack

선형 자료구조의 일종으로 LIFO(Last In First Out)의 구조를 가진다. 이는 나중에 들어간 원소가 가장 먼저 나온다는 의미이다. 이것이 스택의 가장 큰 특징이다. 차곡차곡 쌓이는 구조로 먼저 스택에 들어가게 된 원소는 가장 밑에 깔리게 되고 그 위로 하나씩 쌓이게 된다. 결과적으로 가장 먼저 들어간 원소는 가장 마지막에 나오게 된다.

Queue

선형 자료구조의 일종으로 FIFO(First In First Out)의 구조를 가진다. 이는 먼저 들어간 원소가 가장 먼저 나온다는 의미이다. 줄서기와 같다고 생각하면 이해하기 쉬운데, 줄서기처럼 가장 먼저 줄을 선 사람, 즉 가장 먼저 큐에 들어간 원소는 가장 먼저 나오게 된다.

Stack 두개로 Queue 구현하기

abcde로 구성된 리스트가 있다고 가정한다. 이 순서대로 큐에 넣게 되면 abcde순서 그대로 꺼낼 수 있다. 이를 스택 2개를 사용하여 구현하는 로직을 생각해보았다.

1. abcde를 스택1에 넣는다.

e
d
c
b
a

2. 스택1의 원소들을 꺼내어 바로 스택2에 하나씩 넣는다.

e				a
d				b
c		=> 		c
b				d
a				e

3. 스택2의 원소들을 꺼낸다.
   => abcde

이렇게 간단한 방법으로 큐와 같은 구조를 구상해보았다.