자료구조 - 예상문제 3 스택, 큐, 직접 구현하기

IT 프로그래밍/자료구조

자료구조 - 예상문제 3 스택, 큐, 직접 구현하기

기술1 2024. 12. 15. 10:28

1. 스택(Stack) 구현

기본적인 스택

#include <iostream>
using namespace std;

class Stack {
private:
    int* arr;
    int top;
    int capacity;

public:
    Stack(int size) {
        capacity = size;
        arr = new int[capacity];
        top = -1;
    }

    ~Stack() {
        delete[] arr;
    }

    bool isEmpty() {
        return top == -1;
    }

    bool isFull() {
        return top == capacity - 1;
    }

    void push(int value) {
        if (isFull()) {
            cout << "Stack Overflow!" << endl;
            return;
        }
        arr[++top] = value;
    }

    int pop() {
        if (isEmpty()) {
            cout << "Stack Underflow!" << endl;
            return -1;
        }
        return arr[top--];
    }

    int peek() {
        if (isEmpty()) {
            cout << "Stack is empty!" << endl;
            return -1;
        }
        return arr[top];
    }
};

int main() {
    Stack stack(5);

    stack.push(10);
    stack.push(20);
    stack.push(30);

    cout << "Top element: " << stack.peek() << endl;
    cout << "Popped element: " << stack.pop() << endl;
    cout << "Top element after pop: " << stack.peek() << endl;

    return 0;
}

배열을 이용한 동적 크기 조정 가능한 스택 (크기 변화가 가능하도록 구현)

#include <iostream>
using namespace std;

class DynamicStack {
private:
    int* arr;
    int top;
    int capacity;

public:
    DynamicStack(int size = 2) { // 기본 크기 2
        capacity = size;
        arr = new int[capacity];
        top = -1;
    }

    ~DynamicStack() {
        delete[] arr;
    }

    bool isEmpty() {
        return top == -1;
    }

    bool isFull() {
        return top == capacity - 1;
    }

    void push(int value) {
        if (isFull()) {
            // 배열 크기 두 배로 확장
            int* newArr = new int[capacity * 2];
            for (int i = 0; i < capacity; i++) {
                newArr[i] = arr[i];
            }
            delete[] arr;
            arr = newArr;
            capacity *= 2;
        }
        arr[++top] = value;
    }

    int pop() {
        if (isEmpty()) {
            cout << "Stack Underflow!" << endl;
            return -1;
        }
        return arr[top--];
    }

    int peek() {
        if (isEmpty()) {
            cout << "Stack is empty!" << endl;
            return -1;
        }
        return arr[top];
    }
};

int main() {
    DynamicStack stack;

    stack.push(10);
    stack.push(20);
    stack.push(30);
    stack.push(40);  // 크기 증가

    cout << "Top element: " << stack.peek() << endl;
    cout << "Popped element: " << stack.pop() << endl;
    cout << "Top element after pop: " << stack.peek() << endl;

    return 0;
}

2. 큐(Queue) 구현

기본적인 큐

#include <iostream>
using namespace std;

class Queue {
private:
    int* arr;
    int front;
    int rear;
    int capacity;

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

    ~Queue() {
        delete[] arr;
    }

    bool isEmpty() {
        return front == -1;
    }

    bool isFull() {
        return (rear + 1) % capacity == front;
    }

    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue Overflow!" << endl;
            return;
        }
        if (front == -1) front = 0;
        rear = (rear + 1) % capacity;
        arr[rear] = value;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue Underflow!" << endl;
            return -1;
        }
        int dequeued = arr[front];
        if (front == rear) {
            front = rear = -1; // 큐가 비었을 경우
        } else {
            front = (front + 1) % capacity;
        }
        return dequeued;
    }

    int peek() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        return arr[front];
    }
};

int main() {
    Queue q(5);

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    cout << "Front element: " << q.peek() << endl;
    cout << "Dequeued element: " << q.dequeue() << endl;
    cout << "Front element after dequeue: " << q.peek() << endl;

    return 0;
}

동적 크기 조정 큐

#include <iostream>
using namespace std;

class DynamicQueue {
private:
    int* arr;
    int front;
    int rear;
    int capacity;

public:
    DynamicQueue(int size = 2) { // 기본 크기 2
        capacity = size;
        arr = new int[capacity];
        front = -1;
        rear = -1;
    }

    ~DynamicQueue() {
        delete[] arr;
    }

    bool isEmpty() {
        return front == -1;
    }

