queue, stack, heap 메모리

queue : 큐

큐는 사람들이나 물건들이 처리를 기다리며 서있는 줄을 말하는데, 줄의 맨 앞에서부터 순서대로 처리된다. 컴퓨터 프로그래밍에서의 큐는 데이터가 들어간 순서대로 제거되는 자료구조를 말한다. 이러한 순서를 가리켜 흔히, 선입선출(FIFO ; First In First Out)이라고 한다. 이와는 반대로 스택이라는 자료구조는 먼저 들어간 데이터가 가장 나중에 제거되는 형식인데, 이것을 LIFO (Last In Frist Out)라 한다.

stack : 스택

프로그래밍에서, 스택이란 처리해야할 요청을 저장하는 데이터 저장소 또는 버퍼이다. IBM의 컴퓨터 사전에 보면, 스택은 항상 푸시다운(LIFO : Last In Frist Out) 목록이라고 나와있는데, 이는 새로운 요청이 들어오면 그것은 이전의 것을 밑으로 눌러 내린다는 의미이다. 스택을 바라다 보는 또다른 방법은, 처리할 항목을 항상 스택의 최상위로부터 가져오는 프로그램이라고 이해하는 것이다 (이것은 먼저 도착한 것을 먼저 처리하는 "FIFO"와는 아주 다른 방법이다).

heap : 힙

C나 파스칼 등을 포함한 몇몇 프로그래밍 언어에서, heap은 프로그램이 실행될 때까지는 알 수 없는 가변적인 량만큼의 데이터를 저장하기 위해, 프로그램의 프로세스가 사용할 수 있도록 미리 예약되어 있는 메인 메모리의 영역이다. 예를 들면, 하나의 프로그램은 처리를 위해 한 명 이상의 사용자로부터 서로 다른 량의 입력을 받을 수 있으며, 즉시 모든 입력데이터에 대해 처리를 개시한다. 운영체계로부터 이미 확보된 일정량의 heap 저장공간을 가지고 있으면, 저장과 관련된 처리를 좀더 쉽게 할 수 있으며, 일반적으로 필요할 때마다 운영체계에게 매번 저장공간을 요청하는 것보다 빠르다. 프로세스는 필요할 때 heap 블록을 요구하고, 더 이상 필요 없을 때 반환하며, 이따금씩 "자투리모으기"를 수행함으로써 자신에게 할당된 heap을 관리한다. 여기서 자투리모으기란 더 이상 사용되지 않는 블록들을 사용 가능한 상태로 만들고, 또한 heap 내의 사용 가능한 공간을 인지함으로써 사용되지 않은 작은 조각들이 낭비되지 않도록 하는 것을 말한다.

이 용어는 분명히 다른 용어인 스택(stack)의 영향을 받았다. 스택은 블록들이 저장공간으로부터 어떤 순서에 입각하여 꺼내어지고, 또 같은 방법으로 반환된다는 것을 제외하고는 heap과 비슷하다. 파스칼에서는, subheap은 스택처럼 취급되는 heap의 일부분이다.