[C언어 #62] 연결 리스트 (Linked lists) - 스택 (stack) 구현 - 오름차순 정렬/삽입

c언어 연결 리스트 (Linked lists) - 스택 (stack) 구현 - 오름차순 정렬/삽입

 

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

 

스택에 아이템을 추가할 때 오름차순으로 정렬하여 삽입하기

 

main 함수에 조건에 따라 item을 추가(push), 삽입(insert) 하는 addItem 함수 구현

int main() {
    list *stack;
    stack = newStack();
 
    addItem(stack, 4);
    addItem(stack, 2);    
    addItem(stack, 1);
    addItem(stack, 3);
    addItem(stack, 7);
    addItem(stack, 5);
    addItem(stack, 6);
 
    printf("Top item: %d\n", top(stack));
    
    print(stack);
 
    while (!isEmpty(stack)) {
        int n = pop(stack);
        printf("Pop item: %d\n", n);
    }
}

 

 

조건에 따라 item을 추가(push), 삽입(insert) 하는 addItem 함수 구현

void addItem(list *stack, int n) {
    if (isEmpty(stack) || stack->first->item > n) {
        push(stack, n);
    } else {
        insert(stack, findCell(stack->first, n), n);
    }
}

 

 

삽입하기 위한 위치를 찾아 오름차순(ascending)으로 정렬 하여 item 삽입 함수 구현

void insert(list *stack, cell *c, int n) {
    cell *new = malloc(sizeof(cell));
    *new = (cell) { n, c->next };
    c->next = new;
}

 

 

오름차순 정렬을 위하여 cell 위치 찾는 findCell 함수 구현

cell *findCell(cell *first, int n) {
    if (first->next == NULL) return first;
    cell *c = first->next;
    int a = c->item;
    if (a == n) fail("Item Exists");
    return n > a ? findCell(c, n) : first;
}

 

 

스택(stack) 오름차순 정렬/삽입 구현

/* Stack - addItem(Push, Insert), Sort(ascend), Print, Pop */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
// Structure for individual cells
struct cell {
    int item;
    struct cell *next;
};
 
// Structure for the list as a whole
struct list {
    struct cell *first;
};
 
// typedef for structures
typedef struct cell cell;
typedef struct list list;
 
// Create new stack
list *newStack() {
    list *new = malloc(sizeof(list));
   new->first = NULL;
    return new;
}
 
// Push an item onto stack
void push(list *stack, int n) {
   cell *new = malloc(sizeof(cell));
    *new = (cell) { n, stack->first };
    stack->first = new;
}
 
// Print message and exit program
void fail(char *msg) {
    fprintf(stderr, "%s\n", msg);
    exit(1);
}
 
// Look at top item of stack
int top(list *stack) {
    if (stack->first == NULL) fail("Top of empty stack");
    return stack->first->item;
}
 
// Check if stack is empty
bool isEmpty(list *stack) {    
    return stack->first == NULL;
}
 
// Remove first item from stack
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;
}
 
cell *findCell(cell *first, int n) {
    if (first->next == NULL) return first;
    cell *c = first->next;
    int a = c->item;
    if (a == n) fail("Item Exists");
    return n > a ? findCell(c, n) : first;
}
 
void insert(list *stack, cell *c, int n) {
    cell *new = malloc(sizeof(cell));
    *new = (cell) { n, c->next };
    c->next = new;
}
 
// Print stack items
void print(list *s) {
    list *stack = s;
    if (stack->first == NULL) fail("Print empty stack");
    printf("{ ");
    cell *first = stack->first;
    while(first != NULL) {
        printf("%d", first->item);
        if (first->next != NULL) printf(", ");
        first = first->next;
    }
    printf(" }\n");
}
 
void addItem(list *stack, int n) {
    if (isEmpty(stack) || stack->first->item > n) {
        push(stack, n);
    } else {
        insert(stack, findCell(stack->first, n), n);
    }
}
 
int main() {
    list *stack;
    stack = newStack();
 
    addItem(stack, 4);
    addItem(stack, 2);    
    addItem(stack, 1);
    addItem(stack, 3);
    addItem(stack, 7);
    addItem(stack, 5);
    addItem(stack, 6);
 
    printf("Top item: %d\n", top(stack));
    
    print(stack);
 
    while (!isEmpty(stack)) {
        int n = pop(stack);
        printf("Pop item: %d\n", n);
    }
}