[Coding Interview University] 큐 : 이론 및 구현

<본 블로그는 코딩인터뷰대학 님의 Git과 서적을 참고해서 공부하며 작성하였습니다 :-)>

 

🫧 큐

: FIFO (First In First Out) 순서

: 큐에 저장되는 항목들은 큐에 추가되는 순서대로 제거된다

• 너비 우선 탐색 (bfs)
  • 처리해야 할 노드의 리스트를 저장하는 용도로 큐 사용
  • 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장
  • 노드를 접근한 순서대로 처리 가능
• 캐시 구현

 

🫧 큐 구현하기

💖 tail 포인터가 있는 연결 리스트를 사용하여 구현하기

➡️ enqueue(value) - tail이 가리키는 곳에 value를 추가한다

int main()
{
    int keys[] = { 1, 2, 3, 4, 5 };
    Queue q;
 
    // 위의 키 삽입
    for (int key: keys) {
        q.enqueue(key);
    }
    return 0;
}

➡️ dequeue() - value를 반환하고 가장 최근에 추가된 원소(front)를 제거한다.

int main()
{
    int keys[] = { 1, 2, 3, 4, 5 };
    Queue q;
 
    // 위의 키 삽입
    for (int key: keys) {
        q.enqueue(key);
    }
 
    cout << q.dequeue() << endl;    // 1을 출력
    cout << q.dequeue() << endl;    // 2를 출력
 
    return 0;
}

➡️ empty()

#include <iostream>
#include <stack>
#include <cstdlib>
using namespace std;
 
// 두 개의 Stack을 사용하여 Queue 구현
class Queue
{
    stack<int> s1, s2;
 
public:
    // Queue에 아이템 추가
    void enqueue(int data)
    {
        // 첫 번째 Stack의 모든 요소를 두 번째 Stack으로 이동
        while (!s1.empty())
        {
            s2.push(s1.top());
            s1.pop();
        }
 
        // 항목을 첫 번째 Stack에 푸시
        s1.push(data);
 
        // 모든 요소를 두 번째 Stack에서 첫 번째 Stack으로 다시 이동합니다.
        while (!s2.empty())
        {
            s1.push(s2.top());
            s2.pop();
        }
    }
 
    // Queue에서 아이템 제거
    int dequeue()
    {
        // 첫 번째 Stack이 비어 있는 경우
        if (s1.empty())
        {
            cout << "Underflow!!";
            exit(0);
        }
 
        // 첫 번째 Stack의 최상위 항목을 반환합니다.
        int top = s1.top();
        s1.pop();
        return top;
    }
};

🧡 고정 길이 배열을 사용하여 구현하기

• enqueue(value) - 사용 가능한 저장 공간의 끝에 item을 추가한다.
• dequeue() - value를 반환하고 가장 최근에 추가된 원소를 제거한다.
• empty()
• full()

 

💛 비용

• a bad implementation using linked list where you enqueue at head and dequeue at tail would be O(n) because you'd need the next to last element, causing a full traversal each dequeue
• enqueue: O(1) (amortized, linked list and array [probing])
• dequeue: O(1) (linked list and array)
• empty: O(1) (linked list and array)