덱(deque)

솔까말 스택, 큐는 구현이 쉬우니 넘어가자..

 

주의점 

1.  push_back 할 때에는 back 위치에 숫자를 넣고 back을 한단계 뒤로 뺀다.

    push_front 할 때에는 front를 한단계 앞으로 빼고 front위치에 숫자를 넣는다.

    pop_back 할 때에는 back을 한단계 앞으로 가고 pop한다.

    pop_front 할 때에는 pop 한 후에 한단계 앞으로 간다.

 

2. empty 여부는 front == back

   full 여부는 back+1 == front 이다.

 

즉 arr이 꽉찼다는 것은 모든 배열이 꽉찬게 아닌 어디선가 한칸이 비워진 상태가 꽉찼다는 것이다.

   

 

 

#include <iostream>
#include <string>
#define pii pair<int, int>
#define SIZE 10002
using namespace std;
 
 
int deque[SIZE];
int front = 0;
int back = 0;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int n;
    cin >> n;
 
    string str;
    int su;
    for (int i = 0; i < n; i++)
    {
        cin >> str;
        if (str == "push_back")
        {
            cin >> su;
            deque[back] = su;
            back = (back + 1) % SIZE;
 
        }
        else if(str == "push_front")
        {
            cin >> su;
            front = (front - 1 + SIZE) % SIZE;
            deque[front] = su;
        }
        else if (str == "pop_front")
        {
            if (front == back)
                cout << -1 << '\n';
            else
            {
                cout << deque[front] << '\n';
                front = (front + 1) % SIZE;
            }
            
        }
        else if (str == "pop_back")
        {
            if (front == back)
                cout << -1 << '\n';
            else
            {
                back = (back - 1 + SIZE) % SIZE;
                cout << deque[back] << '\n';
            }
            
        }
        else if (str == "size")
        {
            if (back - front >= 0)
                cout << back - front << '\n';
            else
                cout << (back - front + SIZE) % SIZE << '\n';
        }
        else if (str == "empty")
        {
            if (front == back)
                cout << 1 << '\n';
            else
                cout << 0 << '\n';
        }
        else if (str == "front")
        {
            if (front == back)
                cout << -1 << '\n';
            else
                cout << deque[front] << '\n';
        }
        else if (str == "back")
        {
            if (front == back)
                cout << -1 << '\n';
            else
                cout << deque[(back - 1 + SIZE) % SIZE] << '\n';
        }
        else if (str == "full")
        { // 임의로 추가함
            if ((back + 1) % SIZE == front)
                cout << 1;
            else
                cout << 0;
        }
 
 
    }
}