스택과 큐 그리고 덱

스택, 큐, 덱은 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려 있습니다.

그래서 스택, 큐, 덱을 묶어서 Restricted Structure 라고 부르기도 합니다.

Stack

스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO)을 가진 자료구조 입니다.

 

 

 

스택은 주로 문자열 폭발, 아름다운 괄호 만들기, 짝찾기 키워드 문제에서 주로 쓰입니다.
또한 "교차하지 않고" 라는 문장이 나오면 스택을 사용해야 하는 것 아닌지 염두해야 합니다.

삽입 및 삭제에 O(1), 탐색에 O(n) 이 걸립니다.
탐색에 O(n)이 걸리는 이유는 n번 째 요소를 찾기 위해 앞의 요소를 n번 반복해야 찾을 수 있기 때문입니다.
제일 상단이 아닌 나머지 원소들 확인/변경 기능이 제공되지 않습니다. (STL stack에도 이 기능은 없음)

 

• push(value) 로 해당 value를 스택에 추가
• pop() 을 통해 가장 마지막에 추가한 요소를 제거 (가장 위에 있는 요소)
• peek() / top() 을 통해 가장 마지막에 있는 요소를 참조 (가장 위)
• size() 는 스택의 크기

스택이 비어있는데 top()을 호출하지 않도록 stk.size() 체크를 통해 런타임 에러를 방지해야 합니다. 

#include <bits/stdc++.h>
using namespace std;

stack<string> stk;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    stk.push("스");
    stk.push("택");
    stk.push("과");
    stk.push("큐");
    
    while(stk.size()) {
        cout << stk.top() << '\n';
        stk.pop();
    }
}

큐
과
택
스

 

 

Queue

먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO)을 지닌 자료구조 입니다.

 

 

큐는 BFS 알고리즘과 Flood Fill을 할 때 주로 쓰입니다. 

데이터가 삽입되는 곳을 rear 라고 합니다. 데이터가 제거되는 곳을 front 라고 합니다.
데이터를 추가하려 할 때 큐가 full 한지, 데이터를 삭제할 때 큐가 empty 한지 확인해야 합니다.
큐 역시 스택과 마찬가지로 중간에 위치한 데이터에 대한 접근이 불가능합니다.

 

• push(value) 로 해당 value를 스택에 추가
• pop() 을 통해 가장 앞에 있는 요소를 제거
• size() 는 큐의 크기
• front() 는 가장 앞에 있는 요소를 참조
• back() 는 가장 뒤에 있는 요소 참조

 

#include <bits/stdc++.h>
using namespace std;

queue<int> q;
int main() {
    for(int i=1 ; i <= 10 ; i++) q.push(i);
    while(q.size()){
        cout << q.front() << ' ';
        q.pop();
    }
    return 0;
}

1 2 3 4 5 6 7 8 9 10

 

Deque

double-ended queue의 약자로 앞, 뒤로 삽입, 삭제, 참조가 가능한 자료구조입니다.

 

vector는 새로운 원소가 추가될 때 메모리 재할당 후 이전 원소를 복사하는 방식으로 인하여,
삽입 시 성능이 저하하는 단점이 있습니다.

 

deque는 이러한 vector의 단점 보완하기 위해 여러개의 메모리 블록을 할당하고 
하나의 블록처럼 여기는 기능을 제공합니다. 

 

deque는 메모리가 부족할 때마다 일정한 크기의 새로운 메모리 블록을 할당합니다.
이로써 이전 원소를 복사하지 않습니다.

 

덱은 스케줄링에 사용하며, Sliding Window 알고리즘과 큐를 확인하는 문제에서 주로 쓰입니다.

vector와 마찬가지로 배열 기반의 구조입니다.
중간에 원소를 삽입하거나 삭제할 수 있습니다.
앞, 뒤에서의 삽입, 삭제 성능에 비해 중간 삽입 삭제는 성능이 좋지 않습니다.

 

• push_front(value), push_back(value) : 해당 value를 deque에 추가
• pop()_front(), pop_back() : 앞/뒤 요소 중 가장 앞에 있는 요소를 제거
• size() : 덱의 크기
• front() : 가장 앞에 있는 요소를 참조
• back() : 가장 뒤에 있는 요소 참조
• assign(2, 5) : 2 값으로 4개의 원소를 할당
• at(idx) : idx 번째 원소를 참조 (유효범위 점검으로 dq[idx]보다 '상대적'으로 속도 느림
• dq[idx] : idx 번째 원소를 참조
• clear() : 모든 원소를 제거
• Insert(3, 4) : 3번째 위치에 4의 값을 삽입, 삽입한 곳의 iterator 반환
• erase(iter) : iter가 가리키는 원소 제거, 제거 후 앞/뒤 원소 개수 판단 적은 쪽 원소를 당겨서 채움
• empty() : dq가 비었으면 true 반환

 

#include <bits/stdc++>
using namespace stdl;

deque<int> dq

int main() {
    dp.push_front(1);
    dp.push_back(2);
    dp.push_back(3);

    cout << dq.front() << '\n';
    cout << dq.back() << '\n';
    cout << dq.size() << '\n';
    
    dq.pop_back();
    dq.pop_front();
    cout << dq.size() << '\n';
    return 0;
}

1
3
3
1