연결리스트 - 스택 큐 구현

1. 기본 스택 (Stack using Linked List)

스택은 후입선출(LIFO) 방식으로, 연결 리스트를 사용하여 스택을 구현합니다.

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int value) {
        data = value;
        next = nullptr;
    }
};

class Stack {
private:
    Node* top;

public:
    Stack() {
        top = nullptr;
    }

    bool isEmpty() {
        return top == nullptr;
    }

    void push(int value) {
        Node* newNode = new Node(value);
        newNode->next = top;
        top = newNode;
    }

    int pop() {
        if (isEmpty()) {
            cout << "Stack Underflow!" << endl;
            return -1;
        }
        Node* temp = top;
        int poppedValue = top->data;
        top = top->next;
        delete temp;
        return poppedValue;
    }

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

    ~Stack() {
        while (!isEmpty()) {
            pop();
        }
    }
};

int main() {
    Stack stack;
    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;
}

 

 

2. 기본 큐 (Queue using Linked List)

큐는 선입선출(FIFO) 방식으로, 연결 리스트를 사용하여 큐를 구현합니다.

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int value) {
        data = value;
        next = nullptr;
    }
};

class Queue {
private:
    Node* front;
    Node* rear;

public:
    Queue() {
        front = rear = nullptr;
    }

    bool isEmpty() {
        return front == nullptr;
    }

    void enqueue(int value) {
        Node* newNode = new Node(value);
        if (rear == nullptr) {
            front = rear = newNode;
            return;
        }
        rear->next = newNode;
        rear = newNode;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue Underflow!" << endl;
            return -1;
        }
        Node* temp = front;
        int dequeuedValue = front->data;
        front = front->next;
        if (front == nullptr) {
            rear = nullptr;
        }
        delete temp;
        return dequeuedValue;
    }

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

    ~Queue() {
        while (!isEmpty()) {
            dequeue();
        }
    }
};

int main() {
    Queue q;
    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;
}

 

3. 원형 큐 (Circular Queue using Linked List)

원형 큐는 링 버퍼를 이용하여 큐의 마지막 요소와 첫 번째 요소가 연결되도록 구현됩니다.

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int value) {
        data = value;
        next = nullptr;
    }
};

class CircularQueue {
private:
    Node* front;
    Node* rear;

public:
    CircularQueue() {
        front = rear = nullptr;
    }

    bool isEmpty() {
        return front == nullptr;
    }

    void enqueue(int value) {
        Node* newNode = new Node(value);
        if (isEmpty()) {
            front = rear = newNode;
            newNode->next = front;
            return;
        }
        rear->next = newNode;
        rear = newNode;
        rear->next = front;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue Underflow!" << endl;
            return -1;
        }
        int dequeuedValue = front->data;
        if (front == rear) {
            delete front;
            front = rear = nullptr;
        } else {
            Node* temp = front;
            front = front->next;
            rear->next = front;
            delete temp;
        }
        return dequeuedValue;
    }

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

    ~CircularQueue() {
        while (!isEmpty()) {
            dequeue();
        }
    }
};

int main() {
    CircularQueue cq;
    cq.enqueue(10);
    cq.enqueue(20);
    cq.enqueue(30);
    cout << "Front element: " << cq.peek() << endl;
    cout << "Dequeued element: " << cq.dequeue() << endl;
    cout << "Front element after dequeue: " << cq.peek() << endl;
    return 0;
}

 

4. 두 개의 스택을 이용한 큐 (Queue using Two Stacks)

두 개의 스택을 이용해서 큐를 구현하는 방법입니다. Stack 1은 데이터를 입력받고, Stack 2는 데이터를 출력할 때 사용합니다.

#include <iostream>
using namespace std;

class QueueUsingTwoStacks {
private:
    stack<int> stack1, stack2;

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