    bool isFull() {
        return (rear + 1) % capacity == front;
    }

    void enqueue(int value) {
        if (isFull()) {
            // 배열 크기 두 배로 확장
            int* newArr = new int[capacity * 2];
            int j = 0;
            for (int i = front; i <= rear; i++) {
                newArr[j++] = arr[i % capacity];
            }
            delete[] arr;
            arr = newArr;
            capacity *= 2;
            front = 0;
            rear = j - 1;
        }
        if (front == -1) front = 0;
        rear = (rear + 1) % capacity;
        arr[rear] = value;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue Underflow!" << endl;
            return -1;
        }
        int dequeued = arr[front];
        if (front == rear) {
            front = rear = -1; // 큐가 비었을 경우
        } else {
            front = (front + 1) % capacity;
        }
        return dequeued;
    }

    int peek() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        return arr[front];
    }
};

int main() {
    DynamicQueue q;

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.enqueue(40);  // 크기 증가

    cout << "Front element: " << q.peek() << endl;
    cout << "Dequeued element: " << q.dequeue() << endl;
    cout << "Front element after dequeue: " << q.peek() << endl;

    return 0;
}

(2) 최소값 스택(Min Stack)

이 스택은 추가적으로 현재 스택에서의 최소값을 추적하는 기능을 가집니다.

#include <iostream>
#include <stack>
using namespace std;

class MinStack {
private:
    stack<int> mainStack;
    stack<int> minStack;

public:
    void push(int value) {
        mainStack.push(value);
        if (minStack.empty() || value <= minStack.top()) {
            minStack.push(value);
        }
    }

    int pop() {
        if (mainStack.empty()) {
            cout << "Stack Underflow!" << endl;
            return -1;
        }
        int poppedValue = mainStack.top();
        if (poppedValue == minStack.top()) {
            minStack.pop();
        }
        mainStack.pop();
        return poppedValue;
    }

    int peek() {
        if (mainStack.empty()) {
            cout << "Stack is empty!" << endl;
            return -1;
        }
        return mainStack.top();
    }

    int getMin() {
        if (minStack.empty()) {
            cout << "Stack is empty!" << endl;
            return -1;
        }
        return minStack.top();
    }
};

int main() {
    MinStack stack;
    stack.push(10);
    stack.push(20);
    stack.push(5);
    cout << "Min element: " << stack.getMin() << endl;
    stack.pop();
    cout << "Min element after pop: " << stack.getMin() << endl;

    return 0;
}

(2) 우선순위 큐(Priority Queue)

우선순위 큐는 일반적인 큐와 다르게 데이터를 넣을 때 우선순위가 높은 데이터가 먼저 나오는 큐입니다. 우선순위 큐는 일반적으로 heap을 사용하여 구현됩니다.

여기서는 최대 우선순위 큐를 직접 구현한 예시입니다.

#include <iostream>
#include <vector>
using namespace std;

class PriorityQueue {
private:
    vector<int> heap;

    void heapifyUp(int index) {
        while (index > 0 && heap[index] > heap[(index - 1) / 2]) {
            swap(heap[index], heap[(index - 1) / 2]);
            index = (index - 1) / 2;
        }
    }

    void heapifyDown(int index) {
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;
        int largest = index;

        if (leftChild < heap.size() && heap[leftChild] > heap[largest]) {
            largest = leftChild;
        }

        if (rightChild < heap.size() && heap[rightChild] > heap[largest]) {
            largest = rightChild;
        }

        if (largest != index) {
            swap(heap[index], heap[largest]);
            heapifyDown(largest);
        }
    }

public:
    void enqueue(int value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }

    int dequeue() {
        if (heap.empty()) {
            cout << "Queue Underflow!" << endl;
            return -1;
        }
        int root = heap[0];
        heap[0] = heap[heap.size() - 1];
        heap.pop_back();
        heapifyDown(0);
        return root;
    }

    int peek() {
        if (heap.empty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        return heap[0];
    }
};

int main() {
    PriorityQueue pq;
    pq.enqueue(10);
    pq.enqueue(20);
    pq.enqueue(5);
    cout << "Max element: " << pq.peek() << endl;
    pq.dequeue();
    cout << "Max element after dequeue: " << pq.peek() << endl;

    return 0;
}

(3) 원형 큐(Circular Queue)

원형 큐는 큐에서 데이터를 넣고 뺄 때 배열의 끝에서 처음으로 돌아가서 공간을 재활용하는 큐입니다

#include <iostream>
using namespace std;

class CircularQueue {
private:
    int* arr;
    int front;
    int rear;
    int capacity;

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

