C언어로 배열을 활용한 스택과 큐의 구현 방법

C언어에서 배열을 활용한 스택과 큐 구현은 자료구조의 기본을 이해하는 데 중요한 역할을 합니다. 스택과 큐는 데이터의 저장과 관리 방식을 정의하는 대표적인 자료구조로, 다양한 알고리즘과 실전 프로그래밍에 필수적입니다. 본 기사에서는 스택과 큐의 개념을 살펴보고, 배열을 사용해 구현하는 방법과 그 과정에서 발생할 수 있는 문제 해결법을 상세히 다룹니다. 이를 통해 C언어의 자료구조 활용 능력을 한 단계 끌어올릴 수 있습니다.

스택과 큐란 무엇인가

스택과 큐는 데이터를 저장하고 관리하는 방식에 따라 분류된 자료구조로, 각각 특정한 사용 사례와 특징을 가지고 있습니다.

스택의 정의와 특징

스택(Stack)은 후입선출(LIFO, Last In, First Out) 원칙을 따르는 자료구조입니다.

데이터를 한쪽 끝에서만 삽입(push)하거나 삭제(pop)할 수 있습니다.
대표적 사용 사례: 함수 호출 기록(콜 스택), 되돌리기 기능, 계산기 연산.

큐의 정의와 특징

큐(Queue)는 선입선출(FIFO, First In, First Out) 원칙을 따르는 자료구조입니다.

데이터는 한쪽 끝에서 삽입(enqueue)되고, 반대쪽 끝에서 삭제(dequeue)됩니다.
대표적 사용 사례: 작업 스케줄링, 프린터 대기열, 네트워크 패킷 처리.

스택과 큐의 차이점

스택은 마지막에 삽입된 데이터가 가장 먼저 삭제되는 구조이며, 큐는 먼저 삽입된 데이터가 가장 먼저 삭제되는 구조입니다. 두 구조 모두 데이터의 삽입과 삭제를 효율적으로 처리하기 위한 자료구조로, 특정 문제 해결에 따라 적합성이 달라집니다.

스택과 큐의 기본 개념을 이해하는 것은 배열을 활용한 구현으로 나아가는 첫걸음입니다.

스택의 주요 연산과 활용 예시

스택의 주요 연산

스택은 후입선출(LIFO) 원칙에 따라 작동하며, 다음과 같은 기본 연산이 제공됩니다.

Push

스택의 맨 위에 데이터를 추가합니다.

예: [10, 20] 스택에 30을 Push하면 [10, 20, 30]이 됩니다.

Pop

스택의 맨 위 데이터를 제거합니다.

예: [10, 20, 30]에서 Pop을 호출하면 30이 제거되고 스택은 [10, 20]이 됩니다.

Peek (Top)

스택의 맨 위 데이터를 제거하지 않고 확인합니다.

예: [10, 20, 30]에서 Peek을 호출하면 30이 반환됩니다.

스택의 활용 예시

스택은 다양한 알고리즘에서 활용되며, 대표적인 사용 사례는 다음과 같습니다.

1. 함수 호출 스택

함수 호출 시 현재 상태를 저장하고, 호출이 끝나면 복구합니다. 이를 콜 스택(Call Stack)이라 합니다.

예: 재귀 함수 호출에서 이전 상태를 복구하는 데 사용됩니다.

2. 괄호의 유효성 검사

문자열에서 괄호의 열림과 닫힘이 올바른지 확인하는 데 스택이 사용됩니다.

알고리즘: 열린 괄호는 Push, 닫힌 괄호는 Pop으로 처리하며, 비정상적인 상태를 확인합니다.

3. 되돌리기(Undo) 기능

문서 편집기나 그림 그리기 소프트웨어에서 작업 내역을 추적하고 되돌리는 기능에 사용됩니다.

각 작업은 스택에 Push되고, Undo 시 Pop을 호출합니다.

스택의 이러한 연산과 활용 사례를 이해하면 배열로 구현하는 과정을 더욱 쉽게 따라갈 수 있습니다.

배열로 구현하는 스택

배열을 활용한 스택 구현은 간단하면서도 스택의 기본 동작을 이해하기에 적합합니다. 배열을 사용하면 정해진 크기 내에서 스택의 데이터를 저장하고 관리할 수 있습니다.

스택 배열 구현의 기본 구조

