[21.08.04]큐/스택 활용하기

- 큐 사용하지 않고 죠셉퍼스 구현

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

string str = "ABCDEFGH";
int used[100] = { 0 };

int nextPer(int idx)
{
    for (int i = idx + 1; i < str.length() * 2; i++) {
        int tx = i % str.length();
        if (used[tx] == 1) continue;
        return tx;
    }
    return 0;
}

int selectDie(int idx)
{
    //다섯번째 사람을 선택

    for (int i = 0; i < 5; i++) {
        idx = nextPer(idx);
    }

    return idx;
}

int main()
{
    int cnt = str.length();
    int idx = -1;

    while (cnt != 1) {
        idx = selectDie(idx);
        used[idx] = 1;
        cnt--;
    }

    for (int i = 0; i < str.length(); i++) {
        if (used[i] == 0) {
            cout << str[i] << endl;
            break;
        }
    }
    

    return 0;
}

- 다양한 자료형의 큐 구현하기

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

struct Node{
    int a, b;
};

queue<vector<int>> q;

queue<int> q1[5];

int main()
{
    q.push({ 1, 1 });
    q.push({ 5, 2, 2, 3 });
    q.push({ 3, 3, 1 });
    q.push({ 4, 4, 1, 2, 3, 4, 5 });
    q.push({ 6, 5 });

    vector<int> ret = q.front();
    q.pop();

    q1[0].push(1);
    q1[3].push(3);

    return 0;
}

 

 

- 죠셉퍼스 : 번갈아가며 5번째 사람부터 없애기 마지막 살아남는 사람은?(스택)

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

queue<char> q;

void init()
{
    q.push('G');
    q.push('A');
    q.push('T');
    q.push('R');
}

int main()
{
    init();

    while (q.size() > 1) {

        //1. 네번 넣다 뻈다
        for (int i = 0; i < 4; i++) {
            int ret = q.front();
            q.pop();
            q.push(ret);
        }

        //2. 다섯번쨰는 뺀다.
        q.pop();
    }

    return 0;
}

- 스택에 노드 추가하기

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

struct Node {
    char ch;
    int a, b;
};

stack<Node> st;

int main()
{
    st.push({ 'A', 6, 3 });
    st.push({ 'C', 5, 2 });
    st.push({ 'B', 6, 5 });
    st.push({ 'A', 7, 3 });

    while (!st.empty()) {
        cout << st.top().ch << st.top().a << st.top().b << endl;
        st.pop();
    }
    
    return 0;
}

- 커서위치에따른 명령 수행하기(스택)

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

string str = "A<<<BCD<<<dd<";
stack<char> ll;
stack<char> rr;

void leftGo()
{
    if (ll.empty()) return;

    rr.push(ll.top());
    ll.pop();
}

void rightGo()
{
    if (rr.empty()) return;

    ll.push(rr.top());
    rr.pop();
}

void del()
{
    if (rr.empty()) return;
    rr.pop();
}

void insertChar(char ch)
{
    ll.push(ch);
}
int main()
{
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '<') leftGo();
        else if (str[i] == '>') rightGo();
        else if (str[i] == 'd') del();
        else insertChar(str[i]);
    }

    while (!ll.empty()) {
        leftGo();
    }

    while (!rr.empty()) {
        cout << rr.top();
        rr.pop();
    }
    
    return 0;
}

- 2차원스택의 짚

//2 x 5 배열은 고정 사이즈

1. 쌓인 짚을 출력할 좌표 (첫줄)
2. 짚 정보 개수 (n)
3. 짚 좌표와 아이디 정보들 (n개)


0 0
9
0 0 14
0 0 2
1 2 2
1 2 4
1 4 6
0 4 1
0 0 7
0 4 5
0 4 3

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

stack<int> st[2][5];

int main()
{
    freopen_s(new FILE *, "Text.txt", "r", stdin);
    int tarY, tarX;
    cin >> tarY >> tarX;
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int y, x, id;
        cin >> y >> x >> id;

        st[y][x].push(id);
    }

    stack<int> temp;

    while (st[tarY][tarX].empty() == false)
    {
        temp.push(st[tarY][tarX].top());
        st[tarY][tarX].pop();
    }

    while (!temp.empty()) {
        cout << temp.top() << " ";
        temp.pop();
    }
    
    return 0;
}

- 큐에 노드 추가하기 ----->추후 다시 다룰예정 (링크드리스트?)

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

struct Node {
    int n;
    Node *next;
};

Node *st;

void push(int n)
{
    st = new Node({ n, st });
}

int top()
{
    return st->n;
}

void pop()
{
    st = st->next;
}

int main()
{
    push(1);
    push(2);
    push(3);
    push(4);

    for (int i = 0; i < 4; i++) {
        cout << top();
        pop();
    }
    
    return 0;
}

- 큐(12345를 뒤에서부터 하나씩 지우면서 반복하기)-> 출력 54321

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

queue<int> q; 
int dat[10];

void go(int n)
{
    dat[q.front()]++;
    q.pop();
}

int main()
{
    for (int y = 1; y <= 5; y++) {
        for (int x = 1; x <= y; x++) {
            q.push(x);
        }

        for (int x = 1; x <= y; x++) {
            go(x);
        }
    }

    for (int i = 1; i <= 5; i++) {
        cout << dat[i] << " ";
    }

    return 0;
}