    ~CircularQueue() {
        delete[] arr;
    }

    bool isEmpty() {
        return front == -1;
    }

    bool isFull() {
        return (rear + 1) % capacity == front;
    }

    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue Overflow!" << endl;
            return;
        }
        if (front == -1) front = 0;
        rear = (rear + 1) % capacity;
        arr[rear] = value;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue Underflow!" << endl;
            return -1;
        }
        int dequeued = arr[front];
        if (front == rear) {
            front = rear = -1; // 큐가 비었을 경우
        } else {
            front = (front + 1) % capacity;
        }
        return dequeued;
    }

    int peek() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        return arr[front];
    }
};

int main() {
    CircularQueue q(5);

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.enqueue(40);

    cout << "Front element: " << q.peek() << endl;
    q.dequeue();
    cout << "Front element after dequeue: " << q.peek() << endl;

    q.enqueue(50);
    cout << "Front element after enqueue: " << q.peek() << endl;

    return 0;
}

1. 덱(Deque)

덱(Deque)은 "Double-Ended Queue"의 줄임말로, 양쪽 끝에서 삽입과 삭제가 가능한 큐입니다. 덱은 스택처럼 양쪽 끝에서 데이터를 삽입하거나 삭제할 수 있습니다.

#include <iostream>
using namespace std;

class Deque {
private:
    int* arr;
    int front, rear;
    int capacity;

public:
    Deque(int size) {
        capacity = size;
        arr = new int[capacity];
        front = -1;
        rear = 0;
    }

    ~Deque() {
        delete[] arr;
    }

    bool isFull() {
        return (front == 0 && rear == capacity - 1) || (front == rear + 1);
    }

    bool isEmpty() {
        return front == -1;
    }

    void insertFront(int value) {
        if (isFull()) {
            cout << "Deque Overflow!" << endl;
            return;
        }
        if (front == -1) {
            front = 0;
            rear = 0;
        } else if (front == 0) {
            front = capacity - 1;
        } else {
            front--;
        }
        arr[front] = value;
    }

    void insertRear(int value) {
        if (isFull()) {
            cout << "Deque Overflow!" << endl;
            return;
        }
        if (front == -1) {
            front = 0;
            rear = 0;
        } else if (rear == capacity - 1) {
            rear = 0;
        } else {
            rear++;
        }
        arr[rear] = value;
    }

    int deleteFront() {
        if (isEmpty()) {
            cout << "Deque Underflow!" << endl;
            return -1;
        }
        int value = arr[front];
        if (front == rear) {
            front = rear = -1;
        } else if (front == capacity - 1) {
            front = 0;
        } else {
            front++;
        }
        return value;
    }

    int deleteRear() {
        if (isEmpty()) {
            cout << "Deque Underflow!" << endl;
            return -1;
        }
        int value = arr[rear];
        if (front == rear) {
            front = rear = -1;
        } else if (rear == 0) {
            rear = capacity - 1;
        } else {
            rear--;
        }
        return value;
    }

    int getFront() {
        if (isEmpty()) {
            cout << "Deque is empty!" << endl;
            return -1;
        }
        return arr[front];
    }

    int getRear() {
        if (isEmpty()) {
            cout << "Deque is empty!" << endl;
            return -1;
        }
        return arr[rear];
    }
};

int main() {
    Deque dq(5);

    dq.insertRear(10);
    dq.insertRear(20);
    dq.insertFront(5);
    dq.insertFront(2);

    cout << "Front element: " << dq.getFront() << endl;
    cout << "Rear element: " << dq.getRear() << endl;

    dq.deleteRear();
    cout << "Rear element after delete: " << dq.getRear() << endl;

    dq.deleteFront();
    cout << "Front element after delete: " << dq.getFront() << endl;

    return 0;
}

2. 큐를 이용한 스택 (Queue to Stack)

이 구현은 두 개의 큐를 사용하여 스택을 구현하는 방식입니다. enqueue와 dequeue를 적절히 사용하여 큐를 이용한 스택 동작을 만듭니다.

#include <iostream>
#include <queue>
using namespace std;

class StackUsingQueue {
private:
    queue<int> q1, q2;

public:
    void push(int value) {
        q2.push(value);

        while (!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        }

        // 두 큐를 교환하여 q1을 스택처럼 사용
        swap(q1, q2);
    }

