キューとインデックス

48415 ワード
テキストリンク
*この記事は2022年1月から2月までのNOTIONについて検討したものです.

220120アレイと接続リストを使用してキューを実装(220121個の円形キュー/インデックスコンテンツを追加)

  • キューの定義先入先出(FIFO)-実装する前/後区切り(図では後=後)関数
  • 初期化関数(init)
  • 判定ブランク/判定飽和状態(判定飽和状態のみ)(is empty/is full)
  • (enQueue/DeQueue)の挿入/削除

  • キュー実装(単純アレイ)<アレイ実装の注意事項>

  • frontが指す値は一番前の要素の前にあります

  • 接続リストを実装する場合、frontは一番前の要素を指します.この2つの方法には違いがあります.
    #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();
}

  • キューの変形-円形キュー

  • リングキューを使用する理由
  • 最後の背もたれ配列へのインデックスにより飽和→メモリ浪費
    • となる.
  • ソリューション1:モジュール化演算を使用して円形キュー
    • に導入
  • ソリューション2:接続リストを使用してキュー
    • を実装する.

  • リングキューのステータスの決定


  • 出力計算時の注意点
    -後ろが前じゃなくて前だったら?
    -解決方法:分離出力(front~max array/0~hund)
    #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;
}

    • 2,22121パーセント(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.整理が必要です.
    • [易趣]実施-ゲーム開発
    フレームワークから見たスレッドプールクラス