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

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

 

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

 

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

 

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

// Main function
int main() {    
    list *stack;
 
    // Create new stack
    stack = newStack();
 
    // Add item onto stack
    addItem(stack, 3);
    addItem(stack, 1);
    addItem(stack, 2);
    addItem(stack, 4);
 
    // Look at the top item on the stack
    printf("Top item: %d\n", top(stack));
 
    // Print stack items
    print(stack);
 
    while (!isEmpty(stack)) {
        int n = pop(stack);
        printf("Pop item: %d\n", n);
    }
}

 

 

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

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

 

 

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

// Insert cell in the middle of the stack
void insert(list *stack, cell *c, int n) {
    cell *new = malloc(sizeof(cell));
    *new = (cell) { n, c->next };
    c->next = new;
}

 

 

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

// Find cell on stack
cell *findCell(cell *first, int n) {
    // Return cell if nothing points to the next cell
    if (first->next == NULL) return first;
    
    cell *next = first->next;
    int a = next->item;
 
    // Exit program if item exists
    if (a == n) fail("Item exists");
 
    return n < a ? findCell(next, n) : first;
}

 

 

스택(stack) 내림차순 정렬/삽입 구현

/* Stack - addItem(Push, Insert), Sort(descend), Print, Pop */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
// Structure for individual items
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 *stack = malloc(sizeof(list));
    stack->first = NULL;
    return stack;
}
 
// Push an item onto a stack
void push(list *stack, int n) {
    cell *newCell = malloc(sizeof(cell));
    *newCell = (cell) { n, stack->first };
    stack->first = newCell;
}
 
// Print message and exit program
void fail(char *msg) {
    fprintf(stderr, "%s\n", msg);
    exit(1);
}
 
// Look at the top item of the stack
int top(list *stack) {
    if (stack->first == NULL) fail("Top of empty stack\n");
    return stack->first->item;
}
 
// Check if a stack is empty
bool isEmpty(list *stack) {
    return stack->first == NULL;
}
 
int pop(list *stack) {
    cell *first = stack->first;
    if (first == NULL) fail("Pop from empty stack\n");
    stack->first = first->next;
    int n = first->item;
    free(first);
    return n;
}
 
// Print stack items
void print(list *stack) {
    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");
}
 
// Find cell on stack
cell *findCell(cell *first, int n) {
    // Return cell if nothing points to the next cell
    if (first->next == NULL) return first;
    
    cell *next = first->next;
    int a = next->item;
 
    // Exit program if item exists
    if (a == n) fail("Item exists");
 
    return n < a ? findCell(next, n) : first;
}
 
// Insert cell in the middle of the stack
void insert(list *stack, cell *c, int n) {
    cell *new = malloc(sizeof(cell));
    *new = (cell) { n, c->next };
    c->next = new;
}
 
// Add item onto stack
void addItem(list *stack, int n) {
    if (isEmpty(stack) || stack->first->item < n) {
        push(stack, n);
    } else {
        insert(stack, findCell(stack->first, n), n);
    }
}
 
// Main function
int main() {    
    list *stack;
 
    // Create new stack
    stack = newStack();
 
    // Add item onto stack
    addItem(stack, 3);
    addItem(stack, 1);
    addItem(stack, 2);
    addItem(stack, 4);
 
    // Look at the top item on the stack
    printf("Top item: %d\n", top(stack));
 
    // Print stack items
    print(stack);
 
    while (!isEmpty(stack)) {
        int n = pop(stack);
        printf("Pop item: %d\n", n);
    }
}