자료구조/C++

큐 (Queue)

니푸 2023. 4. 13. 01:22

✔️ Queue

  • 먼저 들어온 것이 먼저 나간다.
  • First in Firt out (FIFO) order
  • 마트에서 줄을 서는 경우와 비슷하다.
  • 큐에서는 데이터를 넣고 뺴는 방향이 한 쪽 이였지만 큐는 앞뒤로 방향이 두 군데다.
  • 데이터를 뒤에 넣는 rear, 데이터를 앞에서부터 빼는 front 변수 두가지를 사용한다.
  • Array, Linked List 두가지로 구현 가능하다.
  • 오늘 강의에서는 주로 Array를 이용한다.
  • 깊이우선탐색은 스택, 너비우선탐색은 큐와 관련이 있다.

Queue ADT

  • 데이터를 넣고 빼고 비어있는가, 차있는가를 확인(스택과 비슷)
  • 스택과의 차이점은 데이터를 넣을때는 앞에서, 뺄때는 뒤에서 뺀다.
  • Push, Pop과 가르게 Insert(Enqueue), Delete(Dequeue) 사용
  • 데이터를 옅보는 Peek

Queue Implementation

  • Overflow: IsFull, 찼는데 Insert
  • Underflow: IsEmpty, 비었는데 Delete, Peek
  • front와 rear의 초기화는 Stack과 비슷
  • Stack은 앞은 고정, top 포인터만 있으면 가능하지만 Queue front를 고정하고 shift 하거나 front와 rear 둘다 움직인다. 두번째 경우가 더 간단하다.
  • Circlular Buffer: 양 쪽 끝이 이어져있다. 구현 방법이 다르다
  • PrintBuffer: 자료구조에서 유의미하다기 보단 구현이 잘 되고 있는지 확인하는 용도
  • <Queue.h>
class Queue{
	...
  void Insert(Data d);
  Data Delete();
  Data Peek();
  bool IsEmpty();
  bool IsFull();
  void PrintQueue();
  void PeintBuffer(); //print circular buffer 물리적으로 실제 저장된 값 프린트
	int Length();
};

Queue Resizable

  • Queue의 사이즈를 정할 필요가 있다.
  • Dynammic한 표현 필요
class QueueResizable{
	Data* data;
	int front, rear;
	int length;
	int queueSize;
	...
};

Queue Template

  • 다른 자료주고와 마찬가지로 generic하게 Template을 많이 사용
  • 위의 Queue 코드와 중요한 차이점은 template <typename Data> 추가

QueueApplications

  • Printer Buffer
  • Hot Pdtato Game: 폭탄 돌리기 게임
  • Queue for Student Info: Stack에서도 사용. 차이점은 먼저 입력한 학생 먼저 출력
  • Breath First Search: 너비 우선 탐색, Stack의 깊이 우선 탐색 코드에서 Queue를 사용하면 너비 우선 탐색
  • Radix Sort
    • 귀소 정렬
    • 비교정렬이 아님
    • 비교없이 Loop를 돌기 때문에 복잡도가 작아짐
  • Bank simulation: Stack에는 Sever Customer 가 많이 나오고 Queue에는 Bank Customoer 가 많이 나온다.

Double - Ended Queue

  • 줄여서 Deque 이라고 한다.
  • Queue를 좀 더 일반화
  • 데이터를 집어넣고 빼는게 앞에서 넣고 뺼수도, 뒤에서 넣고 뺄수도 있다. 즉 front와 rear에서 넣고 빼기가 가능
  • 원래는 Deque가 더 일반적이기 때문에 Deque에서 상속한다. 이 강의에서는 앞에서 Queue를 설명했기 때문에 Queue에서 상속 할 것이다.

  • Stack은 넣은 곳에서 빼고 Deque는 넣은 쪽의 반대에서 뺀다.
  • front는 먼저 읽고 rear는 나중에 읽는다.
  • front는 추가할 때 더 앞에 추가하고 rear는 더 뒤에 추가.
  • Queue와 마찬가지로 Circular Buffer에서 구현 가능
