[자료구조][배열][스택] c 코드 구현

목차

 

자료구조를 공부하며 스택 구현을 배열로 해 보았다

 

-스택으로 구현할 ADT들-

- push(stack, ‘c’) : stack의 top에 데이터를 추가한다. stack이 이미 꽉 차있으면 해당 데이터
는 스택에 저장하지 않고 “Stack FULL”을 출력한다.

 

- pop (stack) : stack의 top에 있는 데이터를 반환하고 stack에서 제거한다. stack이 비어 있
으면 “Stack Empty”를 출력한다.

 

- peek(stack): stack의 top에 있는 데이터를 화면에 출력한다. stack은 변화하지 않는다. 
stack이 비어 있으면 “Stack Empty”를 출력한다.

 

- duplicate(stack): stack의 top에 있는 데이터를 pop해서 두 번  push 한다. stack이 이미 
꽉 차있으면 “Stack FULL”을 출력한다.

 

- upRotate(stack, n): stack의 맨 위 n 개의 데이터를 회전시킨다. 예를 들면 n 이 3이고 
stack의 top에서부터 elem1, elem2, elem3, .... 이 저장되어 있으면  데이터를 하나씩 위
쪽으로 이동시킨다. 맨 위쪽 (top)의 std1은 n-1번 아래쪽으로 이동해서 스택의 결과는 
elem2, elem3, elem1, ...이된다.
(단, n이 데이터의 개수보다 큰 경우에는 아무 작업을 하지 않는다.)

 

- downRotate(stack, n): stack의 맨 위 n 개의 데이터를 회전시킨다. 예를 들면 n 이 3이고 
stack의 top에서부터 elem1, elem2, elem3, .... 이 저장되어 있으면  데이터를 하나씩 d
아래쪽으로 이동시킨다. top에서부터 n번째의 데이터는 top으로 이동해서, 스택의 결과
는  elem3, elem1, elem2, ...이된다.
(단, n이 데이터의 개수보다 큰 경우에는 아무 작업을 하지 않는다.)

 

- print(stack) : stack의 모든 데이터를 top에서부터 순서대로 공백 없이 출력한다. 

 

코드 구현

// 구조체 선언
typedef struct {
    char data[100];
    int top;
} Stack;

 

// 스택 초기화 함수
void init(Stack* stack) {
    stack->top = -1;
}

 

//비어있는지 확인 하는 함수
int isEmpty(Stack* stack) {
    return stack->top == -1;
}

 

// 스택에 데이터를 추가하는 함수
void push(Stack* stack, char data, int size) {
    if (stack->top == size-1) {
        printf("Stack FULL\n");
        return;
    }
    stack->top++;
    stack->data[stack->top] = data;
    
}

 

// 스택에서 데이터를 제거하고 반환하는 함수
char pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack Empty\n");
        return '\0';
    }
    char del = stack->data[stack->top];
    stack->top--;
    return del;
}

 

// 스택의 모든 데이터를 출력하는 함수
void print(Stack* stack) {
    for (int i = stack->top; i >= 0; i--) {
        printf("%c", stack->data[i]);
    }
    printf("\n");
}

 

//상단 회전 함수
void upRotate(Stack *stack, int n) {
    if (n > stack->top + 1)
        return;
    char save = stack->data[stack->top];
    for (int i = stack->top; i >=stack->top-n+2; i--) {
        stack->data[i] = stack->data[i - 1];
    }
    stack->data[stack->top- n+1] = save;
}

 

//하단 회전 함수
void downRotate(Stack* stack, int n) {
    if (n > stack->top + 1)
        return;
    char save = stack->data[stack->top-n+1];
    for (int i = stack->top-n+1; i <=stack->top-1; i++) {
        stack->data[i] = stack->data[i + 1];
    }
    stack->data[stack->top] = save;
}

 

//복제하는 함수
void duplicate(Stack * stack, int size) {
    if (stack->top == size - 1) {
        printf("Stack FULL\n");
        return;
    }
    char top = stack->data[stack->top];
    pop(stack);
    push(stack, top, size);
    push(stack, top, size);
}