[C언어 #60] 연결 리스트 (Linked lists) - 스택 (stack) 구현

c언어 연결리스트 (Linked lists) - 스택 (stack) 구현

 

Stack Operation
스택 작업	간편하고 효율적인 연결 리스트 활용 방식
push	리스트 시작점에 항목 삽입
pop	시작점의 항목 제거
top (peek)	첫번째 항목 보기
isEmpty	항목 유무 확인

 

메인 함수 (main)

int main() {
    list *stack;
    stack = newStack();
    push(stack, 2);
    push(stack, 3);
    push(stack, 5);
    push(stack, 7);
    printf("top %d\n", top(stack));
    while (!isEmpty(stack)) {
        int n = pop(stack);
        printf("%d\n", n);
    }
}

 

 

스택 구조체 (Stack structures) - main 함수에 필요한 구조체 : cell, list

• cell 구조체: 개별 필드 항목을 위한 구조체
• list 구조체: 전체 리스트를 위한 구조체

struct cell {
    int item;
    struct cell *next;
};
 
struct list {
    struct cell *first;
};
 
typedef struct cell cell;
 
typedef struct list list;

 

 

새로운 스택 생성

list *newStack() {
    list *new = malloc(sizeof(list));
    new->first = NULL;
    return new;
}

 

NULL

• 특별한 포인터로 어디도 가리키지 않는다.
• 비어있는 리스트 또는 리스트의 마지막 셀(cell)에 사용
• 프로그램에 속하지 않는 메모리의 일부분으로, 일반적으로 주소(address) 0으로 정의. 따라서 해당 메모리로 향할 경우 segmentation fault로 인한 장애(crash) 발생

 

 

스택의 항목 유무 검사

bool isEmpty(list *stack) {
    return stack->first == NULL;
}

 

 

리스트의 시작점에 항목 삽입

void push(list *stack, int n) {
    cell *newCell = malloc(sizeof(cell));
    *newCell = (cell) { n, stack->first };
    stack->first = newCell;
}

 

 

스택 오류 함수

void fail(char *msg) {
    fprintf(stdeff, "%s\n", msg);
    exit(1);
}

해당 함수는 stderr를 출력하고 프로그램을 에러 코드를 가지고 종료

 

 

리스트의 첫번째 항목 보기

int top(list *stack) {
    if (stack->first == NULL) fail("top of empty stack");
    return stack->first->item;
}

비어있는 스택일 경우 fail함수 호출

 

 

첫번째 항목 제거

int pop(list *stack) {
    cell *first = stack->first;
    if (first == NULL) fail("pop from empty stack");
    stack->first = first->next;
    int n = first->item;
    free(first);
    return n;
}

셀의 값을 변수에 저장한 이후에 리스트에서 제거, 메모리 할당 해제(free)

 

 

스택(stack) 구현

/* Stack */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
struct cell {
    int item;
    struct cell *next;
};
 
struct list {
    struct cell *first;
};
 
typedef struct cell cell;
 
typedef struct list list;
 
// Create a new stack
list *newStack() {
    list *new = malloc(sizeof(list));
    new->first = NULL;
    return new;
}
 
// Push an item onto a stack
void push(list *stack, int n) {
    cell *new = malloc(sizeof(cell));
    *new = (cell) { n, stack->first };
    stack->first = new;
}
 
// Print message and exit if error
void fail(char *message) {
    fprintf(stderr, "%s\n", message);
    exit(1);
}
 
// Look(Peek) at the top item
int top(list *stack) {
    if (stack->first == NULL) fail("Top of empty stack");
    return stack->first->item;
}
 
// Check if a stack is empty
bool isEmpty(list *stack) {
    return stack->first == NULL;
}
 
// Remove the top item
int pop(list *stack) {
    cell *first = stack->first;
    if (first == NULL) fail("Pop from empty stack");
    stack->first = first->next;
    int n = first->item;
    free(first);
    return n;
}
 
int main() {
    list *stack;
    stack = newStack();
    push(stack, 2);
    push(stack, 3);
    push(stack, 5);
    push(stack, 7);
    printf("Top item: %d\n", top(stack));
    while (!isEmpty(stack)) {
        int n = pop(stack);
        printf("Pop: %d\n", n);
    }
}