    int dequeue() {
        if (stack2.empty()) {
            if (stack1.empty()) {
                cout << "Queue Underflow!" << endl;
                return -1;
            }
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int dequeuedValue = stack2.top();
        stack2.pop();
        return dequeuedValue;
    }

    int peek() {
        if (stack2.empty()) {
            if (stack1.empty()) {
                cout << "Queue is empty!" << endl;
                return -1;
            }
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        return stack2.top();
    }
};

int main() {
    QueueUsingTwoStacks q;
    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;
}

 

1.2 최소값을 추적하는 스택 (Stack with Minimum)

이 스택은 최소값을 효율적으로 추적하는 기능을 추가한 구현입니다. 각 스택은 minStack을 추가로 사용하여 최소값을 추적합니다.

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

class StackWithMin {
private:
    struct Node {
        int data;
        int min;
        Node* next;
        Node(int value, int minValue) {
            data = value;
            min = minValue;
            next = nullptr;
        }
    };
    Node* top;

public:
    StackWithMin() {
        top = nullptr;
    }

    bool isEmpty() {
        return top == nullptr;
    }

    void push(int value) {
        int minValue = isEmpty() ? value : std::min(value, top->min);
        Node* newNode = new Node(value, minValue);
        newNode->next = top;
        top = newNode;
    }

    int pop() {
        if (isEmpty()) {
            cout << "Stack Underflow!" << endl;
            return -1;
        }
        Node* temp = top;
        int poppedValue = top->data;
        top = top->next;
        delete temp;
        return poppedValue;
    }

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

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

    ~StackWithMin() {
        while (!isEmpty()) {
            pop();
        }
    }
};

int main() {
    StackWithMin stack;
    stack.push(10);
    stack.push(20);
    stack.push(5);
    stack.push(30);

    cout << "Minimum element: " << stack.getMin() << endl;
    stack.pop();
    cout << "Minimum element after pop: " << stack.getMin() << endl;

    return 0;
}

 

2.3 덱(Deque) (Double Ended Queue using Linked List)

덱은 큐의 양쪽 끝에서 삽입과 삭제가 가능한 자료구조입니다.

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node* prev;
    Node(int value) {
        data = value;
        next = prev = nullptr;
    }
};

class Deque {
private:
    Node* front;
    Node* rear;

public:
    Deque() {
        front = rear = nullptr;
    }

    bool isEmpty() {
        return front == nullptr;
    }

    void enqueueFront(int value) {
        Node* newNode = new Node(value);
        if (isEmpty()) {
            front = rear = newNode;
            return;
        }
        newNode->next = front;
        front->prev = newNode;
        front = newNode;
    }

    void enqueueRear(int value) {
        Node* newNode = new Node(value);
        if (isEmpty()) {
            front = rear = newNode;
            return;
        }
        rear->next = newNode;
        newNode->prev = rear;
        rear = newNode;
    }

    int dequeueFront() {
        if (isEmpty()) {
            cout << "Deque Underflow!" << endl;
            return -1;
        }
        int dequeuedValue = front->data;
        Node* temp = front;
        front = front->next;
        if (front != nullptr) {
            front->prev = nullptr;
        }
        delete temp;
        return dequeuedValue;
    }

    int dequeueRear() {
        if (isEmpty()) {
            cout << "Deque Underflow!" << endl;
            return -1;
        }
        int dequeuedValue = rear->data;
        Node* temp = rear;
        rear = rear->prev;
        if (rear != nullptr) {
            rear->next = nullptr;
        }
        delete temp;
        return dequeuedValue;
    }

    int peekFront() {
        if (isEmpty()) {
            cout << "Deque is empty!" << endl;
            return -1;
        }
        return front->data;
    }

    int peekRear() {
        if (isEmpty()) {
            cout << "Deque is empty!" << endl;
            return -1;
        }
        return rear->data;
    }

