큐와 덱

ppparkta·2022년 3월 29일
1

자료구조

목록 보기
6/9
post-thumbnail

*이 글은 2022년 1월~2월 노션으로 진행한 스터디를 옮긴 글입니다.

220120 배열과 연결리스트로 큐 구현 (220121 원형큐/덱 내용 추가)

  • 큐의 정의 선입선출(FIFO)-front/rear구분(그림 상 rear=back) 구현할 함수
    • 초기화 함수(init)
    • 공백판단/포화상태 판단(포화상태 판단은 배열만)(is_empty/is_full)
    • 삽입/삭제(enQueue/deQueue)

  • 큐 구현(단순배열) <배열로 구현시 주의할 점>

    • front가 가리키는 값은 가장 앞 원소의 앞

    • 연결리스트 구현 시 front는 가장 앞 원소를 가리키므로 두 방식에 차이가 있음

      #include<iostream>
using namespace std;

const int max_queue=100;
int Queue[max_queue];
int front, rear;

void init() {
	front = rear = -1;
}
bool is_empty_queue() {
	if (front == rear) {
		return true;
	}
	else return false;
}
bool is_full() {
	if (rear == max_queue - 1) return true;
	else return false;
}
void enQueue(int data) {
	if(is_full()){
		cout << "큐가 꽉 찼습니다," << endl;
	}
	else{
		Queue[++rear] = data;
	}
	}
int deQueue() {
	if(is_empty_queue()){
		cout << "빈 큐입니다." << endl;
		exit(-1);
	}
	else {
		return Queue[++front];
	}
}
int peek() {
	if (is_empty_queue()) {
		cout << "빈 큐입니다." << endl;
	}
	else {
		return Queue[front];
	}
}
void print_queue() {
	for (int i = front+1; i <= rear; i++) {
		cout << Queue[i] << endl;
	}
}

int main() {
	init();
	enQueue(10);
	enQueue(20);
	enQueue(30);
	print_queue(); cout<< endl;
	deQueue();
	print_queue();
	return 0;
}
  • 큐 구현(연결리스트)
    #include<iostream>
using namespace std;

class Node {
public:
	int data;
	Node* link;
};
Node* rear;
Node* front;

void init() {
	front = rear = NULL;
}
bool is_empty_queue() {
	return(front == NULL);
}
void enQueue(int data) {
	Node* new_node=new Node;
	new_node->data = data;
	new_node->link = NULL;
	if (is_empty_queue()) {
		front = new_node;
		rear = new_node;
	}
	else {
		rear->link = new_node;
		rear = new_node;
	}
}
void deQueue() {
	if (is_empty_queue()) {
		cout << "공백 리스트입니다." << endl;
	}
	else {
		front = front->link;
		if (is_empty_queue()) {
			rear = NULL;
		}
	}
}
void print_queue() {
	for (Node* i = front; i != NULL; i=i->link) {
		cout << i->data << endl;
	}
}

int main() {
	init();
	enQueue(10);
	enQueue(20);
	enQueue(30);
	print_queue();
	deQueue();
	print_queue();
}

  • 큐의 변형-원형큐

    • 원형큐 사용 이유

      • 실제 사용공간이 남았음에도 rear가 배열의 마지막 인덱스를 가리키고 있기 때문에 포화상태로 인식함→메모리낭비 발생
      • 해결방법1: 모듈러 연산을 이용한 원형 큐 도입
      • 해결방법2: 연결리스트 사용하여 큐 구현

    • 원형큐의 상태 판별


    • 출력 연산시 주의점
      - 만약 front보다 rear가 앞에 있다면?
      - 해결방법: 나눠서 출력(front~max_array/0~rear)

      #include<iostream>
using namespace std;
const int max_array = 5;
int Queue[max_array];

