[자료구조] 연결리스트로 스택과 큐 구현하고 분석하기(C언어)

---

연결 리스트 스택

---

연결된 스택 구조

• 노드 = 데이터 필드 + 링크 필드
• 포인터 : top

 

---

연산

• init, is_empty, is_full,
• push, pop

 

---

장점

• 크기가 제한되지 않는다.

 

---

단점

• 동적 메모리 할당이나 해제함
  → 삽입이나 삭제 시간이 좀 더 걸림

---

연결 리스트 스택 연산

• 초기화 함수
  • top 포인터 값을 NULL로 한다.
    
    
• is_empty
  • top 포인터 값이 NULL(true) → 공백(true)
  • top 포인터 값이 false → 적어도 한 개의 노드가 있음
    
    
• is_full
  • 동적 메모리 할당받아 새 노드를 사용하므로 힙 공간의 크기만큼 사용 가능
    → 많은 메모리 공간 사용 가능 → 포화상태 안됨(false)
    
    

• push(삽입연산) 

  

  • 먼저 동적 메모리 할당으로 새 노드를
    만들고 데이터를 넣는다.
    • temp → data = item;
    • temp → link = s→ top;
      
      
  • 이 새 노드를 첫 번째 노드로 삽입
    • s → top = temp;
      
      

• pop(삭제 연산)

• temp라는 임시 노드에 top 노드를 할당하고 데이터 값을 저장해둔다.
  • element data = temp → data;
    
    
• top 포인터를 첫 번째 노드에서 두 번째 노드로 바꾼다.
  • s → top = temp → link;

 

---

연결 리스트 스택 구현

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

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

typedef struct{
    StackNode *top;
} LinkedStackType;

//초기화 함수
void init(LinkedStackType* s){
    s->top = NULL;
}

// 공백 상태 검출 함수
int is_empty(LinkedStackType *s){
    return (s->top == NULL);
}

// 포화 상태 검출 함수
int is_full(LinkedStackType *s){
    return 0;
}

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

//삭제 함수
element pop(LinkedStackType *s){
    if(s->top == NULL){
        fprintf(stderr,"스택이 비어있습니다\n");
        exit(1);
    }
    StackNode *temp = s->top;
    element data = temp -> data;
    s -> top = temp -> link;
    free(temp);
    return data;
}

//피크함수
element peek(LinkedStackType *s){
    if(is_empty(s)){
        printf("스택이 비었습니다");
        exit(1);
    }
    else return s->top->data;
}

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

int main(){
    LinkedStackType s;
    init(&s);
    push(&s,1); print_stack(&s);
    push(&s,2); print_stack(&s);
    push(&s,3); print_stack(&s);
    push(&s,4); print_stack(&s);
    pop(&s); print_stack(&s);
    pop(&s); print_stack(&s);
    pop(&s); print_stack(&s);
    return 0;
}

<출력>

1->NULL
2->1->NULL
3->2->1->NULL
4->3->2->1->NULL
3->2->1->NULL
2->1->NULL
1->NULL

 

 

---

연결리스트 큐

---

연결된 큐 구조

• 노드 = 데이터 필드 + 링크 필드
• 포인터 : front, rear

 

---

연결 리스트 큐 연산

• 초기화 함수
  • front와 rear 포인터 값을 NULL로 한다.
    
    
• is_empty
  • front == rear == NULL 이면 공백(true)
  • false면 적어도 한 개의 노드가 있다는 것을 나타냄
    
    
• is_full
  • 연결 리스트 스택의 포화 상태와 같음
    
    
• • 연결 리스트가 공백 상태일 경우
    enqueue(삽입 함수)

  

  공백 상태에서 추가

  
  
  1. 첫 노드(front)를 새로 추가된 노드(temp)로 설정
     • q → front = temp;
       
       
  2. 마지막 노드(rear)를 새로 추가된 노드(temp)로 설정
     • q → rear = temp;
       
       
  • 연결 리스트가 공백 상태가 아닐 경우
    1. 마지막 노드(rear)의 링크를 NULL에서 추가된 새로 추가된 노드(temp)로 변경
       • q → rear → link = temp;
         
         
    2. rear을 새로 추가된 노드(temp)로 변경
       • q → rear = temp;

 

• dequeue(삭제 함수)
  • 연결 리스트 노드가 1개일 때
    

    

    
     
    1. 더 이상 남은 노드가 없기 때문에 front가 NULL을 가리켜야 함
       • q → front = q→front→link;
         • front 노드의 다음 노드가 결국엔 NULL임
           
           
    2. 위와 같은 이유로 rear도 NULL을 가리켜야 함
       • q → rear = NULL;
         
         
  • 연결 리스트 노드가 여러개일 때
    

    

    
    
    
    1. front가 첫 노드가 아닌 front의 다음 노드를 가리키게 해서 첫 노드를 바꿈
       • q → front = q → front → link;

 

---

연결리스트 큐 구현

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

typedef int element;

// 노드 구조체
typedef struct QueueNode{
    element data;
    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);
}
// 포화상태 검사
int is_full(LinkedQueueType *q){
    return 0;
}
// 삽입 함수
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;
    }
}
// 삭제 함수
element dequeue(LinkedQueueType *q){
    QueueNode *temp = q ->front;
    element data;
    if(is_empty(q)){
        fprintf(stderr,"큐가 비었음");
        exit(1);
    }
    data = temp ->data;
    q -> front = q -> front -> link;
    if(q->front == NULL) q->rear = NULL;
    free(temp);
    return data;
}

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

int main(){
    LinkedQueueType queue;
    init(&queue);

    enqueue(&queue,1); print_queue(&queue);
    enqueue(&queue,2); print_queue(&queue);
    enqueue(&queue,3); print_queue(&queue);
    dequeue(&queue); print_queue(&queue);
    dequeue(&queue); print_queue(&queue);
    dequeue(&queue); print_queue(&queue);
    return 0;
}

 

<출력>

1->NULL
1->2->NULL
1->2->3->NULL
2->3->NULL
3->NULL
NULL