링크드 리스트를 이용한 스택과 큐

스택 과 큐 링크드 리스트 보고서

스택 링크드리스트

 

우선 스택이란?

LIFO(Last In First Out) 먼저 들어간 것이 나중에 나오는, 나중에 들어간 것이 먼저 나오는 것.

 

삽입(Push)

 

비어있는 리스트에 첫 번째 값을 넣고, 두 번째 값, 세 번째 값을 차례대로 넣는다.

그릇을 쌓아올리듯이 데이터들을 하나씩 쌓아올리는 개념이다.

 

삽입 하는 과정을 보자면

초기화를 하면 Head와 Tail이 연결된다

void Init(){
    head = (node*)(malloc(sizeof(node))); //동적할당
    tail = (node*)(malloc(sizeof(node)));    
    head->prev = head; //헤드와 테일을 연결함
    head->next = tail;
    tail->prev = head;
    tail->next = tail;
}
 

데이터 삽입

void Insert(int data){ //넣은 값을 받아옴
    _node *tmp = (node*)(malloc(sizeof(node))); //동적할당
    tmp->data = data //값복사
    tmp->next = tail; //tmp뒤에 tail을 넣음
    tmp->prev = tail->prev; //tmp앞에 tail의 앞에것을 넣음    
    tail->prev->next = tmp; //tail의 앞에것에 뒤에것은 tmp로 바꾸어줌
    tail->prev = tmp; //tail의 앞은 tmp로 바꿈
    //tmp를 만들어서 맨뒤에 넣음
}
 

 

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

삭제(Pop)

pop은 스택에 맨위, 즉 마지막에 들어간(최근에 들어간)값을 리스트에서 제거한다.

void pop_Stack(){
    _node *tmp;
    tmp = tail->prev; //맨뒤부터 시작
    if(tmp != head){ //head가 아니면
        tmp->next->prev=tmp->prev; //연결 고리를 끊고
        tmp->prev->next=tmp->next; //tmp앞에있는것과 tmp뒤에있는것을 연결해줌
        free(tmp);//제거
    }
    printf("팝 스택\n");
}

삭제하는 과정은 Tail의 앞에있는 노드를 선택해

선택한 노드와 연결된 1과 Tail의 연결을 끊고 1과 Tail을 이어준다

 

 

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

2. 큐 링크드 리스트

우선 큐란?

FIFO(First In First Out) 먼저 들어간 것이 먼저나오는

줄서기와 같은 개념이라고 볼 수 있다.

 

삭제(Pop)

Queue는 리스트에 맨밑, 즉 처음에 들어간(제일 오래된)값을 리스트에서 제거한다.

 

void pop_Queue(){
    _node *tmp;
    tmp = head->next; //맨앞부터 시작
    if(tmp != tail){ //꼬리가 아니면
        tmp->next->prev=tmp->prev; //연결고리를 끊고
        tmp->prev->next=tmp->next; //앞뒤를 연결해준후
    free(tmp); //제거
    }
    printf("큐 스택\n");
}

삭제하는 과정은 Head의 다음에 있는 것을 선택해

선택된것과 연결된 Head와 2의 연결을 끊고 Head와 2를 연결해준다

3. 배열로 만들어진 큐,스택 과 링크드리스트로 만들어진 큐,스택의 차이점

배열로 만들어진 큐,스택은 연속적으로 이어져있고, 동적할당이 불가능하나

그러나 링크드리스트는 메모리가 서로 떨어져있고, 링크를 통해 이어지며 동적할당이 편리하다.