자료구조 [ 스택과 큐 ]

스택(Stack)과 큐(Queue)는 컴퓨터 공학에서 매우 중요한 기초 자료구조 중 하나입니다. 이 두 가지 자료구조는 각각의 고유한 특성을 가지고 있으며, 다양한 알고리즘에서 사용됩니다. 이번 글에서는 스택과 큐에 대한 기본 개념을 설명하고, 이를 Java와 C 언어로 직접 구현해 보겠습니다.

스택(Stack)

스택은 "LIFO(Last In, First Out)" 원칙을 따르는 자료구조입니다. 즉, 가장 나중에 삽입된 요소가 가장 먼저 제거됩니다. 이를 현실 세계의 예시로 비유하면, 접시를 쌓는 행위와 유사합니다. 가장 나중에 쌓은 접시가 가장 먼저 사용됩니다.

스택에서 주로 사용하는 연산은 다음과 같습니다:

• push: 스택에 새로운 요소를 추가합니다.
• pop: 스택에서 가장 위에 있는 요소를 제거합니다.
• peek: 스택의 가장 위에 있는 요소를 조회하지만 제거하지는 않습니다.
• isEmpty: 스택이 비어있는지 확인합니다.

스택 구현: Java 예제

import java.util.EmptyStackException;

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

    public Stack(int size) {
        this.maxSize = size;
        this.stackArray = new int[maxSize];
        this.top = -1;
    }

    public void push(int value) {
        if (top == maxSize - 1) {
            System.out.println("스택이 가득 찼습니다.");
        } else {
            stackArray[++top] = value;
        }
    }

    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        } else {
            return stackArray[top--];
        }
    }

    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        } else {
            return stackArray[top];
        }
    }

    public boolean isEmpty() {
        return (top == -1);
    }

    public static void main(String[] args) {
        Stack stack = new Stack(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());
    }
}

위의 Java 코드에서는 스택을 정수 배열로 구현하였으며, push, pop, peek, isEmpty 메서드를 포함하고 있습니다.

스택 구현: C 예제

#include <stdio.h>
#include <stdlib.h>
#define MAX 5

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

void initStack(Stack *s) {
    s->top = -1;
}

int isFull(Stack *s) {
    return s->top == MAX - 1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("스택이 가득 찼습니다.\n");
    } else {
        s->items[++(s->top)] = value;
    }
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("스택이 비어있습니다.\n");
        exit(1);
    } else {
        return s->items[(s->top)--];
    }
}

int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("스택이 비어있습니다.\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;
}

위의 C 코드에서는 스택을 구조체로 구현하였으며, 스택의 최대 크기를 고정값으로 설정하였습니다. push, pop, peek 함수를 통해 스택을 조작할 수 있습니다.

큐(Queue)

큐는 "FIFO(First In, First Out)" 원칙을 따르는 자료구조입니다. 즉, 가장 먼저 삽입된 요소가 가장 먼저 제거됩니다. 현실 세계에서는 줄 서기와 비슷한 개념으로 설명할 수 있습니다. 줄의 맨 앞에 있는 사람이 가장 먼저 서비스를 받는 것과 같습니다.

큐에서 주로 사용하는 연산은 다음과 같습니다:

• enqueue: 큐의 끝에 새로운 요소를 추가합니다.
• dequeue: 큐의 맨 앞에 있는 요소를 제거합니다.
• peek: 큐의 맨 앞에 있는 요소를 조회합니다.
• isEmpty: 큐가 비어있는지 확인합니다.

큐 구현: Java 예제

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

    public Queue(int size) {
        this.maxSize = size;
        this.queueArray = new int[maxSize];
        this.front = 0;
        this.rear = -1;
        this.nItems = 0;
    }

    public void enqueue(int value) {
        if (nItems == maxSize) {
            System.out.println("큐가 가득 찼습니다.");
        } else {
            if (rear == maxSize - 1) {
                rear = -1;
            }
            queueArray[++rear] = value;
            nItems++;
        }
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("큐가 비어있습니다.");
        } else {
            int temp = queueArray[front++];
            if (front == maxSize) {
                front = 0;
            }
            nItems--;
            return temp;
        }
    }

    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("큐가 비어있습니다.");
        } else {
            return queueArray[front];
        }
    }

    public boolean isEmpty() {
        return (nItems == 0);
    }

    public static void main(String[] args) {
        Queue queue = new Queue(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());
    }
}

위의 Java 코드에서는 큐를 정수 배열로 구현하고, enqueue, dequeue, peek, isEmpty 메서드를 통해 큐를 관리합니다.

큐 구현: C 예제

#include <stdio.h>
#include <stdlib.h>
#define MAX 5

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

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

int isFull(Queue *q) {
    return (q->rear + 1) % MAX == q->front;
}

int isEmpty(Queue *q) {
    return q->front == -1;
}

void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("큐가 가득 찼습니다.\n");
    } else {
        if (isEmpty(q)) {
            q->front = 0;
        }
        q->rear = (q->rear + 1) % MAX;
        q->items[q->rear] = value;
    }
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("큐가 비어있습니다.\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;
    }
}

int peek(Queue *q) {
    if (isEmpty(q)) {
        printf("큐가 비어있습니다.\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;
}

위의 C 코드에서는 큐를 배열로 구현하고, enqueue, dequeue, peek 함수로 큐를 조작합니다. 원형 배열을 사용하여 큐의 효율성을 높였습니다.

결론

스택과 큐는 각각의 고유한 특성을 가지고 있으며, 다양한 알고리즘과 문제 해결에 필수적인 역할을 합니다. 이번 글에서는 스택과 큐의 기본 개념과 Java 및 C 언어로의 구현 예제를 살펴보았습니다. 이러한 자료구조를 깊이 이해하고 직접 구현해 보는 것은 컴퓨터 공학의 기본을 탄탄히 다지는 데 큰 도움이 됩니다.

다음 글에서는 좀 더 고급 자료구조와 알고리즘을 다루어 보도록 하겠습니다. 직접 코드를 작성하고 실행해 보면서 자료구조의 작동 방식을 체득해 보세요!