배열로 스택을 구현하기 위해 필요한 요소는 다음과 같습니다:

배열: 데이터를 저장할 공간.
탑(top): 스택의 맨 위 데이터를 가리키는 인덱스.
크기 제한: 스택의 최대 크기를 정의.

스택 배열 구현 코드

아래는 C언어로 배열을 사용해 스택을 구현한 예제입니다.

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

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

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

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

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

// 데이터 삽입 (Push)
bool push(Stack* stack, int value) {
    if (isFull(stack)) {
        printf("스택 오버플로우\n");
        return false;
    }
    stack->data[++stack->top] = value;
    return true;
}

// 데이터 제거 (Pop)
int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("스택 언더플로우\n");
        return -1; // 오류 코드
    }
    return stack->data[stack->top--];
}

// 스택의 맨 위 데이터 확인 (Peek)
int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("스택이 비어 있습니다\n");
        return -1; // 오류 코드
    }
    return stack->data[stack->top];
}

// 테스트
int main() {
    Stack stack;
    initializeStack(&stack);

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

    printf("Top: %d\n", peek(&stack));
    printf("Popped: %d\n", pop(&stack));
    printf("Popped: %d\n", pop(&stack));
    printf("Popped: %d\n", pop(&stack));

    return 0;
}

코드 설명

initializeStack: 스택을 초기화하여 top을 -1로 설정.
isEmpty: 스택이 비어 있는지 확인.
isFull: 스택이 가득 찼는지 확인.
push: 데이터를 스택에 삽입하며, top을 증가.
pop: 데이터를 제거하며, top을 감소.
peek: 데이터를 제거하지 않고 맨 위의 값을 반환.

제한 사항

배열은 크기가 고정되어 있어 스택 오버플로우 문제가 발생할 수 있습니다.
동적 배열이나 연결 리스트를 사용하면 이러한 제한을 해결할 수 있습니다.

이 코드를 기반으로 스택 동작을 이해하고, 다양한 문제 해결에 응용할 수 있습니다.

큐의 주요 연산과 활용 예시

큐의 주요 연산

큐는 선입선출(FIFO) 원칙을 따르며, 다음과 같은 기본 연산을 지원합니다.

Enqueue

큐의 맨 뒤에 데이터를 추가합니다.

예: [10, 20] 큐에 30을 Enqueue하면 [10, 20, 30]이 됩니다.

Dequeue

큐의 맨 앞 데이터를 제거합니다.

예: [10, 20, 30] 큐에서 Dequeue를 호출하면 10이 제거되고 큐는 [20, 30]이 됩니다.

Front

큐의 맨 앞 데이터를 제거하지 않고 확인합니다.

예: [10, 20, 30] 큐에서 Front를 호출하면 10이 반환됩니다.

큐의 활용 예시

큐는 데이터가 순서대로 처리되는 경우에 적합하며, 다음과 같은 사례에서 사용됩니다.

1. 작업 스케줄링

운영 체제의 작업 관리에서 프로세스는 큐에 의해 순서대로 처리됩니다.

예: CPU 작업 대기열에서 프로세스가 Enqueue되고, 처리 시 Dequeue됩니다.

2. 프린터 대기열

프린터는 먼저 요청된 작업을 처리하므로 작업들이 큐에 저장됩니다.

예: 프린트 요청은 큐에 추가되고, 완료되면 제거됩니다.

3. BFS (너비 우선 탐색)

그래프 탐색 알고리즘에서 큐는 노드 방문 순서를 관리하는 데 사용됩니다.

알고리즘: 방문한 노드를 큐에 넣고, 순차적으로 처리하며 연결된 노드를 추가합니다.

4. 네트워크 패킷 처리

네트워크에서 데이터 패킷은 큐를 통해 수신되며, 순서대로 처리됩니다.

큐의 중요성

큐는 데이터를 처리하는 순서가 중요한 경우에 필수적입니다. 이를 이해하고 구현하는 것은 프로그램의 구조적 설계와 효율성 향상에 크게 기여합니다.

배열로 구현하는 큐

배열을 사용해 큐를 구현하면 간단하고 직관적이지만, 고정된 크기로 인해 몇 가지 제한사항이 있습니다. 기본적인 큐 동작을 구현하면서 이러한 특징을 살펴볼 수 있습니다.

큐 배열 구현의 기본 구조