    int pop() {
        if (q1.empty()) {
            cout << "Stack Underflow!" << endl;
            return -1;
        }
        int top = q1.front();
        q1.pop();
        return top;
    }

    int peek() {
        if (q1.empty()) {
            cout << "Stack is empty!" << endl;
            return -1;
        }
        return q1.front();
    }
};

int main() {
    StackUsingQueue stack;

    stack.push(10);
    stack.push(20);
    stack.push(30);
    cout << "Top element: " << stack.peek() << endl;
    stack.pop();
    cout << "Top element after pop: " << stack.peek() << endl;

    return 0;
}

3. 스택을 이용한 큐 (Stack to Queue)

스택을 이용하여 큐를 구현하는 방식입니다. 두 개의 스택을 사용하여 enqueue와 dequeue 작업을 처리합니다.

#include <iostream>
#include <stack>
using namespace std;

class QueueUsingStack {
private:
    stack<int> s1, s2;

public:
    void enqueue(int value) {
        s1.push(value);
    }

    int dequeue() {
        if (s1.empty() && s2.empty()) {
            cout << "Queue Underflow!" << endl;
            return -1;
        }

        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }

        int front = s2.top();
        s2.pop();
        return front;
    }

    int peek() {
        if (s1.empty() && s2.empty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }

        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }

        return s2.top();
    }
};

int main() {
    QueueUsingStack q;

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    cout << "Front element: " << q.peek() << endl;
    q.dequeue();
    cout << "Front element after dequeue: " << q.peek() << endl;

    return 0;
}

4. 이중 큐 (Double Queue)

이중 큐는 두 개의 큐를 동시에 사용하여 데이터를 양방향으로 처리할 수 있는 구조입니다.

#include <iostream>
#include <queue>
using namespace std;

class DoubleQueue {
private:
    queue<int> q1, q2;

public:
    void insertFront(int value) {
        q2.push(value);
    }

    void insertRear(int value) {
        q1.push(value);
    }

    int deleteFront() {
        if (q2.empty() && q1.empty()) {
            cout << "Deque Underflow!" << endl;
            return -1;
        }
        if (!q2.empty()) {
            int front = q2.front();
            q2.pop();
            return front;
        }
        int front = q1.front();
        q1.pop();
        return front;
    }

    int deleteRear() {
        if (q2.empty() && q1.empty()) {
            cout << "Deque Underflow!" << endl;
            return -1;
        }
        if (!q1.empty()) {
            int rear = q1.back();
            q1.pop();
            return rear;
        }
        int rear = q2.back();
        q2.pop();
        return rear;
    }

    int peekFront() {
        if (q2.empty() && q1.empty()) {
            cout << "Deque is empty!" << endl;
            return -1;
        }
        if (!q2.empty()) {
            return q2.front();
        }
        return q1.front();
    }

    int peekRear() {
        if (q2.empty() && q1.empty()) {
            cout << "Deque is empty!" << endl;
            return -1;
        }
        if (!q1.empty()) {
            return q1.back();
        }
        return q2.back();
    }
};

int main() {
    DoubleQueue dq;

    dq.insertFront(10);
    dq.insertRear(20);
    dq.insertFront(5);
    dq.insertRear(30);

    cout << "Front element: " << dq.peekFront() << endl;
    cout << "Rear element: " << dq.peekRear() << endl;

    dq.deleteFront();
    cout << "Front element after delete: " << dq.peekFront() << endl;

    dq.deleteRear();
    cout << "Rear element after delete: " << dq.peekRear() << endl;

    return 0;
}

'IT 프로그래밍 > 자료구조' 카테고리의 다른 글

연결리스트 - 스택 큐 구현 (0)	2024.12.15
자료구조 예상문제 3 - 시간복잡도 (0)	2024.12.15
자료구조 예상문제2 - 미로찾기문제 (2)	2024.12.15
자료구조 예상 문제 1 (0)	2024.12.15
자료구조 그룹액티비티7 (0)	2024.12.15

현재글자료구조 - 예상문제 3 스택, 큐, 직접 구현하기

기술 블로그

x5x6, 빈곤의 사회학적 정의, strtok기능, 빈곤 정의, 따배시 강의 요약, 백준2284번, 따배시 강의, 녹색혁명, 빈곤의 원인, 빈곤이란 무엇인가?, 말레이시아 경제, 오블완, 백준 10813, 거듭제곱 구하는 법, 프로그래밍 예제, string 설명, C++, 따배시, 티스토리챌린지, 빈곤이란,

일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

기술 블로그