Stack

Stack

시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO(Last In First Out)형식으로 데이터를 저장하는 자료구조
활용 예시로는 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로가기), 깊이우선탐색(DFS) 등

push & pop

• push : stack에 데이터를 추가하는 것, 맨 뒤 데이터를 추가하면 완료되기 때문에 시간복잡도는 O(1)
• pop : stack에 데이터를 추출하는 것, 맨 뒤 데이터를 삭제하면 완료되기 때문에 시간복잡도는 O(1)

Stack 두 개를 이용하여 Queue 구현

구현 방법

queue의 enqueue()를 구현할 때 첫 번째 stack을 사용하고, dequeue()를 구현할 때 두 번째 stack을 사용하면 queue를 구현할 수 있음

instack - enqueue
outstack - dequeue

1. enqueue : instack에 push를 하여 데이터를 저장
2. dequeue :
   - 만약 outstack이 비어있다면 instack.pop()을 하고 outstack.push()를 하여 instack에서 outstack으로 모든 데이터를 이동 -> 가장 먼저 왔던 데이터가 top에 위치하게 됨
   - outstack.pop()을 하면 가장 먼저 enqueue된 데이터가 가장 먼저 추출 (FIFO)
   

시간 복잡도

• enqueue : instack.push()를 한번만 하면 되기 때문에 시간복잡도는 O(1)
• dequeue :
  1. worst case는 outstack이 비어있는 경우 : instack에 있는 n개의 데이터를 instack.pop()을 한 이후에 outstack.push()를 하기 때문에 시간복잡도는 O(n)
  2. outstack이 비어있지 않는 경우 : outstack.pop()만 해주면 되기 때문에 시간복잡도는 O(1)
     두 가지 경우를 종합했을 때, amortized O(1)