[자료구조] 스택 stack, 큐 queue, 덱 Deque

스택 stack

LIFO구조

Top: 데이터 삽입 될 위치
push: top에 원소 삽입 위치
pop: 원소 삭제 및 변환
peek: top에 있는 원소 반환
DFS

스택 시간 복잡도

• 데이터 삽입/삭제: O(1)
• top 데이터 조회: O(1)
• 특정 데이터 조회: O(n)
  일일이 검색해야해서 오래 걸림

스택 c++ 구현

#include <iostream>
using namespace std;

// 스택 클래스 정의
class Stack {
private:
    int* arr;       // 스택 배열
    int topIndex;   // 스택의 최상단 인덱스
    int capacity;   // 스택의 최대 크기

public:
    // 생성자: 초기 용량 설정
    Stack(int size) {
        capacity = size;
        arr = new int[capacity];
        topIndex = -1; // 스택은 비어 있는 상태
    }

    // 소멸자: 메모리 해제
    ~Stack() {
        delete[] arr;
    }

    // 스택에 요소 추가
    void push(int value) {
        if (topIndex == capacity - 1) {
            cout << "Stack Overflow! Unable to push " << value << endl;
            return;
        }
        arr[++topIndex] = value;
    }

    // 스택에서 요소 제거
    void pop() {
        if (isEmpty()) {
            cout << "Stack Underflow! Nothing to pop." << endl;
            return;
        }
        topIndex--;
    }

    // 스택의 최상단 요소 확인
    int top() {
        if (isEmpty()) {
            cout << "Stack is empty! No top element." << endl;
            return -1; // 오류 값
        }
        return arr[topIndex];
    }

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

    // 스택의 현재 크기 확인
    int size() {
        return topIndex + 1;
    }
};

int main() {
    Stack s(5); // 최대 크기 5인 스택 생성

    // 테스트
    s.push(10);
    s.push(20);
    s.push(30);

    cout << "Top element: " << s.top() << endl;

    s.pop();
    cout << "After popping, top element: " << s.top() << endl;

    s.push(40);
    cout << "Current size of stack: " << s.size() << endl;

    // 스택이 비었는지 확인
    while (!s.isEmpty()) {
        cout << "Popping: " << s.top() << endl;
        s.pop();
    }

    cout << "Stack is empty: " << (s.isEmpty() ? "Yes" : "No") << endl;

    return 0;
}

큐 Queue

FIFO

끝(Rear)에서 요소를 추가하는 작업을 enqueue
맨 앞(Front)에서 요소를 제거하는 작업을 dequeue

가득 찬 큐에 요소를 추가하려고 할 때 Overflow
빈 큐에 요소를 삭제하려 하면 UnderFlow

enqueue() - 큐에 끝(rear)에 항목을 추가
dequeue() - 큐에 맨 앞(front)에 항목을 제거
peek() - 큐에 맨 앞(front)에 있는 항목을 반환
isfull() - 큐가 가득 찼는지 확인
isempty() - 큐가 비어 있는지 확인

BFS

큐 시간 복잡도

• 데이터 삽입/삭제: O(1)
• front 데이터 조회: O(1)
• 특정 데이터 조회: O(n)
  일일이 검색해야해서 오래 걸림

queue c++ 구현

#include <iostream>
using namespace std;

// 선형 큐 클래스 정의
class LinearQueue {
private:
    int* arr;       // 큐 배열
    int frontIndex; // 큐의 맨 앞 인덱스
    int rearIndex;  // 큐의 맨 뒤 인덱스
    int capacity;   // 큐의 최대 크기

public:
    // 생성자: 초기 용량 설정
    LinearQueue(int size) {
        capacity = size;
        arr = new int[capacity];
        frontIndex = -1; // 초기 상태는 큐가 비어 있음
        rearIndex = -1;  // 초기 상태는 큐가 비어 있음
    }

