[C] 연결리스트 : 스택, 큐

연결리스트로 큐와 스택을 구현해보자

 

[스택]

간단히 말하자면

연결리스트의 맨 앞에 삽입하고 맨 뒤만 삭제하면 된다.

insert_first, delete_first !!

 

단순연결리스트에서도 구현했었다~

 

#include<stdio.h>
#include<stdlib.h>

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

//top은 정수가 아니고 노드를 가리키는 포인터이다
typedef struct {
	StackNode* top;
}LinkedStackType;

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

//insert_first!
void push(LinkedStackType* s, element data) {
	StackNode* tmp = (StackNode*)malloc(sizeof(StackNode));
	tmp->data = data;
	tmp->link = s->top;
	s->top = tmp;
}

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

//동적할당일때 오버플로우는 걱정하지 않아도 되지만
//언더플로우는 고려해야한다.
int is_empty(LinkedStackType* s) {
	return s->top == NULL;
}

element pop(LinkedStackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "stack is empty\n");
		exit(1); //stdlib
	}
	else {
		StackNode* tmp = s->top; //top의 주소 보관
		element data = s->top->data; // tmp->data; 라고 해도 된다.
		s->top = s->top->link; // pop된 리스트 주소 넘겨받음
		free(tmp);
		return data; //pop된 값 return
	}
}

int main() {
	LinkedStackType s;
	init(&s);
	push(&s, 10);
	push(&s, 20);
	push(&s, 30);
	print_stack(&s);
	printf("pop value=%d\n", pop(&s));
	print_stack(&s);
}

10, 20, 30 을 push하고

pop을 해서 30을 꺼냈다

그리고 10, 20이 남은 상태!

출력 결과

---

[큐]

 

큐 구현을 해보자~

#include<stdio.h>
#include<stdlib.h>

typedef int element;
typedef struct QueueNode {
	element data;
	struct QueueNode* 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 data) {
	QueueNode* temp = (QueueNode*)malloc(sizeof(QueueNode));
	temp->data = data;
	temp->link = NULL;
	if (is_empty(q)) { //큐가 비어있을 때
		q->front = temp;
		q->rear = temp;
	}
	else {
		q->rear->link = temp; //큐가 차있으면 마지막 노드를 새 노드로!
		q->rear = temp;
	}
}

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

element dequeue(LinkedQueueType* q) {
	QueueNode* temp = q->front;
	//underflow check
	if (is_empty(q)) {
		fprintf(stderr, "Queue is empty\n");
		exit(1); //stdlib
	}
	else {
		element data = temp->data;
		q->front = q->front->link;
		if (q->front == NULL) { //data 하나 있었는데 삭제한 경우
			q->rear = NULL;
		}
		free(temp);
		return data;
	}
}

int main() {
	LinkedQueueType q; //구조체 변수
	init(&q);
	enqueue(&q, 10);
	enqueue(&q, 20);
	enqueue(&q, 30);
	//10
	//10 20
	//10 20 30 순으로 enqueue됨

	print_queue(&q);

	//맨 앞 10 dequeue
	printf("%d\n", dequeue(&q));

	print_queue(&q);
}

출력 결과

 

앗사라비용,,~

재미있는 자료구조

 

 

 

[참고자료] C언어로 쉽게 풀어 쓴 자료구조, 생능출판, 천인국 공용해 하상호 지음