최종 수정 : 24.12.29
동적연결 스택과 큐
순차 표현방법은 스택이나 큐가 하나만 있을 때는 효율적이나 여러 개의 스택이나 큐가 동시에 있을 때, 이들을 순차 리스트로 표현하면 비효율적이다. 이것을 연결 리스트로 표현해야 효율적이다. 스택은 tp pointer로 첫 노드를 가리키게 하고, 큐의 경우에는 첫째와 마지막 노드를 각각 front와 rear pointer로 가리킴으로써 삽입&삭제가 가능하도록 할 수 있다.
스택과 큐를 연결 리스트로 만들면 메모리르 좀 더 효율적으로 쓸 수 있고, 1차원 배열로 표현했을 때 발생하는 메모리 한계를 극복할 수 있다.
1. 연결 리스트로 구현된 스택의 노드 추가
스택에서의 노드 추가는 가용 공간이 가득 찼는지 확인 후에 노드를 삽입한다. 순차 표현으로 표현된 스택에서의 원소 삽입은 스택을 생성할 때 할당받은 메모리 공간, 즉, top이 스택의 크기(STACK_SIZE-1)이상일 경우에는 원소를 삽입할 수 없다. 그러나 연결 리스트를 이용하여 구성된 스택에서 노드 추가는 메모리 공간의 여유가 있는지 없는지를 통해 노드 추가 여부를 판단한다. 연결된 스택에서의 노드 추가는 먼저 새 노드인 temp를 생성하여 데이터 필드에는 원소를 삽입하고, 링크 필드에는 top을 넣어준 후, top은 temp를 지시하도록 하여 삽입한다.
2. 연결 리스트로 구현된 스택의 노드 삭제
스택에서 노드 삭제 시에는 top pointer의 값이 NULL인지 아닌지를 판단하여 스택이 빈 유무를 확인한다. NULL 값이 아니라면 스택에 원소가 하나 이상 있는 상태이므로 노드 삭제 연산이 가능하다. 삭제하고자 하는 노드의 링크 부분의 값을 top pointer가 가지게 된다. 기억공간의 효율을 위해 삭제된 노드의 공간을 해제해 준다. 스택에서의 삭제이므로 삭제될 노드의 데이터 부분의 값을 반환한다.
3. 연결 리스트로 구현된 큐의 노드 추가
순차 표현된 큐의 노드 추가는 할당받은 큐 크기를 검사하여 아직 메모리 공간의 여유가 있는지를 판단한 후 추가 연산이 이루어진다. 즉, rear가 큐의 크기(QUEUE_SIZE-1) 이상일 경우에는 원소를 삽입할 수 없다. 그러나 연결 리스트로 구현된 동적 연결 큐의 노드 추가는 가용 공간이 여유가 있는지를 검사하여 노드 추가한다. 추가 연산은 추가하고자 하는 노드의 공간을 할당받고 할당받은 노드의 데이터 필드에 데이터를 저장하고, 링크 필드에 값은 NULL 값으로 한다. 큐가 공백인지 아니면 다른 노드가 존재하는지에 따라 연산을 한다. 만약 공백 큐라면 front pointer와 rear pointer는 모두 새로운 노드 temp를 가리키게 된다. 큐에 원소가 하나 이상 존재한다면 마지막 원소인 rear의 링크 부분은 temp 값을 가지고 rear pointer는 temp를 지시하게 하여 삽입한다.
4. 연결 리스트로 구현된 큐의 노드 삭제
동적 연결된 큐의 노드 삭제는 큐가 비어 있는지 아닌지를 먼저 검사한 후 노드가 존재하면 삭제 연산을 진행한다. 큐의 삭제는 front에서 진행되므로 첫 노드를 삭제하기 위해서 front에 front위 링크(front -> link)를 할당하여 완료된다. 또한, 삭제 노드는 free 함수를 이용하여 메모리 해제한다.
참고
독학사 교재
댓글