class Deque{
	...
	void InsertFront(Data d);
	void InsertRear(Data d);
  Data DeleteFront();
	Data DeleteRear();
  Data PeekFront();
	Data PeekRear();
  // bool IsEmpty() inherited
  // bool IsFull() inherited
  // void PrintQueue() inherited
  // void PeintBuffer() inherited
	// int Length() inherited
};
  • PirntQueue - logical, 값
  • PrintBuffer - Physical, 위치
  • <Deque.h>
class Deque : Queue{ // 상속
public:
	Deque() {rear = QUEUE_SIZE-1;}
  void InsertFront(Data d); // cpp에서 정의
	void InsertRear(Data d){Insert(d);}
  Data DeleteFront(){return Delete();}
	Data DeleteRear(); // cpp에서 정의
  Data PeekFront();{return Peek();}
	Data PeekRear(); // cpp에서 정의
	// bool IsEmpty() inherited
  // bool IsFull() inherited
  // void PrintQueue() inherited
  // void PeintBuffer() inherited
	// int Length() inherited
};

Double - Ended Queue Applications

  • Palindrome: 앞에서 읽거나 뒤에서 읽거나 똑같다.
  • Stack with Limited Depth: 웹브라우저 같은 곳에서 동작을 뒤로 돌아갈 때 갯수가 정해져 있는 경우 사용. 가장 오래된 데이터를 지운다.
  • Queue with Two Servers: 은행직원 즉, 서버가 두명일 때. 줄을 두개 서고 줄이 더 짧은 곳에 선다.

✔️ Queue

  • 먼저 들어온 것이 먼저 나간다.
  • First in Firt out (FIFO) order
  • 마트에서 줄을 서는 경우와 비슷하다.
  • 큐에서는 데이터를 넣고 뺴는 방향이 한 쪽 이였지만 큐는 앞뒤로 방향이 두 군데다.
  • 데이터를 뒤에 넣는 rear, 데이터를 앞에서부터 빼는 front 변수 두가지를 사용한다.
  • Array, Linked List 두가지로 구현 가능하다.
  • 오늘 강의에서는 주로 Array를 이용한다.
  • 깊이우선탐색은 스택, 너비우선탐색은 큐와 관련이 있다.

Queue ADT

  • 데이터를 넣고 빼고 비어있는가, 차있는가를 확인(스택과 비슷)
  • 스택과의 차이점은 데이터를 넣을때는 앞에서, 뺄때는 뒤에서 뺀다.
  • Push, Pop과 가르게 Insert(Enqueue), Delete(Dequeue) 사용
  • 데이터를 옅보는 Peek

Queue Implementation

  • Overflow: IsFull, 찼는데 Insert
  • Underflow: IsEmpty, 비었는데 Delete, Peek
  • front와 rear의 초기화는 Stack과 비슷
  • Stack은 앞은 고정, top 포인터만 있으면 가능하지만 Queue front를 고정하고 shift 하거나 front와 rear 둘다 움직인다. 두번째 경우가 더 간단하다.
  • Circlular Buffer: 양 쪽 끝이 이어져있다. 구현 방법이 다르다
  • PrintBuffer: 자료구조에서 유의미하다기 보단 구현이 잘 되고 있는지 확인하는 용도
  • <Queue.h>
class Queue{
	...
  void Insert(Data d);
  Data Delete();
  Data Peek();
  bool IsEmpty();
  bool IsFull();
  void PrintQueue();
  void PeintBuffer(); //print circular buffer 물리적으로 실제 저장된 값 프린트
	int Length();
};

Queue Resizable

  • Queue의 사이즈를 정할 필요가 있다.
  • Dynammic한 표현 필요
class QueueResizable{
	Data* data;
	int front, rear;
	int length;
	int queueSize;
	...
};

Queue Template

  • 다른 자료주고와 마찬가지로 generic하게 Template을 많이 사용
  • 위의 Queue 코드와 중요한 차이점은 template <typename Data> 추가