큐를 배열로 구현하기 위해 다음 요소가 필요합니다:

배열: 데이터를 저장할 공간.
프런트(front): 큐의 맨 앞 데이터를 가리키는 인덱스.
리어(rear): 큐의 맨 뒤 데이터를 가리키는 인덱스.
크기 제한: 큐의 최대 크기를 정의.

큐 배열 구현 코드

다음은 C언어로 배열을 사용해 큐를 구현한 예제입니다.

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

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

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

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

// 데이터 삽입 (Enqueue)
bool enqueue(Queue* queue, int value) {
    if (isFull(queue)) {
        printf("큐 오버플로우\n");
        return false;
    }
    if (isEmpty(queue)) {
        queue->front = 0;
    }
    queue->rear = (queue->rear + 1) % MAX_SIZE;
    queue->data[queue->rear] = value;
    return true;
}

// 데이터 제거 (Dequeue)
int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        printf("큐 언더플로우\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;
}

// 큐의 맨 앞 데이터 확인 (Front)
int front(Queue* queue) {
    if (isEmpty(queue)) {
        printf("큐가 비어 있습니다\n");
        return -1; // 오류 코드
    }
    return queue->data[queue->front];
}

// 테스트
int main() {
    Queue queue;
    initializeQueue(&queue);

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

    printf("Front: %d\n", front(&queue));
    printf("Dequeued: %d\n", dequeue(&queue));
    printf("Dequeued: %d\n", dequeue(&queue));
    printf("Dequeued: %d\n", dequeue(&queue));

    return 0;
}

코드 설명

initializeQueue: 큐를 초기화하여 front와 rear를 -1로 설정.
isEmpty: 큐가 비어 있는지 확인.
isFull: 큐가 가득 찼는지 확인(원형 큐의 논리를 사용).
enqueue: 큐의 맨 뒤에 데이터를 삽입하며, rear를 업데이트.
dequeue: 큐의 맨 앞 데이터를 제거하며, front를 업데이트.
front: 데이터를 제거하지 않고 맨 앞의 값을 반환.

제한 사항

배열은 고정된 크기(MAX_SIZE)로 설정되어, 동적으로 크기를 변경할 수 없습니다.
원형 큐 논리를 사용하지 않으면 공간 낭비가 발생할 수 있습니다.

이 코드는 큐 동작을 이해하고, 배열을 활용한 구현의 강점과 한계를 파악하는 데 유용합니다.

원형 큐의 구현과 차이점

원형 큐는 일반 배열 기반 큐의 한계를 극복하기 위해 고안된 구조로, 큐의 시작과 끝이 연결된 형태를 가지고 있습니다. 이를 통해 배열을 효율적으로 사용하고, 공간 낭비를 줄일 수 있습니다.

원형 큐와 일반 큐의 차이점

공간 효율성

일반 큐는 데이터가 제거된 후에도 공간을 재사용하지 못해 낭비가 발생할 수 있습니다.
원형 큐는 배열의 시작과 끝을 연결하여 공간을 재활용합니다.

인덱스 관리

일반 큐는 rear가 배열의 끝에 도달하면 더 이상 삽입할 수 없습니다.
원형 큐는 (rear + 1) % MAX_SIZE로 순환하며 배열의 시작 부분을 재활용합니다.

원형 큐의 구현 코드

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} CircularQueue;

// 원형 큐 초기화
void initializeCircularQueue(CircularQueue* queue) {
    queue->front = -1;
    queue->rear = -1;
}

// 원형 큐가 비어 있는지 확인
bool isEmpty(CircularQueue* queue) {
    return queue->front == -1;
}

// 원형 큐가 가득 찼는지 확인
bool isFull(CircularQueue* queue) {
    return (queue->rear + 1) % MAX_SIZE == queue->front;
}

// 데이터 삽입 (Enqueue)
bool enqueue(CircularQueue* queue, int value) {
    if (isFull(queue)) {
        printf("큐 오버플로우\n");
        return false;
    }
    if (isEmpty(queue)) {
        queue->front = 0;
    }
    queue->rear = (queue->rear + 1) % MAX_SIZE;
    queue->data[queue->rear] = value;
    return true;
}

