[C언어로 쉽게 풀어쓴 자료구조] Chapter7. 연결 리스트 II (2)

7.5 연결 리스트로 구현한 스택

● 연결된 스택(linked stack) : 연결리스트를 이용한 스택

- 크기가 제한되지 않은 채 동적 메모리 할당을 통해 새로운 요소를 삽입할 수 있다.

- 동적 메모리 할당 및 해제에 소요되는 시간으로 인해 삽입과 삭제 시 소요 시간은 늘어난다.

- top 변수를 가장 최근에 삽입된 데이터를 나타내는 정수가 아닌, 노드를 가리키는 포인터로 선언

typedef int element;
typedef struct StackNode{
	element data;
	struct StackNode* link;
}StackNode;

typedef struct{
	StackNode *top;
}LinkedStackType;

각 노드는 data 필드와 다음 노드를 가리키는 링크 필드로 이루어지고,

LinkedStackType은 연결된 스택 구조체로 top이 스택 최상단 노드를 가리키는 포인터를 나타낸다.

void init(LinkedStackType *s){
	s->top = NULL;
}

int is_empty(LinkedStackType *s){
	return (s->top == NULL);
}

void push(LinkedStackType *s,element item){
	StackNode *temp = (StackNode*)malloc(sizeof(StackNode));
	temp->data = item;
	temp->link = s->top;
	s->top = temp;
}

void print_stack(LinkedStackType *s){
	for(StackNode *p = s->top; p!=NULL; p= p->link){
		printf("%d-> ",p->data);
	}
	printf("NULL\n");
}

element pop(LinkedStackType *s){
	if(is_empty(s)){
		fprintf(stderr,"스택 빔\n");
		exit(1);
	}
	else{
		StackNode *temp = s->top;
		int data = temp ->data;
		s->top = temp->link;
		free(temp);
		return data;
	}
}

int main(void){
	LinkedStackType *s=(LinkedStackType*)malloc(sizeof(LinkedStackType));
	init(s);
	push(s,1);
	print_stack(s);
	push(s,2);
	print_stack(s);
	push(s,3);
	print_stack(s);
	pop(s);
	print_stack(s);
	pop(s);
	print_stack(s);
	pop(s);
	print_stack(s);
	return 0;
	
}

♣ 243p Quiz

01 크기에 제한 없이 동적으로 할당하여 삽입할 수 있다.

02 스택의 최상단 노드를 가리키는 포인터

 

7.6 연결 리스트로 구현한 큐

● 연결된 큐(linkd queue) : 연결리스트를 이용한 큐

- 크기가 제한되지 않은 채 동적 메모리 할당을 통해 새로운 요소를 삽입할 수 있다.

- 코드가 복잡해지고 링크 필드 때문에 메모리 공간을 더 많이 사용한다.

- 단순 연결 리스트에 삭제와 관련된 front 포인터, 삽입과 관련된 rear 포인터를 추가한다.

- front는 연결 리스트의 맨 앞 요소를, rear는 연결 리스트의 맨 뒤 요소를 가리킨다.

- 큐에 요소가 없을 경우 front와 rear는 NULL값이 된다.

typedef int element;
typedef struct StackNode{
	element data;
	struct StackNode* link;
}QueueNode;

typedef struct{
	QueueNode *front, *rear;
}LinkedQueueType;

void init(LinkedQueueType *q){
	q->front = q->rear = NULL;
}

int is_empty(LinkedQueueType *q){
	return (q->front == NULL);
}

void enqueue(LinkedQueueType *q,element item){
	QueueNode *temp = (QueueNode*)malloc(sizeof(QueueNode));
	temp->data= item;
	temp->link= NULL;
	if(is_empty(q)){
		q->front = temp;
		q->rear= temp;
	}
	else{
		q->rear->link = temp;
		q->rear = temp;
	}
}

element dequeue(LinkedQueueType *q){
	QueueNode *temp = q->front;
	element data;
	if(is_empty(q)){
		fprintf(stderr,"큐 빔\n");
		exit(1);
	}
	else{
		data = temp->data;
		q->front = q->front->link;
		if(q->front ==NULL){
			q->rear = NULL;
		}
		free(temp);
		return data;
	}
}

void print_queue(LinkedQueueType *q){
	for(QueueNode *p = q->front; p!=NULL; p = p->link){
		printf("%d-> ",p->data);
	}
	printf("NULL\n");
}

int main(void){
	LinkedQueueType *q=(LinkedQueueType*)malloc(sizeof(LinkedQueueType));
	init(q);
	
	enqueue(q,1);
	print_queue(q);
	enqueue(q,2);
	print_queue(q);
	enqueue(q,3);
	print_queue(q);
	dequeue(q);
	print_queue(q);
	dequeue(q);
	print_queue(q);
	dequeue(q);
	print_queue(q);
	
	return 0;
	
}

 

♣ 249p Quiz

01 b c d

02 NULL