QueueApplications

  • Printer Buffer
  • Hot Pdtato Game: 폭탄 돌리기 게임
  • Queue for Student Info: Stack에서도 사용. 차이점은 먼저 입력한 학생 먼저 출력
  • Breath First Search: 너비 우선 탐색, Stack의 깊이 우선 탐색 코드에서 Queue를 사용하면 너비 우선 탐색
  • Radix Sort
    • 귀소 정렬
    • 비교정렬이 아님
    • 비교없이 Loop를 돌기 때문에 복잡도가 작아짐
  • Bank simulation: Stack에는 Sever Customer 가 많이 나오고 Queue에는 Bank Customoer 가 많이 나온다.

Double - Ended Queue

  • 줄여서 Deque 이라고 한다.
  • Queue를 좀 더 일반화
  • 데이터를 집어넣고 빼는게 앞에서 넣고 뺼수도, 뒤에서 넣고 뺄수도 있다. 즉 front와 rear에서 넣고 빼기가 가능
  • 원래는 Deque가 더 일반적이기 때문에 Deque에서 상속한다. 이 강의에서는 앞에서 Queue를 설명했기 때문에 Queue에서 상속 할 것이다.
  • Stack은 넣은 곳에서 빼고 Deque는 넣은 쪽의 반대에서 뺀다.
  • front는 먼저 읽고 rear는 나중에 읽는다.
  • front는 추가할 때 더 앞에 추가하고 rear는 더 뒤에 추가.
  • Queue와 마찬가지로 Circular Buffer에서 구현 가능
class Deque{
	...
	void InsertFront(Data d);
	void InsertRear(Data d);
  Data DeleteFront();
	Data DeleteRear();
  Data PeekFront();
	Data PeekRear();
  // bool IsEmpty() inherited
  // bool IsFull() inherited
  // void PrintQueue() inherited
  // void PeintBuffer() inherited
	// int Length() inherited
};
  • PirntQueue - logical, 값
  • PrintBuffer - Physical, 위치
  • <Deque.h>
class Deque : Queue{ // 상속
public:
	Deque() {rear = QUEUE_SIZE-1;}
  void InsertFront(Data d); // cpp에서 정의
	void InsertRear(Data d){Insert(d);}
  Data DeleteFront(){return Delete();}
	Data DeleteRear(); // cpp에서 정의
  Data PeekFront();{return Peek();}
	Data PeekRear(); // cpp에서 정의
	// bool IsEmpty() inherited
  // bool IsFull() inherited
  // void PrintQueue() inherited
  // void PeintBuffer() inherited
	// int Length() inherited
};

Double - Ended Queue Applications

  • Palindrome: 앞에서 읽거나 뒤에서 읽거나 똑같다.
  • Stack with Limited Depth: 웹브라우저 같은 곳에서 동작을 뒤로 돌아갈 때 갯수가 정해져 있는 경우 사용. 가장 오래된 데이터를 지운다.
  • Queue with Two Servers: 은행직원 즉, 서버가 두명일 때. 줄을 두개 서고 줄이 더 짧은 곳에 선다.

✔️ Queue

  • 먼저 들어온 것이 먼저 나간다.
  • First in Firt out (FIFO) order
  • 마트에서 줄을 서는 경우와 비슷하다.
  • 큐에서는 데이터를 넣고 뺴는 방향이 한 쪽 이였지만 큐는 앞뒤로 방향이 두 군데다.
  • 데이터를 뒤에 넣는 rear, 데이터를 앞에서부터 빼는 front 변수 두가지를 사용한다.
  • Array, Linked List 두가지로 구현 가능하다.
  • 오늘 강의에서는 주로 Array를 이용한다.
  • 깊이우선탐색은 스택, 너비우선탐색은 큐와 관련이 있다.

Queue ADT

  • 데이터를 넣고 빼고 비어있는가, 차있는가를 확인(스택과 비슷)
  • 스택과의 차이점은 데이터를 넣을때는 앞에서, 뺄때는 뒤에서 뺀다.
  • Push, Pop과 가르게 Insert(Enqueue), Delete(Dequeue) 사용
  • 데이터를 옅보는 Peek

