서론

스택 (Stack) 과 큐 (Queue) 는 모두 데이터를 임시 저장하기 위해 사용하는 자료구조이며, 데이터를 입력하고 출력하는 방향이 정해져있다. 스택, 큐는 서로 비슷한 점을 많이 가지고 있는 자료구조이다.

스택(Stack)

스택은 데이터를 선형적으로 저장하는 데이터 구조로, 후입 선출 Last-In-First-Out (LIFO) 원칙을 따릅니다. 이는 가장 최근에 삽입된 데이터가 가장 먼저 제거되는 구조를 의미합니다. 스택은 데이터를 쌓는다는 개념으로 생각할 수 있습니다.

FILO 혹은 LIFO 은 각각 First In, Last Out 과 Last In, First Out 즉 후입선출을 의미한다.

스택에 주요연산으로:

Push: 스택에 데이터를 넣는 연산으로, 데이터를 스택의 맨 위에 추가합니다.
Pop: 스택에서 데이터를 제거하는 연산으로, 맨 위에 있는 데이터를 꺼냅니다.

활용 예

그렇다면 스택은 어떤 상황에서 활용되기 적합할까? 후입 선출이라 함은 들어온 순서와 나가는 순서가 반대의 관계에 있음을 의미한다. 즉 특정한 순서의 작업을 반대로 되돌릴 때 유용하게 사용할 수 있을 것이다. 이런 예시에는 무엇이 있을까?

• 문서, 이미지 편집기 등에서 사용되는 Undo (Ctrl + z) 기능
• 웹브라우저의 뒤로가기 기능
• 문자열 뒤집기
• 후위표기법의 계산
• 재귀함수의 호출과 실행 (실제로 재귀함수를 많이 호출하게되면 Stack Overflow 가 발생한다)

스택의 구현

#include <stdio.h>
#define MAX_SIZE 100

// 스택 구조체 정의
struct Stack {
    int data[MAX_SIZE];
    int top;
};

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

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

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

// 스택에 데이터를 추가하는 함수 (Push)
void push(struct Stack *stack, int value) {
    if (isFull(stack)) {
        printf("Stack is full. Cannot push.\n");
        return;
    }
    stack->data[++stack->top] = value;
}

// 스택에서 데이터를 제거하고 반환하는 함수 (Pop)
int pop(struct Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty. Cannot pop.\n");
        return -1; // 에러나 기본값 반환
    }
    return stack->data[stack->top--];
}

// 스택의 맨 위에 있는 데이터를 확인하는 함수 (Peek)
int peek(struct Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty. Cannot peek.\n");
        return -1; // 에러나 기본값 반환
    }
    return stack->data[stack->top];
}

int main() {
    struct Stack myStack;
    initialize(&myStack);

    push(&myStack, 10);
    push(&myStack, 20);
    push(&myStack, 30);

    printf("Peek: %d\n", peek(&myStack)); // 맨 위 데이터 확인

    printf("Pop: %d\n", pop(&myStack));
    printf("Pop: %d\n", pop(&myStack));
    printf("Pop: %d\n", pop(&myStack));

    return 0;
}

큐 (Queue)

큐는 데이터의 입력과 출력이 선입 선출 (FIFO) 방식을 따른다. 음식점 대기열과 같이 먼저 들어온 데이터가 먼저 나오게 된다. 큐에 데이터를 넣는 작업을 인큐 (Enqueue), 꺼내는 작업을 디큐 (Dequeue) 라고 한다. 또한 데이터가 나오는 곳을 프론트 (Front) 그리고 데이터가 들어가는 곳을 리어 (Rear) 라고 한다.

큐는 프린터의 대기열 같이 순서가 있는 작업을 순차적으로 처리할 때 사용한다.

큐에는 주로 두 가지 주요 연산이 있습니다:

큐의 주요연산으로:

Enqueue: 큐에 데이터를 넣는 연산으로, 데이터를 큐의 뒤에 추가합니다.
Dequeue: 큐에서 데이터를 제거하는 연산으로, 가장 앞에 있는 데이터를 꺼냅니다.

활용 예

큐는 주로 작업 대기열, BFS (너비 우선 탐색) 알고리즘에서 사용됩니다. 작업이나 데이터의 처리 순서를 관리할 때 유용한 구조입니다.

큐 구현

#include <stdio.h>
#define MAX_SIZE 100

// 큐 구조체 정의
struct Queue {
    int data[MAX_SIZE];
    int front;
    int rear;
};

// 큐 초기화 함수
void initialize(struct Queue *queue) {
    queue->front = -1;
    queue->rear = -1;
}

// 큐가 비어있는지 확인하는 함수
int isEmpty(struct Queue *queue) {
    return queue->front == -1;
}

// 큐가 가득 찼는지 확인하는 함수
int isFull(struct Queue *queue) {
    return (queue->rear + 1) % MAX_SIZE == queue->front;
}

// 큐에 데이터를 추가하는 함수 (Enqueue)
void enqueue(struct Queue *queue, int value) {
    if (isFull(queue)) {
        printf("Queue is full. Cannot enqueue.\n");
        return;
    }
    if (isEmpty(queue)) {
        queue->front = 0;
    }
    queue->rear = (queue->rear + 1) % MAX_SIZE;
    queue->data[queue->rear] = value;
}

// 큐에서 데이터를 제거하고 반환하는 함수 (Dequeue)
int dequeue(struct Queue *queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1; // 에러나 기본값 반환
    }
    int value = queue->data[queue->front];
    if (queue->front == queue->rear) {
        queue->front = -1;
        queue->rear = -1;
    } else {
        queue->front = (queue->front + 1) % MAX_SIZE;
    }
    return value;
}

int main() {
    struct Queue myQueue;
    initialize(&myQueue);

    enqueue(&myQueue, 10);
    enqueue(&myQueue, 20);
    enqueue(&myQueue, 30);

    printf("Dequeue: %d\n", dequeue(&myQueue));
    printf("Dequeue: %d\n", dequeue(&myQueue));
    printf("Dequeue: %d\n", dequeue(&myQueue));

    return 0;
}