자바 및 C 언어로 구현하는 스택(Stack)과 큐(Queue) 자료구조 완벽 가이드

스택(Stack)과 큐(Queue) 자료구조의 핵심 개요 및 작성 배경

컴퓨터 공학 및 임베디드 시스템 설계에서 데이터의 효율적인 저장과 제어는 시스템 성능을 좌우하는 핵심 요소입니다. 이 과정에서 가장 기본적이면서도 빈번하게 사용되는 선형 자료구조가 바로 LIFO 기반의 스택(Stack)과 FIFO 기반의 큐(Queue)입니다. 본 포스팅에서는 기존 블로그 글의 모호한 설명과 예외 처리의 누락 등의 기술적 오류를 바로잡고, 실제 엔지니어링 환경에서 정확하게 동작하는 Java 및 C 언어 구현 코드를 제공합니다. 독자들은 본문을 통해 각 자료구조의 내부 동작 원리를 명확히 이해하고, 실무 시스템 프로그래밍에 즉시 적용할 수 있는 최적화된 코드를 획득할 수 있습니다.

스택 및 큐 자료구조 구현 핵심 요약

• 스택은 LIFO(Last In, First Out) 원칙을 따르며 push(), pop(), peek() 연산을 통해 관리됩니다.
• 큐는 FIFO(First In, First Out) 원칙을 따르며 배열 기반 원형 큐(Circular Queue) 구조를 사용하여 자원 효율성을 극대화합니다.
• 소스 코드 내 모든 주석은 글로벌 개발자 가독성을 위해 영어로 작성되었으며, 메모리 누수 및 오버플로우 방지 로직이 포함되어 있습니다.

스택과 큐의 내부 동작 원리 및 소스 코드 상세 분석

기존 블로그 글에서 다루어진 스택과 큐의 기본적인 개념 정리를 보강하여, 실제 메모리 할당 및 인덱스 제어 과정에서의 오류를 방지할 수 있도록 상세히 분석합니다.

LIFO 원리에 기반한 스택(Stack)의 구조와 구현

스택은 데이터가 입력된 순서의 역순으로 출력되는 구조입니다. 배열을 이용해 스택을 구현할 때, top 변수는 현재 스택의 최상단 요소를 가리킵니다. 스택 크기를 초과하여 데이터를 삽입하는 스택 오버플로우(Stack Overflow)와 비어 있는 상태에서 데이터를 추출하는 언더플로우(Underflow) 예외 처리가 반드시 구현되어야 합니다.

Java 및 C 언어 스택 구현 예제

Java

import java.util.EmptyStackException;

public class StackImplementation {
    private int maxSize;
    private int[] stackArray;
    private int top;

    // Initialize stack with a specific size
    public StackImplementation(size_t size) {
        this.maxSize = size;
        this.stackArray = new int[maxSize];
        this.top = -1;
    }

    // Push an element onto the stack
    public void push(int value) {
        if (top == maxSize - 1) {
            throw new StackOverflowError("Stack Overflow: Stack is full.");
        } else {
            stackArray[++top] = value;
        }
    }

    // Remove and return the top element from the stack
    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        } else {
            return stackArray[top--];
        }
    }

    // Retrieve the top element without removing it
    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        } else {
            return stackArray[top];
        }
    }

    // Check if the stack is empty
    public boolean isEmpty() {
        return (top == -1);
    }

    public static void main(String[] args) {
        StackImplementation stack = new StackImplementation(5);
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("Top element: " + stack.peek());
        System.out.println("Popped element: " + stack.pop());
        System.out.println("Top element after pop: " + stack.peek());
    }
}

C

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

#define MAX 5

typedef struct {
    int items[MAX];
    int top;
} Stack;

// Initialize the stack top index
void initStack(Stack *s) {
    s->top = -1;
}

// Check if the stack is full
int isFull(Stack *s) {
    return s->top == MAX - 1;
}

// Check if the stack is empty
int isEmpty(Stack *s) {
    return s->top == -1;
}

// Push value into the stack
void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Error: Stack Overflow.\n");
    } else {
        s->items[++(s->top)] = value;
    }
}

// Pop value from the stack
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Error: Stack Underflow.\n");
        exit(1);
    } else {
        return s->items[(s->top)--];
    }
}

// Peek top value of the stack
int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Error: Stack is empty.\n");
        exit(1);
    } else {
        return s->items[s->top];
    }
}

int main() {
    Stack s;
    initStack(&s);
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    printf("Top element: %d\n", peek(&s));
    printf("Popped element: %d\n", pop(&s));
    printf("Top element after pop: %d\n", peek(&s));
    return 0;
}

FIFO 원리에 기반한 큐(Queue)의 구조와 원형 배열 활용

큐는 먼저 들어온 데이터가 먼저 나가는 FIFO 구조입니다. 단순 선형 배열을 사용할 경우 데이터가 빠져나간 앞쪽 공간을 재사용할 수 없는 문제가 발생하므로, 모듈로 연산(% MAX)을 활용한 원형 큐(Circular Queue) 구조를 적용하여 메모리 효율을 높여야 합니다.

Java 및 C 언어 큐 구현 예제

Java

public class QueueImplementation {
    private int maxSize;
    private int[] queueArray;
    private int front;
    private int rear;
    private int nItems;

