스택과 큐

스택과 큐는 선형의 자료구조로 순서를 가지고 있고, 메모리에 연속적으로 저장된다.

스택과 큐 모두 배열과 연결리스트로 구현 가능하다. 배열로 구현할 경우 확실한 메모리의 사용크기를 알 수 없어 연결리스트로 구현하는 편이 좀 더 쉽다.

STACK

스택의 사전적 의미 "쌓이다" 처럼 데이터들이 차곡차곡 쌓이는 자료구조의 모습이다.

LIFO(Last In First Out, 후입선출) 구조로 가장 마지막에 저장된 데이터가 가장 먼저 출력된다. 

 

스택은 한 곳으로만 접근할 수 있으며 이 곳을 탑(또는 SP, 스택포인터)이라고 부른다. 스택의 주요 연산으로는 push(삽입)와 pop(삭제)이 있다.위의 그림에서 최초의 탑은 0번 인덱스를 가리키고 있고 데이터가 들어갈 때마다 탑이 가리키는 포인터는 다음 인덱스의 위치를 가리킨다. 스택은 주로 웹브라우저의 뒤로가기, 실행 취소, 연산자 후위 표기법, 함수의 콜 스택에서 활용된다. 그리고 DFS(깊이 우선 탐색)에서도 스택의 자료구조를 활용한다.

 

 

메모리에서 스택의 영역은 다음과 같다.

메모리의 구조

 

메모리의 영역 중 스택 영역은 Heap과 메모리 공간을 공유한다. 큰 메모리의 주소로부터 작은 메모리 주소로 데이터가 저장되게 된다. 

 

스택에 의해 발생되는 에러의 경우 StackOverFlow와 StackUnderFlow가 있다.

※StackOverFlow : 스택 메모리 공간이 다 찾을 경우에 발생하는 에러(ex. 재귀함수)

※StackUnderFlow : 스택 메모리가 비어있는데 계속해서 pop할 경우 발생

QUEUE

큐는 FIFO(First In First Out, 선입선출)구조로 가장 먼저 들어간 데이터가 가장 먼저 나온다. 스택과는 다르게 들어가는 입구와 나오는 입구가 존재한다. 들어가는 입구를 가리키는 포인터를 rear, 나오는 입구를 front라고 부르며 rear를 통해 들어와 front로 나오게 된다. 큐의 주요 연산은 Enqueue(삽입)와 Dequeue(삭제)가 있다.

프린터의 출력 순서, 스케줄링(여러 프로세스에게 적절한 자원 분배), BFS(너비 우선탐색), 버퍼 등에서 큐의 자료구조가 쓰인다.

 

DEQUE

Deque는 Double Ended Queue로 스택과 큐의 특징을 모두 가지고 있다. 큐와 같이 두 곳의 입구가 있고 두 곳에서 삽입과 삭제가 이루어진다. 필요에 따라 스택과 큐로 활용할 수 있으며  끝에 해당하는 데이터의 삽입과 삭제에 있어서 시간복잡도가 O(1)로 굉장히 빠른 속도를 가지고 있어 삽입, 삭제의 시간복잡도가 O(n)인 리스트보다 효율적이다.