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

1. 연결 리스트 스택

1.1. 연결된 스택 구조

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

1.2. 연산

init, is_empty, is_full,
push, pop

1.3. 장점

크기가 제한되지 않는다.

1.4. 단점

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

1.5. 연결 리스트 스택 연산

초기화 함수
- 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;

1.6. 연결 리스트 스택 구현


      
      
      
    
    
      <code />
    
#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;
}

<출력>


      
      
      
    
    
      <code />
    
1->NULL
2->1->NULL
3->2->1->NULL
4->3->2->1->NULL
3->2->1->NULL
2->1->NULL
1->NULL

2. 연결리스트 큐

2.1. 연결된 큐 구조

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

2.2. 연결 리스트 큐 연산

초기화 함수
- 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;

2.3. 연결리스트 큐 구현


      
      
      
    
    
      <code />
    
#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;
}

<출력>


      
      
      
    
    
      <code />
    
1->NULL
1->2->NULL
1->2->3->NULL
2->3->NULL
3->NULL
NULL

저작자표시 변경금지

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

Today :

1. 연결 리스트 스택

1.1. 연결된 스택 구조

1.2. 연산

1.3. 장점

1.4. 단점

1.5. 연결 리스트 스택 연산

1.6. 연결 리스트 스택 구현

2. 연결리스트 큐

2.1. 연결된 큐 구조

2.2. 연결 리스트 큐 연산

2.3. 연결리스트 큐 구현

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

검색 태그

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역