자료구조 - 스택

컴공거북이·2025년 5월 8일

자료구조

목록 보기

6/6

스택이란?

가장 마지막에 추가된 데이터를 가장 먼저 내어주는 자료구조
즉, 후입선출(Last-In First-Out, LIFO) 원칙을 따름

⭐️ 스택의 주요 특징

삽입과 삭제는 항상 top(맨 위) 에서 이루어짐
ex: 워드의 '되돌리기' 기능
→ 가장 마지막에 한 작업부터 거꾸로 하나씩 취소

< 예제 풀어보기 (9주차-1번) >

⭐️ 의사코드 -> c언어 코드가 되는 과정에 집중

초기 전제

int t, N; //전역변수
// t는 top의 위치를 의미
// N은 스택의 size를 의미

< 스택 초기화 >

//1. 스택 초기화
t = -1;

< 스택 PUSH(삽입) >

void push(char *stack, char c){
    // 1. 스택이 가득 찼는지 확인
    if(t == N-1){
        printf("Stack FULL\n");
        return;
    }
    // 2. top 한 칸 올리기
    t = t+1;
    // 3. top 위치에 원소 추가
    stack[t] = c;
    // 4. 함수 종료
    return;
}

< 스택 POP(삭제) >

char pop(char *stack){
    //1. 스택이 비었는 지 확인
    if(t <= -1){
        return printf("Stack Empty\n");
    }
    //2. top 한 칸 내리기
    t = t-1;
    //3. 기존의 top 원소 반환
    return stack[t+1];
}

< 스택 Peek(top 원소 반환) >

char peek(char *stack){
    //1. 스택이 비었는 지 확인
    if(t <= -1){
        return printf("Stack Empty\n");
    }
    //2. top 원소 반환
    return stack[t];
}

< 스택 DUPLICATE >

//top 원소를 꺼내서 두 번 다시 넣기

void duplicate(char *stack){
    //1. 스택 크기 확인
    if(t >= N-2){
        printf("Stack FULL\n");
        return;
    }
    //2. top에 있는 원소 삭제
    char c = pop(stack);
    //3. 삭제한 원소 2번 삽입
    push(stack,c);
    push(stack,c);
    // 4. 함수 종료
    return;
}

< 스택 upRotate >

//stack의 맨 위 n개의 원소를 위쪽으로 회전

void upRotate(char *stack, int n) {
    //1. 스택 사이즈 구하기
    int stackSize = t+1;
    //2. 회전할 원소의 개수가 스택의 크기보다 큰 지 확인
    if (stackSize < n) return;
    //3. top의 원소 임시 저장 
    char tmp = stack[t];
    //4. 맨 위 n개의 원소를 한 칸씩 위로 이동
    for (int i=0; i<n-1; i++) {
        stack[t-i] = stack[t-i-1];
    }
    //5. 원래 top이였던 값을 top의 n번째 아래에 넣기
    stack[t-(n-1)] = tmp;
    //6. 함수 종료
    return;
}

< 스택 downRotate >

//stack의 맨 위 n개의 원소를 아래쪽으로 회전

void downRotate(char *stack, int n) {
    //1. 스택 사이즈 구하기
    int stackSize = t+1;
    //2. 회전할 원소의 개수가 스택의 크기보다 큰 지 확인
    if (stackSize < n) return;
    //3. top의 n번째 아래에 있는 값 임시 저장
    char tmp = stack[t-(n-1)];
    //4. 맨 위 n개의 원소를 한 칸씩 아래로 이동
    for (int i = n-1; i >0; i--) {
        stack[t-i] = stack[t-i+1];
    }
    //5. 원래 top의 n번째 아래에 있던 값을 맨 위에 넣기
    stack[t] = tmp;
    //6. 함수 종료
    return;
}