[C++] 스택(stack), 큐(queue), 데크(deque) 직접 구현하기

스택(stack)

#include <iostream>

// 스택 클래스 정의
class Stack {
private:
    static const int MAX_SIZE = 100; // 스택의 최대 크기
    int arr[MAX_SIZE]; // 스택을 저장할 배열
    int top; // 스택의 가장 위에 있는 요소의 인덱스

public:
    Stack() : top(-1) {} // 생성자, 스택 초기화

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

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

    // 스택에 요소 추가
    void push(int value) {
        if (isFull()) {
            std::cout << "스택이 가득 찼습니다." << std::endl;
            return;
        }

        arr[++top] = value;
        std::cout << value << "이(가) 스택에 추가되었습니다." << std::endl;
    }

    // 스택에서 요소 제거
    void pop() {
        if (isEmpty()) {
            std::cout << "스택이 비어있습니다." << std::endl;
            return;
        }

        int value = arr[top--];
        std::cout << value << "이(가) 스택에서 제거되었습니다." << std::endl;
    }

    // 스택의 가장 위에 있는 요소 반환
    int topValue() {
        if (isEmpty()) {
            std::cout << "스택이 비어있습니다." << std::endl;
            return -1;
        }

        return arr[top];
    }
};

 

 

큐 (Queue)

// 큐 클래스 정의
class Queue {
private:
    static const int MAX_SIZE = 100; // 큐의 최대 크기
    int arr[MAX_SIZE]; // 큐를 저장할 배열
    int front; // 큐의 가장 앞에 있는 요소의 인덱스
    int rear; // 큐의 가장 뒤에 있는 요소의 인덱스

public:
    Queue() : front(-1), rear(-1) {} // 생성자, 큐 초기화

    // 큐가 비어있는지 확인
    bool isEmpty() {
        return (front == -1 && rear == -1);
    }

    // 큐가 가득 찼는지 확인
    bool isFull() {
        return (rear == MAX_SIZE - 1);
    }

    // 큐에 요소 추가
    void enqueue(int value) {
        if (isFull()) {
            std::cout << "큐가 가득 찼습니다." << std::endl;
            return;
        }

        if (isEmpty()) {
            front = rear = 0;
        } else {
            rear++;
        }

        arr[rear] = value;
        std::cout << value << "이(가) 큐에 추가되었습니다." << std::endl;
    }

    // 큐에서 요소 제거
    void dequeue() {
        if (isEmpty()) {
            std::cout << "큐가 비어있습니다." << std::endl;
            return;
        }

        int value = arr[front];
        if (front == rear) {
            front = rear = -1;
        } else {
            front++;
        }

        std::cout << value << "이(가) 큐에서 제거되었습니다." << std::endl;
    }

    // 큐의 가장 앞에 있는 요소 반환
    int frontValue() {
        if (isEmpty()) {
            std::cout << "큐가 비어있습니다." << std::endl;
            return -1;
        }

        return arr[front];
    }
};

 

데크(deque) 

#include <iostream>

// 덱 노드 정의
class Node {
public:
    int data;
    Node* prev;
    Node* next;

    Node(int value) : data(value), prev(nullptr), next(nullptr) {}
};

// 덱 클래스 정의
class Deque {
private:
    Node* front; // 덱의 가장 앞에 있는 노드
    Node* rear; // 덱의 가장 뒤에 있는 노드

public:
    Deque() : front(nullptr), rear(nullptr) {} // 생성자, 덱 초기화

    // 덱이 비어있는지 확인
    bool isEmpty() {
        return (front == nullptr && rear == nullptr);
    }

    // 덱의 가장 앞에 요소 추가
    void pushFront(int value) {
        Node* newNode = new Node(value);

        if (isEmpty()) {
            front = rear = newNode;
        } else {
            newNode->next = front;
            front->prev = newNode;
            front = newNode;
        }

        std::cout << value << "이(가) 덱의 가장 앞에 추가되었습니다." << std::endl;
    }

    // 덱의 가장 뒤에 요소 추가
    void pushBack(int value) {
        Node* newNode = new Node(value);

        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear->next = newNode;
            newNode->prev = rear;
            rear = newNode;
        }

        std::cout << value << "이(가) 덱의 가장 뒤에 추가되었습니다." << std::endl;
    }

    // 덱의 가장 앞에 있는 요소 제거
    void popFront() {
        if (isEmpty()) {
            std::cout << "덱이 비어있습니다." << std::endl;
            return;
        }

        int value = front->data;
        Node* temp = front;

        if (front == rear) {
            front = rear = nullptr;
        } else {
            front = front->next;
            front->prev = nullptr;
        }

        delete temp;
        std::cout << value << "이(가) 덱의 가장 앞에서 제거되었습니다." << std::endl;
    }

    // 덱의 가장 뒤에 있는 요소 제거
    void popBack() {
        if (isEmpty()) {
            std::cout << "덱이 비어있습니다." << std::endl;
            return;
        }

        int value = rear->data;
        Node* temp = rear;

        if (front == rear) {
            front = rear = nullptr;
        } else {
            rear = rear->prev;
            rear->next = nullptr;
        }

        delete temp;
        std::cout << value << "이(가) 덱의 가장 뒤에서 제거되었습니다." << std::endl;
    }

    // 덱의 가장 앞에 있는 요소 반환
    int frontValue() {
        if (isEmpty()) {
            std::cout << "덱이 비어있습니다." << std::endl;
            return -1;
        }

        return front->data;
    }

    // 덱의 가장 뒤에 있는 요소 반환
    int backValue() {
        if (isEmpty()) {
            std::cout << "덱이 비어있습니다." << std::endl;
            return -1;
        }

        return rear->data;
    }
};