[c++] 배열과 포인터를 사용한 스택 및 큐 구현

14 Dec 2023

이번에는 C++ 언어를 사용하여 배열과 포인터를 이용한 스택(Stack)과 큐(Queue)를 구현하는 방법에 대해 알아보겠습니다.

스택(Stack) 구현

먼저, 스택(Stack)은 후입선출(Last In, First Out; LIFO) 구조를 갖는 자료구조로, 배열을 이용하여 구현할 수 있습니다. 아래는 C++로 배열을 사용하여 스택을 구현한 예시 코드입니다.

#include <iostream>
#define MAX_SIZE 100

class Stack {
private:
    int top;
    int arr[MAX_SIZE];

public:
    Stack() {
        top = -1;
    }

    void push(int x) {
        if (top >= MAX_SIZE - 1) {
            std::cout << "Stack Overflow" << std::endl;
            return;
        }
        arr[++top] = x;
    }

    void pop() {
        if (top < 0) {
            std::cout << "Stack Underflow" << std::endl;
            return;
        }
        top--;
    }

    int peek() {
        if (top < 0) {
            std::cout << "Stack is Empty" << std::endl;
            return -1;
        }
        return arr[top];
    }
};

위의 코드는 정수를 저장할 수 있는 배열을 사용하여 스택을 구현한 것입니다. push 함수는 스택에 요소를 추가하고, pop 함수는 가장 최근에 추가된 요소를 제거합니다. peek 함수는 현재 스택의 맨 위에 있는 요소를 반환합니다.

큐(Queue) 구현

다음은 큐(Queue)를 포인터를 사용하여 구현한 예시 코드입니다. 큐는 선입선출(First In, First Out; FIFO) 구조를 갖는 자료구조입니다.

#include <iostream>
#define MAX_SIZE 100

class Queue {
private:
    int front, rear, size;
    int* arr;

public:
    Queue(int sz) {
        front = rear = -1;
        size = sz;
        arr = new int[size];
    }

    void enqueue(int x) {
        if ((front == 0 && rear == size - 1) || (rear == (front - 1) % (size - 1))) {
            std::cout << "Queue is Full" << std::endl;
            return;
        }
        else if (front == -1) {
            front = rear = 0;
            arr[rear] = x;
        }
        else if (rear == size - 1 && front != 0) {
            rear = 0;
            arr[rear] = x;
        }
        else {
            arr[++rear] = x;
        }
    }

    int dequeue() {
        if (front == -1) {
            std::cout << "Queue is Empty" << std::endl;
            return -1;
        }
        int data = arr[front];
        arr[front] = -1;
        if (front == rear) {
            front = rear = -1;
        }
        else if (front == size - 1) {
            front = 0;
        }
        else {
            front++;
        }
        return data;
    }
};

위의 코드는 포인터를 사용하여 동적으로 할당한 배열을 이용하여 큐를 구현한 것입니다. enqueue 함수는 큐에 요소를 추가하고, dequeue 함수는 큐에서 요소를 제거합니다.

이상으로 C++를 사용하여 배열과 포인터를 이용하여 스택과 큐를 구현하는 방법에 대해 알아보았습니다.

참고문헌