// 데이터 제거 (Dequeue)
int dequeue(CircularQueue* queue) {
    if (isEmpty(queue)) {
        printf("큐 언더플로우\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;
}

// 큐의 맨 앞 데이터 확인 (Front)
int front(CircularQueue* queue) {
    if (isEmpty(queue)) {
        printf("큐가 비어 있습니다\n");
        return -1; // 오류 코드
    }
    return queue->data[queue->front];
}

// 테스트
int main() {
    CircularQueue queue;
    initializeCircularQueue(&queue);

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

    printf("Front: %d\n", front(&queue));
    printf("Dequeued: %d\n", dequeue(&queue));
    enqueue(&queue, 40);
    printf("Front: %d\n", front(&queue));
    printf("Dequeued: %d\n", dequeue(&queue));

    return 0;
}

코드 설명

initializeCircularQueue: 원형 큐를 초기화합니다.
isEmpty: 원형 큐가 비어 있는지 확인합니다.
isFull: 원형 큐가 가득 찼는지 확인하며 (rear + 1) % MAX_SIZE를 사용합니다.
enqueue: 데이터를 삽입하며 rear를 순환적으로 업데이트합니다.
dequeue: 데이터를 제거하며 front를 순환적으로 업데이트합니다.
front: 큐의 맨 앞 데이터를 반환합니다.

원형 큐의 장점

배열 크기 내에서 메모리를 효율적으로 사용합니다.
일정한 크기의 데이터 스트림(예: 네트워크 버퍼) 처리에 적합합니다.

원형 큐를 구현하면 큐의 공간 활용도를 최대화하고, 배열 기반 자료구조의 한계를 극복할 수 있습니다.

스택과 큐의 한계 및 개선 방법

배열을 활용한 스택과 큐는 구현이 간단하고 성능이 우수하지만, 몇 가지 한계가 있습니다. 이러한 한계를 극복하는 방법을 이해하면 보다 효율적이고 유연한 자료구조를 설계할 수 있습니다.

스택과 큐의 주요 한계

1. 고정 크기 제한

배열 기반 구현에서는 크기가 고정되어 있어, 초기 설정된 크기를 초과하는 데이터를 저장할 수 없습니다.

문제점: 데이터 삽입 시 스택 오버플로우나 큐 오버플로우가 발생할 수 있습니다.
영향: 예측하지 못한 데이터 증가를 처리하지 못해 프로그램의 안정성이 저하됩니다.

2. 비효율적인 메모리 사용

배열 기반 큐에서는 데이터가 제거되더라도 해당 메모리 공간을 재활용하지 못해 공간 낭비가 발생합니다.

일반 큐의 경우: Dequeue 연산 후에도 비어 있는 공간은 활용되지 않습니다.
원형 큐로 해결 가능: 원형 큐를 사용하면 공간 낭비를 줄일 수 있지만, 고정 크기의 한계는 여전히 존재합니다.

3. 동적 크기 조정 불가

배열은 크기가 고정되어 있어, 실행 중 동적으로 크기를 변경하거나 확장하는 것이 어렵습니다.

문제점: 큰 크기의 배열을 미리 설정하면 메모리 낭비가 발생할 수 있고, 작은 크기를 설정하면 데이터를 초과할 수 있습니다.

한계를 극복하기 위한 개선 방법

1. 동적 배열 사용

동적 메모리 할당을 통해 배열 크기를 실행 중에 확장하거나 축소할 수 있습니다.

방법: C언어의 malloc, realloc을 사용해 동적 배열 구현.
장점: 데이터 증가량에 따라 배열 크기를 유연하게 조정 가능.

2. 연결 리스트 활용

연결 리스트 기반 스택과 큐를 구현하면 고정 크기 제한이 사라지고, 메모리 낭비를 줄일 수 있습니다.

스택 구현: 노드 추가 및 제거가 간단하며, 메모리를 필요에 따라 동적으로 사용.
큐 구현: 노드 기반으로 삽입과 제거를 효율적으로 처리 가능.

3. 라이브러리 및 모듈 사용

C언어에서 제공되지 않는 기능을 외부 라이브러리나 모듈로 확장할 수 있습니다.

예: glib 같은 C 라이브러리를 사용하여 동적 크기의 자료구조 구현.

4. 하이브리드 접근

배열과 연결 리스트의 장점을 결합하여 하이브리드 자료구조를 설계할 수 있습니다.

예: 동적 배열을 사용하되, 데이터를 노드로 관리하여 유연성과 성능을 극대화.

결론

배열 기반 스택과 큐는 간단하고 효율적이지만, 고정 크기와 공간 낭비 문제가 있습니다. 동적 배열, 연결 리스트, 라이브러리 활용 등의 방법을 통해 이러한 한계를 극복할 수 있습니다. 상황에 맞는 자료구조 설계를 통해 더 유연하고 강력한 프로그램을 작성할 수 있습니다.

연습 문제와 해설

자료구조인 스택과 큐를 배열로 구현하고 응용하는 연습 문제를 통해 학습 효과를 높일 수 있습니다. 각 문제는 구현력을 향상시키고 실전 프로그래밍 감각을 기르는 데 중점을 둡니다.

문제 1: 스택 구현 및 연산 테스트

문제
배열을 사용해 다음 조건에 맞는 스택을 구현하세요:

최대 크기 N을 입력받아 스택 초기화.
Push, Pop, Peek 연산 구현.
사용자가 명령을 입력할 때마다 해당 연산을 수행.

입력 예시

N = 5
Push 10
Push 20
Pop
Peek
Push 30

출력 예시

Pushed: 10
Pushed: 20
Popped: 20
Top: 10
Pushed: 30

해설

스택 배열을 초기화하고 크기를 제한합니다.
각 명령을 처리하여 스택의 동작을 테스트합니다.

문제 2: 큐의 순환 구조 테스트

문제
원형 큐를 구현하고 다음 조건을 테스트하세요:

큐의 크기 N을 입력받아 초기화.
Enqueue, Dequeue, Front 연산 구현.
큐가 가득 찼거나 비었을 때 적절한 메시지를 출력.

입력 예시

N = 3
Enqueue 10
Enqueue 20
Enqueue 30
Enqueue 40
Dequeue
Enqueue 40
Front

출력 예시

Enqueued: 10
Enqueued: 20
Enqueued: 30
Queue Overflow
Dequeued: 10
Enqueued: 40
Front: 20

해설

큐를 초기화하고, 순환 구조를 통해 공간을 재활용합니다.
가득 찬 상태와 비어 있는 상태를 확인합니다.

문제 3: 괄호 유효성 검사 (스택 활용)

문제
스택을 활용해 주어진 문자열의 괄호가 유효한지 확인하세요.

괄호 (), {}, []를 포함한 문자열 입력.
열린 괄호는 Push, 닫힌 괄호는 Pop으로 처리.
모든 연산 종료 후 스택이 비어 있어야 유효.

입력 예시

{[()]}
{[(])}

출력 예시

Valid
Invalid

해설

열린 괄호와 닫힌 괄호가 짝을 이루는지 확인합니다.
스택이 비어 있거나 짝이 맞지 않는 경우를 검출합니다.

문제 4: 큐를 이용한 작업 스케줄링

문제
큐를 사용해 작업 목록을 처리하세요:

작업 수 N과 각 작업의 처리 시간을 입력받아 큐에 저장.
처리 순서대로 작업을 꺼내며, 처리 시간을 기록.
모든 작업이 완료된 후 총 처리 시간을 출력.

입력 예시

N = 3
Task1 5
Task2 3
Task3 2

출력 예시

Task1 processed in 5s
Task2 processed in 3s
Task3 processed in 2s
Total time: 10s

해설

작업 목록을 큐에 저장하고 처리 순서대로 꺼냅니다.
각 작업 시간을 합산해 총 처리 시간을 계산합니다.

결론

이러한 연습 문제는 스택과 큐의 동작을 이해하고, 구현력을 향상시키며, 실전 문제 해결 능력을 키우는 데 도움을 줍니다. 정답 코드는 구현 후 테스트를 통해 확인하세요.

요약

본 기사에서는 C언어로 배열을 활용한 스택과 큐의 구현 방법을 설명했습니다. 스택의 기본 연산(Push, Pop, Peek)과 큐의 주요 연산(Enqueue, Dequeue, Front)을 이해하고, 일반 큐와 원형 큐의 차이점과 구현 방법을 살펴보았습니다. 또한, 배열 기반 구현의 한계와 이를 극복하기 위한 동적 배열과 연결 리스트 같은 대안도 제시했습니다. 연습 문제를 통해 실전 활용 능력을 키우고, 스택과 큐를 다양한 응용 사례에 적용할 수 있는 기초를 다질 수 있습니다.