1. 스택(stack)
"스택"이란 여러 개의 데이타 항목들이 일정한 순서로 나열된 자료 구조로 한쪽 끝에서만 새로운 항목을 삽입하거나 기존 항목을 삭제할 수 있도록 고안된 것이다. 스택은 동전을 넣고 뺄 수 있도록 되어 있는 동전 케이스와 같은 작동 원리를 가지고 있다. 삽입된 동전들은 케이스 내부에 일정한 순서로 저장된다. 먼저 삽입된 동전은 케이스의 가장 아래쪽에 위치하고 가장 최근에 삽입된 동전은 입구에 놓인다. 스택에 저장된 데이타 항목들 중에 먼저 삽입된 것은 나중에 삭제되고, 나중에 삽입된 것이 먼저 삭제된다. 그래서 스택을 후입 선출 리스트(Last- In-First-Out List) 라고 부른다. 선입 선출법을 사용하는 큐와는 상반된 성질을 가진다.
＊ 삽입과 삭제는 현재 저장된 최상위 항목이 위치한 top 에서만 일어난다.
＊ top 위치는 "스택 포인터"라는 지시자가 가리킨다.
＊ 스택 포인터는 스택 기저에서 시작하여 항목이 삽입되면 하나 증가하고,
삭제되면 하나 감소한다.
＊ 스택에는 한계가 있어서 그 한계를 초과하도록 삽입할 수 없다.
2. 힙(heap)
heap은 프로그램이 실행될 때까지는 알 수 없는 가변적인 량만큼의 데이터를 저장하기 위해, 프로그램의 프로세스가 사용할 수 있도록 미리 예약되어 있는 메인 메모리의 영역이다. 예를 들면, 하나의 프로그램은 처리를 위해 한 명 이상의 사용자로부터 서로 다른 량의 입력을 받을 수 있으며, 즉시 모든 입력데이터에 대해 처리를 개시한다. 운영체계로부터 이미 확보된 일정량의 heap 저장공간을 가지고 있으면, 저장과 관련된 처리를 좀더 쉽게 할 수 있으며, 일반적으로 필요할 때마다 운영체계에게 매번 저장공간을 요청하는 것보다 빠르다. 프로세스는 필요할 때 heap 블록을 요구하고, 더 이상 필요 없을 때 반환하며, 이따금씩 "자투리모으기"를 수행함으로써 자신에게 할당된 heap을 관리한다. 여기서 자투리모으기란 더 이상 사용되지 않는 블록들을 사용 가능한 상태로 만들고, 또한 heap 내의 사용 가능한 공간을 인지함으로써 사용되지 않은 작은 조각들이 낭비되지 않도록 하는 것을 말한다.
이 용어는 분명히 다른 용어인 스택(stack)의 영향을 받았다. 스택은 블록들이 저장공간으로부터 어떤 순서에 입각하여 꺼내어지고, 또 같은 방법으로 반환된다는 것을 제외하고는 heap과 비슷하다. 파스칼에서는, subheap은 스택처럼 취급되는 heap의 일부분이다.
c언어에서 heap에 메모리를 할당할 때는 memory allocation--> malloc()을 사용한다.
typedef struct { int key; }element;
void run(); void view(); void insert_max_heap(); element delete_max_heap(); element heap[MAX_ELEMENTS]; int n=0;
main() { run(); }
void run() { element arr[5]; int i; printf("Input number of 5:\n"); for(i=0;i<5;i++) { scanf("%d",&arr[i].key); insert_max_heap(arr[i].key,&n); } printf("BEFORE : "); view(); delete_max_heap(&n); printf("AFTER : "); view(); }
void view() { int i; for (i=1; i<=n; i++) { printf("%d ",heap[i].key); } printf("\n"); }
void insert_max_heap(element item,int *n) { int i; if(HEAP_FULL(*n)) { fprintf(stderr,"The heap is full.\n"); exit(1); } i=++(*n); while((i!=1) && (item.key > heap[i/2].key)) { heap[i]=heap[i/2]; i/=2; } heap[i]=item; }
element delete_max_heap(int *n) { int parent,child; element item,temp; if(HEAP_EMPTY(*n)) { fprintf(stderr,"The heap is empty\n"); exit(1); } item = heap[1]; temp = heap[(*n)--]; parent = 1; child = 2;
while(child <= *n) { if ((child<*n)&&(heap[child].key) < heap[child+1].key) child++; if(temp.key>=heap[child].key) break; heap[parent]=heap[child]; parent=child; child*=2; } heap[parent]=temp; return item; }
나의 flickr.
아이뉴스 24.
댓글을 달아 주세요