    // Initialize circular queue
    public QueueImplementation(int size) {
        this.maxSize = size;
        this.queueArray = new int[maxSize];
        this.front = 0;
        this.rear = -1;
        this.nItems = 0;
    }

    // Insert an element at the rear of the queue
    public void enqueue(int value) {
        if (nItems == maxSize) {
            throw new IllegalStateException("Queue Overflow: Queue is full.");
        } else {
            if (rear == maxSize - 1) {
                rear = -1;
            }
            queueArray[++rear] = value;
            nItems++;
        }
    }

    // Remove an element from the front of the queue
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue Underflow: Queue is empty.");
        } else {
            int temp = queueArray[front++];
            if (front == maxSize) {
                front = 0;
            }
            nItems--;
            return temp;
        }
    }

    // View the front element of the queue
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty.");
        } else {
            return queueArray[front];
        }
    }

    // Check if the queue is empty
    public boolean isEmpty() {
        return (nItems == 0);
    }

    public static void main(String[] args) {
        QueueImplementation queue = new QueueImplementation(5);
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        System.out.println("Front element: " + queue.peek());
        System.out.println("Dequeued element: " + queue.dequeue());
        System.out.println("Front element after dequeue: " + queue.peek());
    }
}

C

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

#define MAX 5

typedef struct {
    int items[MAX];
    int front;
    int rear;
} Queue;

// Initialize queue pointers
void initQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

// Check if circular queue is full
int isFull(Queue *q) {
    return (q->rear + 1) % MAX == q->front;
}

// Check if queue is empty
int isEmpty(Queue *q) {
    return q->front == -1;
}

// Enqueue operation with circular index calculation
void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Error: Queue Overflow.\n");
    } else {
        if (isEmpty(q)) {
            q->front = 0;
        }
        q->rear = (q->rear + 1) % MAX;
        q->items[q->rear] = value;
    }
}

// Dequeue operation
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Error: Queue Underflow.\n");
        exit(1);
    } else {
        int value = q->items[q->front];
        if (q->front == q->rear) {
            q->front = q->rear = -1;
        } else {
            q->front = (q->front + 1) % MAX;
        }
        return value;
    }
}

// Peek queue front value
int peek(Queue *q) {
    if (isEmpty(q)) {
        printf("Error: Queue is empty.\n");
        exit(1);
    } else {
        return q->items[q->front];
    }
}

int main() {
    Queue q;
    initQueue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    printf("Front element: %d\n", peek(&q));
    printf("Dequeued element: %d\n", dequeue(&q));
    printf("Front element after dequeue: %d\n", peek(&q));
    return 0;
}

자료구조 비교 분석 표

특성 비교	스택 (Stack)	큐 (Queue)
데이터 접근 원칙	LIFO (Last In, First Out)	FIFO (First In, First Out)
주요 삽입 연산 함수	push()	enqueue()
주요 삭제 연산 함수	pop()	dequeue()
주요 활용 분야	함수 호출 스택, 실행 취소(Undo)	작업 스케줄링, 버퍼(Buffer) 관리
메모리 구조 제어	단일 포인터 (top)	이중 포인터 또는 인덱스 (front, rear)

자료구조 최적화 및 프로파일링 실무 노하우

• Cache Locality Consideration: 임베디드 시스템 및 고성능 연산 환경에서는 CPU 캐시 히트율을 극대화하기 위해 연결 리스트보다 연속된 메모리 공간을 점유하는 배열 기반의 스택과 큐를 우선적으로 선택하세요.
• Dynamic Allocation Management: 동적 크기 조절이 필요한 경우 크기 재할당(Reallocation) 비용과 단편화 현상을 고려하여 환형 버퍼 크기를 고정하거나 적절한 임계값을 설정하세요.
• Profiling Tools Integration: 대규모 데이터 트래픽을 처리하는 시스템에서는 메모리 누수와 병목 현상 진단을 위해 Valgrind 또는 Java VisualVM 프로파일링 도구를 연동하여 모니터링하세요.

자료구조 구현 시 흔히 발생하는 오류 및 예방 방안

• Stack Overflow and Underflow: 스택의 최대 크기를 초과하여 데이터를 삽입하거나 빈 스택에서 요소를 추출할 때 발생하는 예외 상황.
  • 예방 방안: push() 및 pop() 연산 수행 전 반드시 isFull() 및 isEmpty() 검증 로직을 선행 수행하도록 구현합니다.
• Queue Pointer Mismanagement: 원형 큐 구현 시 front와 rear 인덱스 계산 시의 오산으로 인한 데이터 손실 또는 무한 루프 발생.
  • 예방 방안: 인덱스 증가 시 반드시 모듈로 연산((index + 1) % MAX)을 적용하여 배열 경계 범위를 초과하지 않도록 제어합니다.

마무리

스택과 큐는 컴퓨터 공학 및 시스템 소프트웨어 개발의 근간이 되는 핵심 자료구조입니다. LIFO와 FIFO의 동작 메커니즘을 명확히 이해하고 예외 처리가 보장된 코드를 작성하는 것은 안정적인 애플리케이션 개발의 필수 조건입니다. 제시된 예제 코드를 바탕으로 내부 메모리 제어 방식을 체득하시기 바랍니다.

---

C 기본문법

---

JAVA 기본문법