12일차

큐

∙ 큐 (queue)

- 자료구조에서 큐는 데이터를 마치 줄을 세워 늘여 놓듯이 저장하는 선형 자료 구조로서, 선입선출 원리에 따라 삽입과 삭제가 수행된다.

선입선출 (FIFO) : 먼저 들어온 데이터가 먼저 출력됨

- 데이터 삽입은 뒤쪽에서 데이터 삭제는 앞쪽에서 수행되는 리스트

 

 

∙ 큐의 주요 연산

큐의 동작

- enqueue(e) : 큐의 맨 뒤에 있는 원소 e를 추가. push(e)

- dequeue() : 큐의 맨 앞에 있는 원소를 삭제. pop()

- front() : 큐의 맨 앞에있는 원소를 참고. peek()

- empty() : 큐가 비어있으면 true를 반환

- size() : 큐의 원소 개수를 반환

 

 

∙ 배열을 이용한 큐의 구현

- 미리 정해진 크기의 배열을 할당하고, 큐의 앞과 뒤를 나타내는 front와 rear변수를 사용

> equeue(e) : rear 값을 1 증가시키고, 해당 위치(arr [rear])에 e를 대입

> dequeue() : front 값을 1 증가시킴

> front() : arr[front] 값을 반환

 

 

∙ 연결 리스트를 이용한 큐의 구현

- 이중 연결 리스트를 이용하며, 새로 추가한 데이터를 연결 리스트 맨 앞에 삽입하는 방식

> enqueue(e) : push_back(e)

> dequeue() : pop_front()

> front() : header -> next 값을 반환

 

 

∙ 리스트 방식의 큐 소스코드

#include <iostream>
#include <list>

template <typename T>
class Queue
{
public:
    Queue() {}
    
    void enqueue(const T& e) {lst.push_back(e);}
    void dequeue() {lst.pop_front();}
    const T& front() const {return lst.front();}
    
    bool empty() const {return lst.empty();}
    int size() const {return lst.size();}

private:
    std::list<T> lst;
};

using namespace std;

int main()
{
    // 큐 생성
    Queue<int> q;
    
    // 큐에 데이터 삽입
    q.enqueue(10); // (front)10(rear)
    q.enqueue(20); // (front)10, 20(rear)
    q.enqueue(30); // (front)10, 20 ,30(rear)
    
    // 큐에있는 데이터 꺼내기
    q.dequeue(); // (front)20, 30(rear)
    
    // 큐를 하나씩 출력
    while (!q.empty()){
        auto& e = q.front();
        cout << e << endl;
        q.dequeue();
    }
}

 

 

∙ std::queue

- FIFO(First-In First-Out) 방식의 큐 자료 구조를 구현한 컨테이너 어댑터

- 템플릿 매개변수 T는 큐에 저장할 타입을 지정하고, Container에는 내부에서 사용할 컨테이너를 지정

- Container에는 deque 또는 list를 지정할 수 있음

- 주요 멤버 함수

> queue::push(e)

> queue::pop()

> queue::front()

 

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    // 큐 생성
    queue<int> q;
    
    // 큐에 데이터 삽입
    q.push(10);
    q.push(20);
    q.push(30);
    
    // 큐 삭제
    q.pop();
    
    // 큐 데이터 하나씩 출력
    while (!q.empty()){
        auto& e = q.front();
        cout << e << endl;
        q.pop();
    }
}