    // 소멸자: 메모리 해제
    ~LinearQueue() {
        delete[] arr;
    }

    // 큐에 요소 삽입
    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue Overflow! Unable to enqueue " << value << endl;
            return;
        }
        if (isEmpty()) {
            frontIndex = 0; // 첫 번째 삽입 시 front를 0으로 설정
        }
        arr[++rearIndex] = value; // rearIndex 증가 후 값 삽입
    }

    // 큐에서 요소 제거
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue Underflow! Nothing to dequeue." << endl;
            return;
        }
        cout << "Dequeuing: " << arr[frontIndex] << endl;
        frontIndex++;
        // 모든 요소를 제거한 경우 큐 초기화
        if (frontIndex > rearIndex) {
            frontIndex = -1;
            rearIndex = -1;
        }
    }

    // 큐의 맨 앞 요소 확인
    int front() {
        if (isEmpty()) {
            cout << "Queue is empty! No front element." << endl;
            return -1; // 오류 값
        }
        return arr[frontIndex];
    }

    // 큐의 맨 뒤 요소 확인
    int rear() {
        if (isEmpty()) {
            cout << "Queue is empty! No rear element." << endl;
            return -1; // 오류 값
        }
        return arr[rearIndex];
    }

    // 큐가 비었는지 확인
    bool isEmpty() {
        return frontIndex == -1;
    }

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

    // 큐의 현재 크기 확인
    int size() {
        if (isEmpty()) return 0;
        return rearIndex - frontIndex + 1;
    }
};

int main() {
    LinearQueue q(5); // 최대 크기 5인 선형 큐 생성

    // 테스트
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    cout << "Front element: " << q.front() << endl;
    cout << "Rear element: " << q.rear() << endl;

    q.dequeue();
    cout << "After dequeue, front element: " << q.front() << endl;

    q.enqueue(40);
    q.enqueue(50);
    q.enqueue(60); // 큐가 가득 차면 enqueue 불가

    cout << "Current size of queue: " << q.size() << endl;

    // 큐가 비었는지 확인
    while (!q.isEmpty()) {
        cout << "Dequeuing: " << q.front() << endl;
        q.dequeue();
    }

    cout << "Queue is empty: " << (q.isEmpty() ? "Yes" : "No") << endl;

    return 0;
}

덱 Deque

Queue 와 Stack 의 특징을 동시에 갖고 있음
Overflow와 UnderFlow 또한 둘 다 갖고 있음

deque.removeFirst(); //덱의 앞쪽에 있는 데이터 삭제
단, 덱이 비어 있으면 NoSuchElementException 발생

deque.removeLast();  //덱의 앞쪽에 있는 데이터 삭제
단, 덱이 비어 있으면 NoSuchElementException 발생

deque.remove(); //덱의 앞쪽에 있는 데이터 삭제
단, 덱이 비어 있으면 NoSuchElementException 발생

deque.pollFirst(); //덱의 앞쪽에 있는 데이터 삭제
단, 덱이 비어 있으면 null 반환

deque.pollLast(); //덱의 뒷쪽에 있는 데이터 삭제
단, 덱이 비어 있으면 null 반환

deque.poll(); //덱의 앞쪽에 있는 데이터 삭제
단, 덱이 비어 있으면 null 반환

Object getFirst(); //덱의 앞쪽에 있는 데이터 가지고 옴
단, 덱이 비어 있으면 NoSuchElementException 발생

Object peek(); //덱의 앞쪽에 있는 데이터 가지고 옴
단, 덱이 비어 있으면 null 반환

Object peekFirst(); //덱의 앞쪽에 있는 데이터 가지고 옴
단, 덱이 비어 있으면 null 반환

Object getLast(); //덱의 뒷쪽에 있는 데이터 가지고 옴
단, 덱이 비어 있으면 NoSuchElementException 발생

Object peekLast(); //덱의 뒷쪽에 있는 데이터 삭제
단, 덱이 비어 있으면 null 반환

