Stack

Stack은 어떤 자료구조 인가요?

stack은 후입선출 LIFO(Last In First Out)의 자료구조 입니다. 시간복잡도는 push O(1), pop O(1)입니다. 활용 예시는 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS)등이 있습니다.

 

LIFO

stack은 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO(Last In First Out)형식으로 데이터를 저장하는 자료구조 입니다.

 

 

push & pop

stack에서 데이터를 추가하는 것을 push라고 하고 데이터를 추출 하는 것은 pop이라고 합니다. push의 경우 stack의 맨 뒤에 데이터를 추가하면 완료되기 때문에 시간복잡도는 O(1)입니다. 이와 동일하게 pop의 경우도 맨 뒤의 데이터를 삭제하면 완료 되기 때문에 O(1)의 시간복잡도를 갖습니다. push와 pop은 모두 stack의 top에 원소를 추가하거나 삭제하는 형식으로 구현됩니다.

 

 

활용

stack은 재귀적인 특징이 있어서 프로그램을 개발할 때 자주 쓰이는 자료구조 입니다. 활용 예시로는 call stack, 후위 표기법 ㅇ녀산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤도 가기), 깊이우선탐색(DFS) 등이 있습니다.

 

 

Stack 두 개를  이용하여 Queue를 구현한다면?

queue위 enqueue()를 구현할 때 첫 번째 stack을 사용하고, dequeue()를 구현할 때 두번째 stack을 사용하면 queue를 구현할 수 있습니다. 

 

편의상 enqueue()를 사용할 stack을 instack이라고 부르고 dequeue()에 사용할 stack을 outstack이라고 칭하겠습니다. 두 개의 stack으로 queue를 구현하는 방법은 다음과 같습니다. 

 

1. enqueue() :: instack에 push()를 하여 데이터를 저장합니다. -> instack.push()를 한번만 하면 되기 때문에 시간 복잡도는 O(1)입니다.
2. dequeue() :: 만약 outstack이 비어 있다면 instack.pop()을 하고 outstack.push()를 하여 instack에서 outstaack으로 모든 데이터를 옮겨 넣습니다. 이 결과로 가장 먼저 왔던 데이터는 outstack의 top에 위치하게 된다. 그리고 outstack.pop()을 하면 가장먼저 왔던 데이터가 가장 먼저 추출된다.(FIFO) -> 두 가지 경우를 따져봐야 합니다. worst case는 outstack이 비어있는 경우입니다. 이 때는 instack에 있는 n개의 데이터를 instack.pop()을 한 이후에 oustack.push()를 해줘야 합니다. 따라서 총 2*n번의 작업이 실행되어야 하므로 O(n)의 시간복잡도를 갖습니다. 하지만 outstack이 비어있지 않는 경우에는 outstack.pop()만 해주면 됩니다. 이는 O(1)의 시간복잡도를 갖습니다. 이를 종합했을때, amortized O(1)의 시간복잡도를 갖는다고 할 수 있습니다.

 

 

Queue 두 개를 이용하여 stack을 구현한다면?

편의상 push()에 사용할 queue는 q1이라고 부르고 pop()에 사용할 queue를 q2라고 칭하겠습니다. 두 개의 queue로 stack을 구현하는 방법은 다음과 같습니다.

1. push() :: q1으로 enqueue()를 하여 데이터를 저장합니다. -> q1.enqueue()를 한번만 하면 되기 때문에 O(1)의 시간복잡도를 갖습니다. 
2. pop() ::  q1에 저장된 데이터의 갯수가 1 이하로 남을 때까지 dequeue()를 한 후, 추출된 데이터를 q2에 enqueue()합니다. 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이터는 q2로 옮겨진다. 그리고 q1에 남아 있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환한다. (LIFO) 마지막으로 다음에 진행될 pop()을 위와 같은 알고리즘으로 진행하기 위해 q1과 q2의 이름을 swap한다. -> q1에 저장되어 있는 n개의 원소중에 n-1개를 q2로 옮겨야 하므로 Q(n)이 됩니다.