Stack 알아보기

[C언어]

스택(Stack)

후입선출(Last In, First Out / LIFO) 원칙을 따르는 자료 구조

삽입과 삭제는 top이라 부르는 한쪽 끝에서만 이루어짐

마지막에 삽입된 요소가 가장 먼저 삭제!

---🐢

System Stack

함수 호출 시 실행 흐름과 관련된 정보와 데이터 저장을 위해 스택 프레임(stack frame)을 사용

함수가 호출될 때마다 새로운 스택 프레임이 생성

함수 종료 시 해당 스택 프레임 삭제

 

스택 프레임 구성 요소

- 리턴 주소(return address)

- 지역 변수(local variables)

- 프레임 포인터(previous frame pointer); 이전 스택 프레임의 시작 주소 가리킴

 

스택 프레임 동작 과정

1. 함수 호출

새로운 함수가 호출되면, 스택 프레임이 생성되어 system stack의 top에 위치

2. 함수 실행

함수가 실행되는 동안 지역 변수와 매개변수 등을 스택 프레임을 통해 참조

3. 함수 종료

함수가 종료되면 스택 프레임 제거되면서, 리턴 주소로 돌아가 이전 호출 지점으로 복원

--🐢-

스택 연산

Push()

스택에 element를 추가하는 함수

void Push(Stack* stack, int value) {
    if (IsFull(stack)) {
        printf("Stack overflow! Unable to push %d\n", value);
    } else {
        stack->data[++stack->top] = value; // top을 증가시키고, 요소를 추가
    }
}

Pop()

스택에서 element를 제거하는 함수

int Pop(Stack* stack) {
    if (IsEmpty(stack)) {
        printf("Stack underflow! Unable to pop\n");
        return -1; // 스택이 비어있으면 오류 반환
    } else {
        return stack->data[stack->top--]; // 요소를 반환하고 top을 감소시킴
    }
}

CreateStack()

스택 생성 함수

Stack* CreateStack() {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    if (stack != NULL) {
        stack->top = -1; // 스택을 초기화, top이 -1이면 빈 상태
    }
    return stack;
}

IsFull()

스택이 가득 찼는지 확인하는 함수

int IsFull(Stack* stack) {
    return stack->top == MAX_SIZE - 1; // top이 MAX_SIZE-1이면 스택이 가득 찬 상태
}

IsEmpty()

스택이 비었는지 확인하는 함수

int IsEmpty(Stack* stack) {
    return stack->top == -1; // top이 -1이면 스택이 비어 있는 상태
}

-🐢--

스택 예시 코드

배열

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 5  // 스택의 최대 크기

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

// 스택 생성 함수
Stack* CreateStack() {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    if (stack != NULL) {
        stack->top = -1; // 스택을 초기화, top이 -1이면 빈 상태
    }
    return stack;
}

// 스택이 가득 찼는지 확인하는 함수
int IsFull(Stack* stack) {
    return stack->top == MAX_SIZE - 1; // top이 MAX_SIZE-1이면 스택이 가득 찬 상태
}

// 스택에 요소를 추가하는 함수 (Push)
void Push(Stack* stack, int value) {
    if (IsFull(stack)) {
        printf("Stack overflow! Unable to push %d\n", value);
    } else {
        stack->data[++stack->top] = value; // top을 증가시키고, 요소를 추가
    }
}

// 스택이 비었는지 확인하는 함수
int IsEmpty(Stack* stack) {
    return stack->top == -1; // top이 -1이면 스택이 비어 있는 상태
}

// 스택에서 요소를 제거하는 함수 (Pop)
int Pop(Stack* stack) {
    if (IsEmpty(stack)) {
        printf("Stack underflow! Unable to pop\n");
        return -1; // 스택이 비어있으면 오류 반환
    } else {
        return stack->data[stack->top--]; // 요소를 반환하고 top을 감소시킴
    }
}

// 메인 함수에서 스택 연산 사용 예시
int main() {
    Stack* stack = CreateStack();
    
    Push(stack, 10);
    Push(stack, 20);
    Push(stack, 30);
    Push(stack, 40);
    Push(stack, 50);
    Push(stack, 60); // 이 연산은 스택이 가득 차서 실패함

    printf("Pop: %d\n", Pop(stack)); // 출력: 50
    printf("Pop: %d\n", Pop(stack)); // 출력: 40
    printf("Pop: %d\n", Pop(stack)); // 출력: 30
    printf("Pop: %d\n", Pop(stack)); // 출력: 20
    printf("Pop: %d\n", Pop(stack)); // 출력: 10
    printf("Pop: %d\n", Pop(stack)); // 이 연산은 스택이 비어서 실패함

    free(stack);
    return 0;
}

연결 리스트

#include <stdio.h>
#include <stdlib.h>

// 노드 구조체 정의
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 스택의 맨 위를 가리키는 포인터
Node* top = NULL;

// 스택 생성 함수
void CreateStack() {
    top = NULL; // 스택 초기화 (top이 NULL이면 스택이 비어 있는 상태)
}

// 스택이 비었는지 확인하는 함수
int IsEmpty() {
    return top == NULL; // top이 NULL이면 스택이 비어 있는 상태
}

// 스택에 요소를 추가하는 함수 (Push)
void Push(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 새 노드 동적 할당
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return;
    }
    newNode->data = value; // 새로운 노드에 값 저장
    newNode->next = top;   // 새로운 노드의 next가 현재의 top을 가리키게 설정
    top = newNode;         // top을 새로운 노드로 갱신
}

// 스택에서 요소를 제거하는 함수 (Pop)
int Pop() {
    if (IsEmpty()) {
        printf("Stack underflow! Unable to pop\n");
        return -1; // 스택이 비어 있으면 오류 반환
    } else {
        Node* temp = top;      // 현재 top 노드를 임시로 저장
        int value = top->data; // top 노드의 데이터 저장
        top = top->next;       // top을 다음 노드로 갱신
        free(temp);            // 이전 top 노드 메모리 해제
        return value;          // 제거한 데이터 반환
    }
}

// 스택의 맨 위 요소를 확인하는 함수 (Peek)
int Peek() {
    if (IsEmpty()) {
        printf("Stack is empty!\n");
        return -1;
    } else {
        return top->data; // 현재 top 노드의 데이터 반환
    }
}

// 메인 함수에서 스택 연산 사용 예시
int main() {
    CreateStack();
    
    Push(10);
    Push(20);
    Push(30);

    printf("Top element: %d\n", Peek()); // 출력: 30

    printf("Pop: %d\n", Pop()); // 출력: 30
    printf("Pop: %d\n", Pop()); // 출력: 20
    printf("Pop: %d\n", Pop()); // 출력: 10
    printf("Pop: %d\n", Pop()); // 출력: Stack underflow!

    return 0;
}

🐢---

 

🐢: 요즘 감기가 독하네요. 이번 주 내내 열이 나서 아무것도 못 했어요ㅠㅠㅠ 모두 건강 잘 챙기시고 항상 행복하시길 바랍니다!