[C++] [스택, 덱, 큐] BOJ 1213, 18115

스택, 큐, 덱

Stack

LIFO(LAST IN FIRST OUT)

자료의 맨 끝 위치에서만 모든 연산이 이루어짐

연산이 이루어지는 위치를 top이라고 부름

삽입은 push 삭제는 pop

std:: stack

push(element) : top에 원소를 추가

pop(): top에 있는 원소를 삭제

top(): top에 있는 원소를 반환

empty(): 스택이 비어있는지 확인(비어있으면 true)

size(): 스택 사이즈를 반환

Queue

FIFO(FIRST IN FIRST OUT)

자료의 왼쪽 끝 위치에서 삭제 오른쪽 끝 위치에서 삽입 연산이 이루어짐

삭제가 이루어지는 위치를 front, 삽입이 이루어지는 위치를 rear라고 부름

삭제는 dequeue, 삽입은 enqueue

Dequeue 연산마다 배열의 모든 원소를 한 칸씩 옮겨야 함 => 비효율적

원형큐

• 배열을 원형으로 사용하여 큐를 구현 > 실제로 원형인 배열이 있는 것은 아니다.
• 구조: 전단과 후단을 관리하기 위한 2개의 변수가 필요함

front : 첫번째 요소 하나 앞의 인덱스 (rear+1)%SIZE == front 이면 FULL

rear : 마지막 요소의 인덱스

원형이기 때문에 front와 rear가 같게 되면 포화상태가 생긴다.

Deque

자료의 양 끝에서 연산이 이루어짐

BOJ 11866 _요세푸스 문제 0

https://www.acmicpc.net/problem/11866

=> 문제 : 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

=> 풀이 방법: Queue를 사용해서 1부터 N까지 Queue에 저장한 다음 K-1번 앞에 있는 걸 뒤에 붙이고 pop한다. Queue가 빌 때까지 반복

핵심: 앞에 있는 걸 뒤에 붙이는 걸 생각해내야한다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
    int N, K;
    cin >> N >> K;
    queue<int> q;
    for (int i = 0; i < N; i++) {
        q.push(i + 1);
    }
    cout << "<";
    while (!q.empty()) {
        for (int i = 0; i < K-1; i++) {
            q.push(q.front());
            q.pop();
        }
        cout << q.front();
        q.pop();
        if (!q.empty()) {
            cout<<", ";
        }
    }
    cout << ">";
}

BOJ 18115_카드놓기

https://www.acmicpc.net/problem/18115

=> 문제 :

수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다.

1. 제일 위의 카드 1장을 바닥에 내려놓는다.
2. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.
3. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.

수현이는 처음에 카드 N장을 들고 있다. 카드에는 1부터 N까지의 정수가 중복되지 않게 적혀 있다. 기술을 N번 사용하여 카드를 다 내려놓았을 때, 놓여 있는 카드들을 확인했더니 위에서부터 순서대로 1, 2, …, N이 적혀 있었다!

놀란 수현이는 처음에 카드가 어떻게 배치되어 있었는지 궁금해졌다. 처음 카드의 상태를 출력하여라.

=>입력: 첫 번째 줄에는 N (1 ≤ N ≤ 106)이 주어진다.

두 번째 줄에는 길이가 N인 수열 A가 주어진다. Ai가 x이면, i번째로 카드를 내려놓을 때 x번 기술을 썼다는 뜻이다. Ai는 1, 2, 3 중 하나이며, An은 항상 1이다.

=>풀이방법: 기술은 뒤에서 빼야하고 남은 카드는 뒤, 앞 모두 뺴야하므로 근데 queue는 사용이 번거로우므로 둘 다 deque을 사용

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int N;
    cin >> N;
    deque<int> d;
    deque<int> l;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        d.push_back(a);
    }
    for (int i = 0; i < N; i++) {
        if (d.back() == 1) {
            l.push_front(i+1);
        }
        else if(d.back() == 2) {
            int temp = l.front();
            l.pop_front();
            l.push_front(i+1);
            l.push_front(temp);
        }
        else if (d.back() == 3) {
            l.push_back(i+1);
        }
        d.pop_back();
    }
    while (!l.empty()) {
        cout << l.front() <<" ";
        l.pop_front();
    }

}