    ~Deque() {
        while (!isEmpty()) {
            dequeueFront();
        }
    }
};

int main() {
    Deque dq;
    dq.enqueueRear(10);
    dq.enqueueRear(20);
    dq.enqueueFront(30);
    dq.enqueueFront(40);
    cout << "Front element:

 

1. 스택 관련 구현

1.1 중간값을 추적하는 스택 (Stack with Median)

이 스택은 모든 값의 중간값을 추적하는 기능을 제공합니다. push와 pop 시마다 중간값을 쉽게 구할 수 있도록 구현합니다.

#include <iostream>
#include <stack>
#include <set>

using namespace std;

class StackWithMedian {
private:
    stack<int> mainStack;
    multiset<int> sortedSet;

public:
    void push(int value) {
        mainStack.push(value);
        sortedSet.insert(value);
    }

    int pop() {
        if (mainStack.empty()) {
            cout << "Stack Underflow!" << endl;
            return -1;
        }
        int value = mainStack.top();
        mainStack.pop();
        sortedSet.erase(sortedSet.find(value));
        return value;
    }

    int getMedian() {
        if (mainStack.empty()) {
            cout << "Stack is empty!" << endl;
            return -1;
        }
        auto it = sortedSet.begin();
        advance(it, sortedSet.size() / 2);
        return *it;
    }

    ~StackWithMedian() {
        while (!mainStack.empty()) {
            pop();
        }
    }
};

int main() {
    StackWithMedian stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    cout << "Median: " << stack.getMedian() << endl;
    stack.pop();
    cout << "Median after pop: " << stack.getMedian() << endl;
    return 0;
}

1.2 크기 추적 스택 (Stack with Size Tracking)

이 스택은 각 스택의 크기를 추적합니다.

#include <iostream>
using namespace std;

class StackWithSize {
private:
    struct Node {
        int data;
        Node* next;
        Node(int value) : data(value), next(nullptr) {}
    };
    Node* top;
    int size;

public:
    StackWithSize() : top(nullptr), size(0) {}

    void push(int value) {
        Node* newNode = new Node(value);
        newNode->next = top;
        top = newNode;
        size++;
    }

    int pop() {
        if (top == nullptr) {
            cout << "Stack Underflow!" << endl;
            return -1;
        }
        Node* temp = top;
        int poppedValue = top->data;
        top = top->next;
        delete temp;
        size--;
        return poppedValue;
    }

    int getSize() {
        return size;
    }

    ~StackWithSize() {
        while (top != nullptr) {
            pop();
        }
    }
};

int main() {
    StackWithSize stack;
    stack.push(10);
    stack.push(20);
    cout << "Size of stack: " << stack.getSize() << endl;
    stack.pop();
    cout << "Size of stack after pop: " << stack.getSize() << endl;
    return 0;
}

 

2. 큐 관련 구현

2.1 우선순위 큐 (Priority Queue)

우선순위 큐는 각 항목에 우선순위를 부여하고 우선순위가 높은 항목이 먼저 나가도록 구현됩니다.

cpp

코드 복사

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

class PriorityQueue {
private:
    multiset<pair<int, int>> pq;
    int count;

public:
    PriorityQueue() : count(0) {}

    void enqueue(int value, int priority) {
        pq.insert({priority, count++});
    }

    int dequeue() {
        if (pq.empty()) {
            cout << "Queue Underflow!" << endl;
            return -1;
        }
        auto it = pq.begin();
        int value = it->first;
        pq.erase(it);
        return value;
    }

    bool isEmpty() {
        return pq.empty();
    }
};

int main() {
    PriorityQueue pq;
    pq.enqueue(10, 1);
    pq.enqueue(20, 3);
    pq.enqueue(30, 2);
    cout << "Dequeued: " << pq.dequeue() << endl;
    cout << "Dequeued: " << pq.dequeue() << endl;
    return 0;
}

2.2 슬라이딩 윈도우 최소값을 추적하는 큐 (Queue with Sliding Window Minimum)

슬라이딩 윈도우에서 최소값을 추적하는 큐를 구현합니다. 이 큐는 현재 윈도우에서 최소값을 O(1) 시간에 추출할 수 있도록 합니다.\

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

class SlidingWindowMinQueue {
private:
    deque<int> dq;

public:
    void enqueue(int value) {
        while (!dq.empty() && dq.back() > value) {
            dq.pop_back();
        }
        dq.push_back(value);
    }

    int getMin() {
        return dq.front();
    }

    void dequeue() {
        if (dq.empty()) {
            cout << "Queue Underflow!" << endl;
            return;
        }
        dq.pop_front();
    }

    void print() {
        for (int num : dq) {
            cout << num << " ";
        }
        cout << endl;
    }
};

int main() {
    SlidingWindowMinQueue queue;
    vector<int> nums = {2, 1, 3, 5, 4, 8, 2, 7};
    
    for (int i = 0; i < nums.size(); i++) {
        queue.enqueue(nums[i]);
        if (i >= 3 - 1) {
            cout << "Min of window [" << i - 2 << " to " << i << "]: " << queue.getMin() << endl;
            queue.dequeue();
        }
    }
    return 0;
}

 

3.1 양방향 큐 (Deque)

양쪽에서 삽입과 삭제가 가능하도록 구현한 큐입니다.

#include <iostream>
using namespace std;

class Deque {
private:
    struct Node {
        int data;
        Node* next;
        Node* prev;
        Node(int value) : data(value), next(nullptr), prev(nullptr) {}
    };
    Node* front;
    Node* rear;

public:
    Deque() : front(nullptr), rear(nullptr) {}

    void enqueueFront(int value) {
        Node* newNode = new Node(value);
        if (front == nullptr) {
            front = rear = newNode;
        } else {
            newNode->next = front;
            front->prev = newNode;
            front = newNode;
        }
    }

    void enqueueRear(int value) {
        Node* newNode = new Node(value);
        if (rear == nullptr) {
            front = rear = newNode;
        } else {
            newNode->prev = rear;
            rear->next = newNode;
            rear = newNode;
        }
    }

    int dequeueFront() {
        if (front == nullptr) {
            cout << "Queue Underflow!" << endl;
            return -1;
        }
        int value = front->data;
        Node* temp = front;
        front = front->next;
        if (front != nullptr) {
            front->prev = nullptr;
        }
        delete temp;
        return value;
    }

    int dequeueRear() {
        if (rear == nullptr) {
            cout << "Queue Underflow!" << endl;
            return -1;
        }
        int value = rear->data;
        Node* temp = rear;
        rear = rear->prev;
        if (rear != nullptr) {
            rear->next = nullptr;
        }
        delete temp;
        return value;
    }

    bool isEmpty() {
        return front == nullptr;
    }

    ~Deque() {
        while (!isEmpty()) {
            dequeueFront();
        }
    }
};

int main() {
    Deque dq;
    dq.enqueueFront(10);
    dq.enqueueRear(20);
    dq.enqueueFront(30);
    dq.enqueueRear(40);

    cout << "Dequeued from front