「データ構造」キュー(Queue)

4903 ワード
CS キュー データ構造 テキストリンク
すべての内容は以下の内容を参照して作成されています.

1.定義と性質



定義＃テイギ＃


一端から要素を挿入し、他端から要素を除去できるデータ構造.
スタックでは、先に入った要素が表示され、キューでは、先に入った要素が表示されます.スタックは第1の第1の出力(FILO)と呼ばれ、キューは第1の第1の出力(FIFO)と呼ばれる.

気性


✔｣要素の追加/削除/確認👉🏻 O(1)


スタックは通常、要素を追加および削除する場所をtopと呼び、通常は要素が上下に配置されていると考えられ、キューは追加する場所をback、すなわち後、削除する場所をfront、すなわち前と呼ぶ.要するに、一番前または一番後ろに位置する元素の確認度はO(1)である.

✔前後ではなく要素のチェック/変更👉🏻 あり得ない


スタックと同様に、「キュー」というデータ構造では、インデックス・アクセス要素の機能は使用されませんが、配列を作成するときにサマリーを実行して機能できます.ただし、STL queueにはインデックスが内部要素にアクセスする機能はありません.

2.機能と実施

#include <iostream>

using namespace std;

const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;

void push(int x){
  if(tail == MX) {
    cout << "queue is full\n";
    return;
  }
  dat[tail++] = x;
}

void pop(){
  if(head == tail) {
    cout << "queue is empty\n";
    return;
  }
  head++;
}

int front(){
  return dat[head];
}

int back(){
  return dat[tail-1];
}

void test(){
  push(10); push(20); push(30);
  cout << front() << '\n'; // 10
  cout << back() << '\n'; // 30
  pop(); pop();
  push(15); push(25);
  cout << front() << '\n'; // 30
  cout << back() << '\n'; // 25
}

int main(void) {
  test();  
}

3. STL queue

#include <iostream>
#include <queue>
using namespace std;

int main(void) {
	queue<int> q;

  q.push(10); // 10
  q.push(20); // 10 20
  q.push(30); // 10 20 30
  cout << q.size() << '\n'; // 3
  if(q.empty()) cout << "q is empty\n";
  else cout << "q is not empty\n"; //

  q.pop(); // 20 30
  cout << q.front() << '\n'; // 20
  cout << q.back() << '\n'; // 30
  q.push(40); // 20 30 40
  q.pop(); // 30 40
  cout << q.front() << '\n'; // 30
}

4.練習問題


✔️ BOJ 10845号：スタート 
#include <iostream>
#include <queue>
#include <string>

using namespace std;

int main() {
    int n; //명령의 수
    queue<int> q;

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    
    string cmd;
    int item;
    for (int i = 0; i < n; i++) {
        cin >> cmd;
        if (cmd == "push")
        {
            cin >> item;
            q.push(item);

        } else if (cmd == "pop")
        {
            if (q.empty()) {
                cout << -1 << "\n";
            } else {
                cout << q.front() << "\n";
                q.pop();
            }
        } else if (cmd == "size")
        {
            cout << q.size() << "\n";
        } else if (cmd == "empty")
        {
            cout << q.empty() << "\n";
        } else if (cmd == "front")
        {
            if (q.empty()) {
                cout << -1 << "\n";
            } else {
                cout << q.front() << "\n";
            }
        } else if (cmd == "back")
        {
            if (q.empty()) {
                cout << -1 << "\n";
            } else {
                cout << q.back() << "\n";
            }
        }           
    }
    return 0;
}
10.embind class no memberクラスメソッド外部呼び出し
[白俊]2178号-探索迷宮