Queue Implementation

  • Overflow: IsFull, 찼는데 Insert
  • Underflow: IsEmpty, 비었는데 Delete, Peek
  • front와 rear의 초기화는 Stack과 비슷
  • Stack은 앞은 고정, top 포인터만 있으면 가능하지만 Queue front를 고정하고 shift 하거나 front와 rear 둘다 움직인다. 두번째 경우가 더 간단하다.
  • Circlular Buffer: 양 쪽 끝이 이어져있다. 구현 방법이 다르다
  • PrintBuffer: 자료구조에서 유의미하다기 보단 구현이 잘 되고 있는지 확인하는 용도
  • <Queue.h>
class Queue{
	...
  void Insert(Data d);
  Data Delete();
  Data Peek();
  bool IsEmpty();
  bool IsFull();
  void PrintQueue();
  void PeintBuffer(); //print circular buffer 물리적으로 실제 저장된 값 프린트
	int Length();
};

Queue Resizable

  • Queue의 사이즈를 정할 필요가 있다.
  • Dynammic한 표현 필요
class QueueResizable{
	Data* data;
	int front, rear;
	int length;
	int queueSize;
	...
};

Queue Template

  • 다른 자료주고와 마찬가지로 generic하게 Template을 많이 사용
  • 위의 Queue 코드와 중요한 차이점은 template <typename Data> 추가

QueueApplications

  • Printer Buffer
  • Hot Pdtato Game: 폭탄 돌리기 게임
  • Queue for Student Info: Stack에서도 사용. 차이점은 먼저 입력한 학생 먼저 출력
  • Breath First Search: 너비 우선 탐색, Stack의 깊이 우선 탐색 코드에서 Queue를 사용하면 너비 우선 탐색
  • Radix Sort
    • 귀소 정렬
    • 비교정렬이 아님
    • 비교없이 Loop를 돌기 때문에 복잡도가 작아짐
  • Bank simulation: Stack에는 Sever Customer 가 많이 나오고 Queue에는 Bank Customoer 가 많이 나온다.

Double - Ended Queue

  • 줄여서 Deque 이라고 한다.
  • Queue를 좀 더 일반화
  • 데이터를 집어넣고 빼는게 앞에서 넣고 뺼수도, 뒤에서 넣고 뺄수도 있다. 즉 front와 rear에서 넣고 빼기가 가능
  • 원래는 Deque가 더 일반적이기 때문에 Deque에서 상속한다. 이 강의에서는 앞에서 Queue를 설명했기 때문에 Queue에서 상속 할 것이다.
  • Stack은 넣은 곳에서 빼고 Deque는 넣은 쪽의 반대에서 뺀다.
  • front는 먼저 읽고 rear는 나중에 읽는다.
  • front는 추가할 때 더 앞에 추가하고 rear는 더 뒤에 추가.
  • Queue와 마찬가지로 Circular Buffer에서 구현 가능
class Deque{
	...
	void InsertFront(Data d);
	void InsertRear(Data d);
  Data DeleteFront();
	Data DeleteRear();
  Data PeekFront();
	Data PeekRear();
  // bool IsEmpty() inherited
  // bool IsFull() inherited
  // void PrintQueue() inherited
  // void PeintBuffer() inherited
	// int Length() inherited
};
  • PirntQueue - logical, 값
  • PrintBuffer - Physical, 위치
  • <Deque.h>
class Deque : Queue{ // 상속
public:
	Deque() {rear = QUEUE_SIZE-1;}
  void InsertFront(Data d); // cpp에서 정의
	void InsertRear(Data d){Insert(d);}
  Data DeleteFront(){return Delete();}
	Data DeleteRear(); // cpp에서 정의
  Data PeekFront();{return Peek();}
	Data PeekRear(); // cpp에서 정의
	// bool IsEmpty() inherited
  // bool IsFull() inherited
  // void PrintQueue() inherited
  // void PeintBuffer() inherited
	// int Length() inherited
};

Double - Ended Queue Applications

  • Palindrome: 앞에서 읽거나 뒤에서 읽거나 똑같다.
  • Stack with Limited Depth: 웹브라우저 같은 곳에서 동작을 뒤로 돌아갈 때 갯수가 정해져 있는 경우 사용. 가장 오래된 데이터를 지운다.
  • Queue with Two Servers: 은행직원 즉, 서버가 두명일 때. 줄을 두개 서고 줄이 더 짧은 곳에 선다.