[자료구조] 리스트로 된 큐

main.c

#include <stdio.h>

#include "q.h"

int main(){

struct data q;

init(&q);

enqueue(&q, 1);

enqueue(&q, 2);

enqueue(&q, 3);

enqueue(&q, 4);

while (!empty(&q)){

printf("%d ", dequeue(&q));

}

return 0;

}

q.c

#include <stdio.h>

#include <stdlib.h>

#include "q.h"

void init(struct data *a){

a->front = NULL;  // front와 rear은 NULL로 초기화 해준다.

a->rear = NULL;

}

void enqueue(struct data *a, int num){

struct data *newnode = (struct data *)malloc(sizeof(struct data));  // 새롭게 동적할당한다.

newnode->next = NULL;  // 새로운 노드는 null을 가리킴

newnode->num = num;  // 새로운 노드에 값 입력

if (empty(a)){  // 이 노드가 처음이라면

a->front = newnode;  // front와 rear은 newnode를 가리킨다.

a->rear = newnode;

}

else{  // 처음 이후라면

a->rear->next = newnode; // a->rear과 newnode1은 같다. newnode1->next에 newnode2를 저장한다.

a->rear = newnode;  // newnode1이 있던 rear에 newnode2가 덮어쓴다.

}

}

int dequeue(struct data *a){

struct data *del;  // 삭제할 노드 위치 나타냄

int i;

if (empty(a)){  // front가 NULL 이라면 나감

exit(-1);

}

del = a->front;  // 현재 front 위치저장

i = a->front->num;  // front의 값 i 저장

a->front = a->front->next;  // front의 위치를 다음으로 덮어쓰기

free(del);  // 덮어쓰기 전 front의 위치를 해제해줌

return i;  // 덮어쓰기 전 front의 값 돌려줌

}

int empty(struct data *a){

if (a->front == NULL){  // a->front가 NULL 이라는 뜻은 큐가 비어있다는 뜻

return 1;

}

else{

return 0;

}

}

int peek(struct data *a){

if (empty(a)){

exit(-1);

}

return a->front->num;

}

q.h

struct data{

struct data *next;

struct data *front;

struct data *rear;

int num;

};

void init(struct data *a);

void enqueue(struct data *a, int num);

int dequeue(struct data *a);

int empty(struct data *a);

int peek(struct data *a);

[q]

front = NULL  --  &malloc1  --  &malloc1  --  &malloc1

rear = NULL  --  &malloc1  --  &malloc2  --  &malloc3

               

                   [malloc1]       [malloc2]      [malloc3]

                    num = 1         num = 2         num = 3

               next = &malloc2  next = &malloc3    next = NULL 

                        l                  l                l

                   [newnode]     [newnode]    [newnode]

                     &malloc1        &malloc2       &malloc3

enqueue일때

newnode->next = NULL;  // malloc1에 null을 넣는다. 

newnode->num = num;  //  malloc1 num에 1을 넣는다.

if (empty(a)){  // 처음 1번 실행

a->front = newnode;  // front에 &malooc1

a->rear = newnode;  // rear에 &malloc1

}

else{  

a->rear->next = newnode; // q의 rear이 &malloc1이므로 malloc1에 들어가서 next에 &malloc2를 넣음

a->rear = newnode;  // &malloc1이 있던 q의 rear에 &malloc2로 바꿈

}

결론적으로 rear이 하나씩 이동하면서 malloc을 가리키게 된다.

바로 전에 있던 malloc의 next를 지금의 malloc으로 바꿔주는 이유는 front가 malloc1부터 시작하니 next로 접근하면서 출력하기 위해서

dequeue일때

del = a->front;  // &malloc1부터 지워나간다

i = a->front->num;  // malloc1의 num인 1을 먼저 i에 넣음

a->front = a->front->next;  // q의 front인 &malloc2를 &malloc1에 덮어쓴다.

free(del);  // &malloc1을 해제한다.

return i;  //  1을 반환한다.

출력은 rear이 다 만들어놓은 길을 front로 처음부터 따라가면 된다.

스택하고 다른점은 단 1가지다. malloc의 next가 앞을 가리키고 있냐 뒤를 가리키고 있냐이다.

나머지 방식은 똑같다.

--------------------------------------------------------------------------------------------------------------

2017.01.03

#include <stdio.h>

#include <stdlib.h>

struct data{

int num;

struct data *front;

struct data *rear;

struct data *next;

};

void init(struct data *a){

a->front = NULL;

a->rear = NULL;

}

int empty(struct data * a){

if(a->front == NULL){

return 0;

}else{

return 1;

}

}

int pop(struct data *a){

struct data *del;

int i;

del = a->front;

i = a->front->num;

a->front = a->front->next;

free(del);

return i;

}

void push(struct data *a, int num){

struct data *newnode = (struct data *)malloc(sizeof(struct data));

newnode->next = NULL;

newnode->num = num;

if(!empty(a)){

a->front = newnode;

a->rear = newnode;

}else{

a->rear->next = newnode;

a->rear = newnode;

}

}

int main(){

struct data node;

init(&node);

push(&node, 1);

push(&node, 2);

push(&node, 3);

while(empty(&node)){

printf("%d ", pop(&node));

}

return 0;

}

큐에서 front는 처음 위치를 저장하고 있고 rear는 마지막 위치를 저장한다.

입력할때 rear가 위치를 이동하며 입력함. (정확히 rear와 newnode의 next)

출력할때 front가 위치를 이동하며 출력함. (정확히 front와 newnode의 next)

newnode는 num과 next만 사용한다.

num은 값이고 next는 front의 다음 위치이다.

node는 추가될때마다 rear만 사용한다.