스택과 큐

🔑Table of Contents

1. 스택이란?

---

📌스택이란? 

• 삽입과 삭제 연산을 한 쪽 끝에서만 일어나도록 제한한 리스트
• 스택에서 삽입과 삭제 연산이 일어나는 끝을 top이라하고, 삽입 연산과 삭제 연산을 각각 push, pop이라고 한다 

• LIFO : 스택에서 나중에 삽입된 원소가 먼저 삭제되는 성질
• 시스템에서 함수 호출이 발생할 경우, 가장 최근에 호출된 곳으로 복귀하기 위해 스택에 복귀 주소를 저장해 둔다 

📌스택의 구현1 - 배열

#define MAX_STACK_SIZE 1000              // 스택의 최대 크기 정의

// 스택에 저장될 요소의 구조체 정의
typedef struct {
    int key;  // 저장할 데이터 (다른 필드도 확장 가능)
    /* other fields here */
} element;

// 스택 배열과 top 인덱스 정의
element stack[MAX_STACK_SIZE];
int top = 0;  // 현재 스택의 맨 위를 가리키는 인덱스

// 스택이 가득 찼을 때 호출되는 함수 (에러 처리용)
void stack_full() {
    fprintf(stderr, "Stack is full!\n");
}

// 스택이 비었을 때 호출되는 함수 (에러 처리용)
element stack_empty() {
    fprintf(stderr, "Stack is empty!\n");
    element error = { -1 };  // 에러를 나타내는 element 반환
    return error;
}

// 스택에 새 요소를 push하는 함수
void push(int *top_ptr, element item)
{
    // top이 최대 크기를 넘지 않도록 확인
    if (*top_ptr >= MAX_STACK_SIZE) {
        stack_full();  // 에러 메시지 출력
        return;
    }

    // 현재 top 위치에 item 저장 후 top 증가
    stack[(*top_ptr)++] = item;
}

// 스택에서 요소를 pop하는 함수
element pop(int *top_ptr)
{
    // 스택이 비었는지 확인
    if (*top_ptr == 0) {
        return stack_empty();  // 에러 메시지 출력 및 에러 값 반환
    }

    // top 감소 후 해당 위치 값 반환
    return stack[--(*top_ptr)];
}

 

 

📌스택의 구현2 - 연결 리스트

 

// 스택에 item을 push (삽입)하는 함수
void push(list_pointer stack, int item)
{
    list_pointer temp;
    temp = (list_pointer) malloc(sizeof(list_node));  // 새 노드를 동적으로 할당

    if (temp == NULL) {       // 메모리 할당 실패 시 에러 처리
        stack_full();         // 사용자 정의 에러 함수
        return;
    }

    temp->data = item;         // 새 노드에 데이터 저장
    temp->link = stack->link;  // 새 노드가 기존의 top 노드를 가리키도록 설정
    stack->link = temp;        // stack(head)의 link를 새 노드로 갱신 (새 top)
}

// 스택에서 값을 pop (삭제 및 반환)하는 함수
int pop(list_pointer stack)
{
    list_pointer temp;
    int item;
    if (stack->link == NULL) {  // 스택이 비어있는 경우 처리
        return stack_empty();   // 사용자 정의 에러 반환
    }
    temp = stack->link;         // top 노드를 temp에 저장
    item = temp->data;          // 데이터 추출
    stack->link = temp->link;   // stack의 link를 다음 노드로 이동 (top 제거)

    free(temp);                 // 제거된 노드 메모리 해제
    return item;                // 꺼낸 데이터 반환
}

 

 

📌큐란?

     삽입 연산이 한쪽 끝에서 일어나고 삭제는 다른쪽 끝에서만 일어나도록 제한한 리스트

     rear  : 삽입이 일어나는 쪽

     front : 삭제가 일어나는 쪽

     enqueue : 삽입 연산

     dequeue : 삭제 연산

     FIFO : 큐에서는 먼저 삽입된 원소가 먼저 삭제되는 특성이 있음

     운영체제에서 여러 작업들을 스케줄링할 때 큐에 작업을 저장해 순서대로 수행하기도 함

 

 

 

📌큐의 구현1 - 배열

// 큐에 item을 삽입하는 함수
void enqueue(int *rear_ptr, element item)
{
    // rear가 큐의 최대 크기에 도달한 경우
    if (*rear_ptr >= MAX_QSIZE) {
        queue_full();  // 큐가 가득 찼다는 에러 처리 함수
        return;
    }

    // rear 위치에 item 삽입 후 rear 증가
    queue[(*rear_ptr)++] = item;
}

 

 

📌환형 큐

     환형 큐가 비어있는 경우는 front = rear일 때이고

     큐가 꽉 차있을 때에는 rear+1 (mod MAX_QSIZE) = front 

void enqueue (int *rear_ptr, int front, element item){
   if(( *rear_ptr + 1) % MAX_QSIZE == front){
       queue_full();
       return;
   }
   element dequeue(int *front_ptr, int rear){
       int k;
       if (*front_ptr == rear){
           return queue_empty();
       }
       k= *front_ptr;
       *front_ptr = (*front_ptr + 1) & MAX_QSIZE;
       return queue[k];
   }
}

 

 

📌큐의 구현2 - 연결 리스트 

    해드 노드를 가진 연결 리스트를 이용해 큐를 구현한다 

    각 노드는 data, link 필드로 구성되어있다고 하자