int front, rear;
//초기화
void init() {
	front = rear = 0;
}
//공백상태
bool is_empty_queue() {
	return(front == rear);
}
//포화상태(자료를 M-1개 사용하는 경우)
bool is_full_queue() {
	return(front == (rear + 1) % max_array);
}
//삽입
void enQueue(int data) {
	if (is_full_queue()) {
		cout << "error: full_queue_insert" << endl;
	}
	else {
		rear = (rear + 1) % max_array;
		Queue[rear] = data;
	}
}
//삭제(단순삭제)
void deQueue() {
	if (is_empty_queue()) {
		cout << "error: empty_queue_delete" << endl;
	}
	else {
		front = (front + 1) % max_array;
	}
}
//피크
int peek() {
	if (is_empty_queue()) {
		cout << "error: empty_queue_peek" << endl;
		exit(1);
	}
	else {
		return(Queue[rear]);
	}
}
//출력
void print_queue() {
	if (is_empty_queue()) {
		cout << "error: empty_queue_print" << endl;
	}
	else {
		if (front <= rear) {
			for (int i = front + 1; i <= rear; i++) {
				cout << Queue[i] << " ";
			}
			cout << endl << "마지막 큐입니다." << endl;
		}
		else {
			for (int i = front + 1; i < max_array; i++) {
				cout << Queue[i] << " ";
			}
			for (int i = 0; i <= rear; i++) {
				cout << Queue[i] << " ";
			}
			cout << endl << "마지막 큐입니다." << endl;
		}
	}
}

int main() {
	init();
	enQueue(10);
	enQueue(20);
	enQueue(30);
	enQueue(40);
	print_queue();
	deQueue();
	deQueue();
	print_queue();
	enQueue(60);
	enQueue(70);
	print_queue();
	return 0;
}

  • 큐의 변형-덱

    • Double-Ended Queue

    • 큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있음

220121 백준 덱(10866)

  • 코드
    #include <iostream>
#include <deque>
using namespace std;

deque<int> deq;
int main() {
 int n;
 cin >> n;

 while (n--) {
  char ch[15];
  cin >> ch;

  if (ch[0] == 'p' && ch[1] == 'u') {
   int data;
   cin >> data;

   if (ch[5] == 'f') {
    deq.push_front(data);
   }
   else {
    deq.push_back(data);
   }
  }
  else if (ch[0] == 'p' && ch[1] == 'o') {
   int data;

   if (ch[4] == 'f') {
    if (deq.empty()) cout << "-1" << '\n';
    else {
     data = deq.front();
     deq.pop_front();
     cout << data << '\n';
    }
   }
   else {
    if (deq.empty()) cout << "-1" << '\n';
    else {
     data = deq.back();
     deq.pop_back();
     cout << data << '\n';
    }
   }
  }
  else if (ch[0] == 's') {
   cout << deq.size() << '\n';
  }
  else if (ch[0] == 'e') {
   if (deq.empty()) cout << '1' << '\n';
   else cout << '0' << '\n';
  }
  else if (ch[0] == 'f') {
   if (deq.empty()) cout << "-1" << '\n';
   else cout << deq.front() << '\n';
  }
  else if (ch[0] == 'b') {
   if (deq.empty()) cout << "-1" << '\n';
   else cout << deq.back() << '\n';
  }
 }

 return 0;
}

220121 백준 크게 만들기 2트(2812)

  • 코드(방식 전면 변경)
    #include<iostream>
#include<string>
#include<queue>
using namespace std;
string input;
deque<char> q;
int N, K;
void delWithBig() {
	// 문자열 input를 순회하면서
	for (int i = 0; i < input.length(); i++) {
		// 삭제할게 있는데, 덱에 있는것보다 input[i]가 크면 덱에 요소 삭제
		while (K && !q.empty() && q.back() < input[i]) {
			q.pop_back();
			K--;
		}
		q.push_back(input[i]);
	}
	// 삭제할게 남았으면 덱에서 그 만큼 덜 출력 
	for (int i = 0; i < q.size() - K; i++)
		cout << q[i];
}
int main() {
	cin >> N >> K;
	cin >> input;
	delWithBig();
}
  • 방식 변경 원래 스택으로 구현하려고 했는데 생각해보니 스택으로 넣은 뒤 반대 방향으로 꺼내야 함. 마침 덱 이용하면 쉽게 구현 가능할듯 하여 덱 쓰는 방식으로 전면 수정 덱 어떻게 사용할까?→queue STL로 사용 가능. 정리 필요.
profile
ppparkta
겉촉속촉
이전 포스트

스택으로 응용문제 풀기

다음 포스트

트리

0개의 댓글

관련 채용 정보