Stack & Queue

1. Stack

 Stack은 선형 자료구조의 일종으로 자료를 쌓아 올리는 형태의 자료구조입니다. Data를 맨 아래부터 쌓기 때문에 가장 먼저 넣은 원소가 늦게 나오고, 나중에 들어간 원소가 가장 먼저 나옵니다. (후입선출 : LIFO=Last In FIrst Out)

  자료의 삽입 삭제는 한 곳(Top)에서만 이뤄집니다. 만약 스택이 비어있을 때 자료를 꺼내려고 시도를 하면 Stack Underflow가 발생하고, 반대로 스택이 꽉 차있을 자료를 넣으려고 하면 Stack Overflow가 발생합니다..

 

 이 Stack은 재귀적인 알고리즘, 후위 표기법 계산, 역순 문자열 만들기에 쓰이며, 웹 브라우저의 뒤로가기, 문서작업에서 Ctrl+z(가장 나중에 수정한 내역을 되돌림)에 쓰입니다.

 

2. Queue

 Queue는 데이터들이 일렬로 줄을 서서 기다리는 것을 뜻합니다. 음식점에서 줄을 기다리는 것과 같습니다..

Stack과는 달리 Queue는 Rear부분에서 자료의 삽입이 Front에서 자료의 삭제가 이루어 집니다. 즉 선입선출(FIFO = First In First Out)의 자료구조를 가집니다. 

 이 Queue는 BFS 너비우선 탐색 알고리즘에 많이 사용되며, OS의 Task 스케쥴링에서 선입선처리를 위해 사용됩니다.