Stack과 Queue의 차이점에 대해 설명해보세요
Keyword
LIFO, FIFO
Script
Stack은 자료의 입력과 출력을 한 곳으로 제한한 자료구조입니다. 그래서 LIFO(Last In First Out) 구조로, 마지막에 삽입된 데이터가 먼저 삭제되는 자료구조입니다.
반면 Queue는 자료의 입력과 출력을 양쪽 끝으로 제한한 자료구조입니다. 그래서 FIFO(First In First Out) 구조로 먼저 삽입된 데이터가 먼저 삭제되는 자료구조입니다.
Additional
Stack의 사용예시
웹 브라우저 방문기록을 Stack으로 구현할 수 있다. 마지막으로 방문한 웹 사이트를 가장 먼저 조회할 수 있기 때문에, 뒤로 가기 기능을 구현할 때 유용하다.
함수의 call stack도 Stack의 예시이다. call stack에는 해당 함수가 사용하는 지역 변수, 인수, 호출한 함수의 stack 정보, return address 등이 저장된다. 이 stack은 각 함수 call 마다 생성되며, 이를 통해 여러 함수들이 중첩되어 사용할 수 있게 된다.
Queue의 사용예시
프린터의 인쇄 대기열을 Queue로 구현하면, 먼저 요청된 작업부터 차례대로 수행할 수 있다.
또 버퍼의 경우도 Queue로 구현했을 때, pending 중인 작업 중 가장 먼저 처리할 것부터 순차적으로 처리할 수 있다.
덱(Deque, Double-ended Queue)
Deque는 양방향 큐이다. Stack과 Queue가 결합된 자료구조라고도 할 수 있다. 특징은 양쪽 끝에서 추가와 제거를 모두 수행할 수 있다는 것이다.
즉 양 끝에서 발생하는 삽입과 삭제에 대해 O(1)의 시간복잡도로 수행할 수 있다. 물론 중간에 데이터를 삽입하거나 삭제할 때는 O(n) 시간복잡도를 가진다. 이는 Deque가 Array처럼 연속된 물리적 공간에 저장되도록 구현되기 때문인데, 이 덕분에 Queue와는 다르게 index를 이용한 Random Access가 가능하다.
원형 큐(Circular Queue)
일반적인 Queue는 선형 자료구조이다. 원형 Queue는 선형 Queue의 단점인 "공간의 효율성"을 보완한다. 즉, '메모리 재사용'을 가능하게 한다.
배열로 구현된 선형 Queue는 원소가 빠져나가고 남은 공간을 다시 사용할 수 없다. 남은 공간을 사용하기 위해서는 다시 모든 데이터를 앞으로 이동시켜야하는데, 이는 O(n)의 시간복잡도가 소요된다.
반면 원형 Queue는 주어진 크기에서 앞의 공간이 남게 되면, Queue의 끝을 앞으로 가져와 일종의 순환고리를 만든다.
실제 구현에서는 front를 통해 첫번째 데이터를 가르키고, rear를 통해 마지막 데이터를 가르키게 하면서, 원형 Queue의 처음과 끝을 표현할 수 있다.
주의할 점은 공백 상태와 포화 상태 모두 front와 rear가 0을 가르키게 되는데, 공백과 포화를 구분하기위해 항상 하나의 공간을 비워둔다.
Stack 을 사용하여 미로찾기 구현하기
일반적으로 DFS 알고리즘을 수행하는데 Stack을 사용할 수 있다. 그리고 DFS 알고리즘을 통해 미로를 탐색하는 알고리즘을 구현할 수 있다.
Stack에는 지금까지의 경로를 삽입하게 된다. 현재 좌표에서 가능한 모든 방향의 좌표를 Stack에 삽입하고, 마지막으로 삽입한 좌표로 이동한다. 만약 되돌아가는 것 이외에 더 갈 수 있는 곳이 없다면 Stack에서 경로를 삭제하면서 다시 되돌아간다.
만약 탐색과정에서 출구를 만나면 Exit을 할 수 있고, 출구를 만나기 전에 Stack이 비어있게 되면, 출구를 찾을 수 없는 경우임을 알 수 있다.
두개의 Stack을 가지고 Queue를 구현
두 개의 Stack이 있다면, Queue를 구현할 수 있다.
먼저 데이터가 삽입될때는 첫번째 Stack으로 삽입한다.
그리고 데이터의 삭제 명령이 떨어졌을 때, 만약 두번째 Stack이 비어있다면, 첫번째 Stack에서 모든 원소를 삭제하고 두번째 Stack에 삽입한다.
이 과정에서 원소의 순서가 reverse되기 때문에, 여기에서 삭제 연산을 수행하면 가장 먼저 들어온 데이터가 먼저 빠져나가게 되는 Queue처럼 동작한다.
Stack을 통한 괄호의 유효성 검사
Stack의 LIFO 구조를 이용해서 괄호의 유효성 검사도 수행할 수 있다.
괄호는 기본적으로 왼쪽, 오른쪽 괄호가 모두 존재해야 올바르게 사용한다고 할 수 있다.
그리고 가장 내부의 괄호부터 생각해보면, 왼쪽 괄호가 나온다음 바로 오른쪽 괄호가 나온다.
아래 수식을 보자.
(1 + (2 + (4 * 5 + 1) * 3) * 9)왼쪽 괄호가 들어오면, Stack에 추가한다.
오른쪽 괄호가 들어오면, 마지막에 들어온 괄호와 짝을 비교하고, Stack에서 삭제를 수행한다.
이 때, 작업이 모두 끝났을 때, Stack이 비어있지 않다면 잘못된 괄호가 있다는 것이다.
