1장 큐와 std::queue
1. 큐
가. 큐(queue)란?
- queue: 땋아 늘인 머리. 대기열. 줄을 서다.
- 자료구조에서 큐는 데이터를 마치 줄을 세워 늘여 놓듯이 저장하는 선형 자료 구조로서,
선입선출 원리에 따라 삽입과 삭제가 수행됨 - 선입선출: 먼저 들어온 데이터가 먼저 출력됨. FIFO (First-In First-Out)
- 데이터 삽입은 뒤쪽(rear)에서, 데이터 삭제는 앞쪽(front)에서 수행되는 리스트
2. 큐의 주요 연산
- enqueue(e): 큐의 맨 뒤(rear)에 원소 e를 추가. push(e). (삽입)
- dequeue(): 큐의 맨 앞에 있는 원소를 삭제. pop(). (삭제)
- front(): 큐의 맨 앞(front)에 있는 원소를 참조. peak().
- empty(): 큐가 비어 있으면 true를 반환
- size(): 큐의 원소 개수를 반환
3. 큐의 동작
- enqueue(10) : 10 삽입
- enqueue(20) : 20 삽입
- enqueue(30) : 30 삽입
- dequeue() : 10 삭제
- front() : 20
- enqueue(40) : 40 삽입
4. 스택과 큐
가. 스택과 큐의 동작 비교
- 스택: top 이 아웃됨
- 큐: front가 아웃됨
5. 큐의 구현
가. 배열을 이용한 큐의 구현
- 미리 정해진 크기의 배열을 할당하고, 큐의 앞과 뒤를 나타내는 front와 rear 변수를 사용
- enqueue(e): rear 값을 1 증가시키고, 해당 위치 (arr[rear])에 e를 대입
- dequeue(): front값을 1 증가시킴
- front(): arr[front] 값을 반환
나. 연결 리스트를 이용한 큐의 구현
- 이중 연결 리스트를 이용하여, 새로 추가한 데이터를 연결 리스트 맨 앞에 삽입하는 방식
- enqueue(e): push_back(e)
- dequeue(): pop_front()
- front(): header -> next 값을 반환
다. std::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;
};
라. 구현한 Queue 클래스 동작 확인
#include <iostream>
#include <list>
using namespace std;
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;
};
int main()
{
Queue<int> q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.dequeue();
cout << q.front() << endl;
q.enqueue(40);
while (!q.empty()) {
auto& e = q.front();
cout << e << ", ";
q.dequeue();
}
cout << endl;
}
6. std::queue
가. std::queue
- FIFO(First-In First-Out)방식의 큐 자료구조를 구현한 컨테이너 어댑터
template<class T, class Container = std::deque<T>>
class queue; - 템플릿 매개변수 T는 큐에 저장할 타입을 지정하고, Container 에는 내부에서 사용할 컨테이너를 지정
- Container에는 dequeue 또는 list를 지정할 수 있음
- <queue>에 정의되어 있음
- 주요 멤버 함수
- queue::push(e)
- queue::pop()
- queue::front()
나. std::queue 사용 예제
#include <iostream>
#include <queue>
using namespace std;
int main()
{
queue<int> q;
q.push(10);
q.push(20);
q.push(30);
q.pop();
cout << q.front() << endl;
q.push(40);
while (!q.empty()) {
auto& e = q.front();
cout << e << ", ";
q.pop();
}
cout << endl;
}
2장 환형 큐
1. 배열을 이용한 큐의 구현
가. 배열을 이용하여 구현한 큐의 문제점
- 큐에 데이터의 삽입과 삭제가 지속적으로 발생할 경우, 배열의 앞 부분에 무효화되는 공간이 늘어남
2. 환형 큐 (배열을 이용한 큐의 단점 보완 위해서)
가. 환형 큐(circular queue)란?
- 선입선출(FIFO) 원칙에 따라 작업이 수행되고, 마지막 위치가 마치 원을 이루듯이 다시 첫 번째 위치에 연결되는 선형 데이터 구조. 원형 큐.
- 큐의 front와 rear 값이 시계 방향으로 한 칸 씩 이동하는 형태
- 실제 구현에서는 배열 전체의 크기를 이용하여 나머지(%) 연산을 수행
- 큐가 empty 또는 full 상태인지를 확인하기 위해 원소의 개수를 따로 저장해야 함.
나. 환형 큐에서 데이터 추가
rear = (rear + 1) % capacity;
arr[rear] = e;
cout++;
다. 환형 큐에서 데이터 삭제: dequeue()
라. 환형 큐의 구현
#include <iostream>
#define MAX_QUEUE 10
using namespace std;
template <typename T>
class CircularQueue
{
public:
CircularQueue(int sz = MAX_QUEUE)
{
arr = new T[sz];
capacity = sz;
count = 0;
front_idx = 0;
rear_idx = -1;
}
~CircularQueue()
{
delete [] arr;
}
void enqueue(const T& e)
{
if (full()) {
std::cout << "Overflow error!" << std::endl;
return;
}
rear_idx = (rear_idx + 1) % capacity;
arr[rear_idx] = e;
count++;
}
void dequeue()
{
if (empty()) {
std::cout << "Underflow error!" << std::endl;
return;
}
front_idx = (front_idx + 1) % capacity;
count--;
}
const T& front() const { return arr[front_idx]; }
bool empty() const { return count == 0; }
int full() const { return count == capacity; }
int size() const { return count; }
private:
T& arr;
int front_idx;
int rear_idx;
int count;
int capacity;
};
마. 구현한 CircularQueue 클래스 동작 확인
int main()
{
CircularQueue<int> q(5);
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.enqueue(40);
q.enqueue(50); // full 상태
q.dequeue();
q.dequeue(); // 원소 2개 삭제
q.enqueue(60);
q.enqueue(70); // full 상태
q.enqueue(80); // 오버플로우 에러
while (!q.empty()) {
auto& e = q.front();
cout << e << ", ";
q.dequeue();
}
}
3장 양방향 큐와 std::deque
1. 양방향 큐
가. 양방향 큐(deque)란?
- deque: Double Ended Queue
- 삽입과 삭제가 양쪽 끝에서 모두 가능한 자료구조
나. 양방향 큐의 주요 연산
- push_front(e) : 양방향 큐의 맨 앞에 원소 e를 추가
- pop_front(): 양방향 큐의 맨 앞에 있는 원소를 삭제
- push_back(e): 양방향 큐의 맨 뒤에 있는 원소 e를 추가
- pop_back() : 양방향 큐의 맨 뒤에 있는 원소를 삭제
- front() : 양방향 큐의 맨 앞에 있는 원소를 참조
- back(): 양방향 큐의 맨 뒤에 있는 원소를 참조
- empty() : 양방향 큐가 비어 있으면 true를 반환
- size() : 양방향 큐의 원소 개수를 반환
2. 양방향 큐의 구현
가. 배열을 이용한 양방향 큐의 구현
- 환형 큐와 비슷한 방식으로, 양방향 큐의 맨 앞과 맨 마지막 위치를 갱신
나. 연결 리스트를 이용한 양방향 큐의 구현
- 이중 연결 리스트를 이용하여 연결 리스트의 맨 앞과 맨 뒤에 자료를 각각 추가 & 삭제 가능
3. std::deque
가. std::deque
- template<class T, class Allocator = std::allocator<T>>
class deque; - 양방향 큐의 동작을 지원하는 순차 컨테이너
- <deque>에 정의되어 있음
- std::deque의 특징
- 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작
- 맨 앞과 맨 뒤에 자료를 추가 또는 삭제하는 연산이 O(1) 시간 복잡도로 동작
- 중간 위치에서 자료를 삽입 또는 삭제하는 O(n) 시간 복잡도로 동작 (n은 원소 개수)
- std::stack, std::queue 등의 STL 컨테이너 어댑터의 기본 컨테이너로 사용
나. std::deque의 구현 방식
- C++ 표준은 어떤 기능의 동작만을 정의할 뿐이며, 어떻게 구현해야 하는지는 정의하지 않음
- 보통 std::deque은 단인 메모리 청크(chunk)를 사용하지 않으며, 대신 크기가 같은 여러 개의
메모리 청크를 사용하여 데이터를 저장함
다. std::deque 사용 예제
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> d = {10, 20, 30, 40};
d.push_front(50);
d.push_back(60);
for (int i = 0; i < d.size(); i++) {
cout << d[i] << ", ";
}
cout << endl;
}
'3학년 > 자료구조와 알고리즘 스터디' 카테고리의 다른 글
| [자료구조와 알고리즘] 6장 재귀 (1) | 2023.05.21 |
|---|---|
| [자료구조와 알고리즘] 4장 스택 (1) | 2023.05.09 |
| [자료구조와 알고리즘] 3장 연결 리스트 (0) | 2023.04.11 |
| [자료구조와 알고리즘] 2장 배열: C에서 C++로 (0) | 2023.04.02 |
| [자료구조와 알고리즘] 1주차 개요, 시간 복잡도 (1) | 2023.03.26 |
