언어 책을 보면 스택이나 힙, 큐, 데크라는 말이 나옵니다. 물론 이 말의 뜻을 몰라도 프로그램 짜는데 어려움은 없습니다. 모든 것은 컴파일러라 알아서 해주니까요. 그렇지만 용어의 의미도 모르고 프로그램을 만들려면 조금 답답합니다.
이들 용어는 사용하는 곳에 따라서 의미가 조금 다릅니다. 자료 구조에서 사용할 때와 메모리에서 사용할 때 의미가 조금씩 다릅니다. 자료 구조론에서는 스택과 큐, 데크 등의 용어를 사용합니다. 반면 프로그램을 만들 때는 스택과 힙이라는 용어를 많이 사용합니다.
먼저 우리가 보통 스택과 큐, 힙을 말할 때는 C나 C++의 메모리 구조와 관련된 용어로 사용 합니다. C/C++에서 메모리는 다음과 같은 계층을 이룹니다.
1. 코드(code) 영역
2. 데이터(data) 영역
3. 힙(heap) 영역
4. 스택(stack) 영역
코드 영역은 코드 자체를 구성하는 메모리 영역입니다. 즉 프로그램 명령이 위치하는 곳으로 기계어로 제어되는 메모리 영역입니다. 하위 메모리라고 부르는 가장 낮은 쪽에 있는 메모리 영역입니다. 이 부분은 기계어 부분이므로 프로그래머가 신경 쓸 이유가 없습니다.
데이터 영역에는 데이터가 보관됩니다. 예를 들면 전역(global) 변수, 정적(static) 변수, 그외 초기화된 각종 배열과 구조, 자료들이 저장됩니다.
힙 영역은 프로그래머가 스스로 할당한 메모리 영역을 뜻합니다. 즉 터보C의 함수 중에 메모리를 할당하는 함수인 malloc() 등을 사용하여 배정한 메모리가 힙 영역에 해당합니다. 메모리 모델에 따라서 사용하는 함수가 달라지는데 메모리 할당 때는 malloc() farmalloc() 함수를 사용하고 재배정 때는 realloc() 함수를, 메모리 해제 때는 free()나 farfree() 함수를 사용합니다.
스택 영역은 프로그램이 자동으로 사용하는 임시 메모리 영역에 해당합니다. 즉 자동 변수를 저장하거나 함수로 인수를 보낼 때, 복귀 번지를 저장할 때 등에 사용합니다.
스택과 힙은 사용 용도에 따라서 조금씩 다른 의미로 사용합니다. 예컨대 버퍼 메모리에서 스택고 힙이라는 용어를 사용하면 버퍼 메모리를 구성하는 두 가지 방식을 뜻합니다. 이때 스택은 후입선출(LIFO=Last In First Out) 방식의 버퍼를 말하고, 힙은 선입선출(FIFO=First In First Out) 방식의 버퍼를 뜻합니다.
스택의 경우 후입선출 방식이므로 동작 과정이 푸시(push)와 팝(pop)의 과정으로 이루어집니다. 이를 통해 동작이 한 쪽 끝(top)에서만 일어납니다. 다시 말해서 자료가 들어가는 구멍(입구)과 나오는 구멍(출구)이 하나입니다. 이 때문에 맨 마지막에 들어간 것이 제일 먼저 나오는 겁니다.
큐(Queue)는 프로그램 언어에서 보면 자료 구조의 한 형태로 순차 목록의 한 형태를 뜻합니다. 원소의 삽입은 뒤(rear)에서 이루어지고 삭제는 앞(front)에서 이루어지는 자료 구조를 뜻합니다. 메모리에 적용할 경우 큐는 선입선출 방식을 뜻합니다. 이 때문에 힙과 큐를 혼동해서 사용하기도 합니다. 의미는 같지만 큐는 자료 구조론에서 사용하는 용어고, 힙은 메모리 관련 용어로 사용한다고 보면 됩니다.
데크(Deque)는 Double Ended QUEue의 줄임말로 스택과 큐의 동작 방식을 복합한 방식입니다. 자료 구조에서 선형구조의 목록을 뜻하는 용어로 목록의 양 쪽 끝에서 삽입과 삭제가 가능한 방식입니다.
데크는 입출입 형태에 따라서 한 쪽을 제한할 수 있습니다. 입력 제한 데크라는 방식은 scroll이라고 하는데, 삽입(input)은 목록의 한 쪽 끝에서 이루어지고, 삭제(출력,output)는 목록의 양 쪽 끝에서 이루어지는 방식입니다. 반대로 출력 제한 데크가 있습니다. 출력 제한 데크는 shelf라고 하는데 삽입은 양 쪽 끝에서 이루어지고, 삭제는 목록의 한 쪽 끝에서 이루어지는 방식을 뜻합니다.
[출처] [본문스크랩] 메모리 영역|작성자 독선생
