[Data Structure/자료구조] 스택과 큐(Stack & Queue&Deque)

스택과 큐

Stack과 Queue는 선형 자료구조의 일종이며, Array와 LinkedList로 구현할 수 있다.

 

스택과 큐 사용사례를 설명해주세요.

Stack

주로 FILO가 필요한 환경에서 사용된다.

• 자바의 Stack 메모리 영역: 지역변수와 매개변수 데이터 값이 저장되는 공간이며, 메소드 호출시 메모리에 할당되고 종료되면 메모리가 해제되며, LIFO(Last In First Out)구조를 가진다.
• 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

Queue

주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.

• OS의 스케쥴러: 자원의 할당과 회수를 하는 스케쥴러 역할을 큐가 할 수 있다.
  메모리에 적재된 다수의 프로세스 중 어떤 프로세스에게 자원을 할당할 것인가 그 순서를 결정하는 것이 자원의 효율적인 사용에 있고, 가장 단순한 형태의 스케쥴링 정책이 선입선처리(First Com First Served) 즉, 큐라고 볼 수 있다.
• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

 

스택과 큐를 비교하고, 구현 방법에 대해 설명해 주세요.

Stack

• 스택은 FILO구조로 차곡차곡 쌓아올린 형태의 자료구조이다.
• 형태: 스택은 정해진 방향으로만 자료를 쌓을 수 있고 가장 위(top)을 통해서만 접근할 수 있다.
            top은 가장 최근에 들어온 자료가 된다.
            스택에서는 자료를 삭제할때도 top을 통해서만 가능하다.
            스택에서 top을 통해 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'이라고 한다.
• 구현: 배열기반 구현시, 스택은 마지막에 넣은 자료를 먼저 빼는 구조이기 때문에 자료를 넣고 뺄 때 기존의 자료들의 위치를 변경할 필요가 없다. 단순히 넣고 빼면 되므로 삽입/추출 시, O(1) 수준의 시간복잡도를 요구한다.
           리스트기반 구현시, 스택은 마지막에 넣은 자료를 삽입 혹은 추출 시, 기존의 마지막에 넣어져 있던 자료(tail)와의 상호 prev/next 관계만 바꾸어주면 되므로 삽입/추출 시, O(1) 수준의 시간복잡도를 요구한다.(LinkedList)

Queue

• 큐는 LIFO구조로 앞뒤가 뚫린 터널이나 원통 형태의 자료구조이다.
• 형태: 정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리, 큐는 한쪽 끝에서 삽입, 다른 쪽 끝에서 삭제가 양쪽으로 이루어진다.
          큐에서 프론트는 가장 먼저 큐에 들어왔던 첫 번째 원소, 리어는 가장 늦게 큐에 들어온 마지막 원소가 된다.
• 구현: 배열기반 구현시, 큐는 그와 반대로 먼저 넣은 자료를 먼저 빼는 구조이므로 자료를 넣고 뺄 때, 기존에 삽입된 자료들의 위치를 변경해야 한다. 따라서 삽입/추출 시, O(n) 수준의 시간복잡도가 요구된다.
           리스트기반 구현시, 큐는 먼저 넣은 자료를 삽입 혹은 추출 시, 기존의 가장 앞에 넣어져 있던 자료(head)와의 상호 prev/next 관계만 바꾸어주면 되므로 삽입/추출 시, O(1) 수준의 시간복잡도가 요구된다.(LinkedList)

 

원형 큐(Circular Queue)란? 사용하는 이유는 무엇인가?

• 배열을 이용한 queue는 이미 사용한 영역인 front의 앞부분에 대해서 다시 활용을 못하기 때문에 메모리를 낭비한다는 단점이 있었다.
  그리고 이동 큐를 이용하여 큐가 다 찼을 경우 데이터들을 앞쪽으로 이동시켜 사용하는 방법이 있지만 남아있는 모든 데이터를 다 이동시켜야 한다는 불편한 작업을 수행해야 하기 때문에 그리 효율적으로 동작하지 못한다고 했었다.
  원형 큐는 이와같은 단점을 보완하는 구조로 큐의 맨 끝과 맨 처음이 연결된 형태의 구조이기 때문에 이미 꺼내어 사용한 큐의 앞부분에 다시 데이터를 저장하여 재사용이 가능한 형태의 큐이다.

 

Deque는 어떻게 구현할 수 있을까요?

• deque는 큐의 양쪽에서 데이터를 넣고 뺄 수 있는 형태의 자료구조이다. 하나의 자료구조에 stack과 queue의 형태를 합쳐놓은 것이라고 생각할 수 있다.
  deque는 양쪽으로 입출력이 모두 가능하지만 한쪽으로만 출력할 수 있도록 설정할수도 있다. 이것을 셸프shelf 라고 한다.
• Java에서 deque는 인터페이스로 구현되어 있다.