deque c++ 코드 구현

#include <iostream>
using namespace std;

// 선형 덱 클래스 정의
class LinearDeque {
private:
    int* arr;       // 덱 배열
    int frontIndex; // 덱의 맨 앞 인덱스
    int rearIndex;  // 덱의 맨 뒤 인덱스
    int capacity;   // 덱의 최대 크기

public:
    // 생성자: 초기 용량 설정
    LinearDeque(int size) {
        capacity = size;
        arr = new int[capacity];
        frontIndex = -1; // 초기 상태는 덱이 비어 있음
        rearIndex = -1;  // 초기 상태는 덱이 비어 있음
    }

    // 소멸자: 메모리 해제
    ~LinearDeque() {
        delete[] arr;
    }

    // 덱이 비었는지 확인
    bool isEmpty() {
        return frontIndex == -1;
    }

    // 덱이 가득 찼는지 확인
    bool isFull() {
        return rearIndex == capacity - 1;
    }

    // 앞쪽에 요소 삽입
    void pushFront(int value) {
        if (isFull() || frontIndex == 0) {
            cout << "Deque Overflow! Unable to push " << value << " at front." << endl;
            return;
        }
        if (isEmpty()) {
            frontIndex = 0;
            rearIndex = 0;
        } else {
            frontIndex--;
        }
        arr[frontIndex] = value;
    }

    // 뒤쪽에 요소 삽입
    void pushBack(int value) {
        if (isFull()) {
            cout << "Deque Overflow! Unable to push " << value << " at back." << endl;
            return;
        }
        if (isEmpty()) {
            frontIndex = 0;
            rearIndex = 0;
        } else {
            rearIndex++;
        }
        arr[rearIndex] = value;
    }

    // 앞쪽 요소 제거
    void popFront() {
        if (isEmpty()) {
            cout << "Deque Underflow! Nothing to pop from front." << endl;
            return;
        }
        if (frontIndex == rearIndex) {
            frontIndex = -1;
            rearIndex = -1;
        } else {
            frontIndex++;
        }
    }

    // 뒤쪽 요소 제거
    void popBack() {
        if (isEmpty()) {
            cout << "Deque Underflow! Nothing to pop from back." << endl;
            return;
        }
        if (frontIndex == rearIndex) {
            frontIndex = -1;
            rearIndex = -1;
        } else {
            rearIndex--;
        }
    }

    // 앞쪽 요소 확인
    int front() {
        if (isEmpty()) {
            cout << "Deque is empty! No front element." << endl;
            return -1; // 오류 값
        }
        return arr[frontIndex];
    }

    // 뒤쪽 요소 확인
    int back() {
        if (isEmpty()) {
            cout << "Deque is empty! No back element." << endl;
            return -1; // 오류 값
        }
        return arr[rearIndex];
    }

    // 현재 덱 크기
    int size() {
        if (isEmpty()) return 0;
        return rearIndex - frontIndex + 1;
    }
};

int main() {
    LinearDeque dq(5); // 최대 크기 5인 선형 덱 생성

    // 테스트
    dq.pushBack(10);
    dq.pushFront(20);
    dq.pushBack(30);

    cout << "Front element: " << dq.front() << endl; // 출력: 20
    cout << "Back element: " << dq.back() << endl;   // 출력: 30

    dq.popFront();
    cout << "After popFront, front element: " << dq.front() << endl; // 출력: 10

    dq.pushFront(40);
    dq.popBack();
    cout << "After popBack, back element: " << dq.back() << endl;   // 출력: 10

    cout << "Current size of deque: " << dq.size() << endl; // 출력: 2

    // 덱의 요소를 모두 제거
    while (!dq.isEmpty()) {
        cout << "Removing front: " << dq.front() << endl;
        dq.popFront();
    }

    cout << "Deque is empty: " << (dq.isEmpty() ? "Yes" : "No") << endl;

    return 0;
}