[연결리스트] 연결리스트 응용 - 스택, 큐 구현 (C언어)

[연결리스트] 연결리스트 응용 - 스택, 큐 구현 (C언어)

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

[스택]

간단히 말하자면

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

insert_first, delete_first !!

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

#include #include 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

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

"); 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

", pop(&s;)); print_stack(&s;); }

10, 20, 30 을 push하고

pop을 해서 30을 꺼냈다

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

출력 결과

[큐]

큐 구현을 해보자~

#include #include 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("

"); } element dequeue(LinkedQueueType* q) { QueueNode* temp = q->front; //underflow check if (is_empty(q)) { fprintf(stderr, "Queue is empty

"); 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

", dequeue(&q;)); print_queue(&q;); }

출력 결과

앗사라비용,,~

재미있는 자료구조

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

from http://sxyzn.tistory.com/15 by ccl(A) rewrite - 2021-08-15 02:26:38