기본 자료구조 - Stack, Queue, Deque

스택(Stack)

• FILO (First In, Last Out) 구조
• 삽입과 삭제 연산이 동일한 한군데
• 삽입/삭제 연산 시간복잡도 O(1)
• 제일 상단의 원소 확인이 O(1)
• 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
• 이전에 활용한 데이터를 역으로 추적하거나 처음 들어온 데이터보다 나중에 들어온 데이터가 빨리 나가야 할 때 사용

stack<int> s;
s.push(10);
s.push(20);
s.top();	//20
s.pop(); 	//20

 

 

큐 (Queue)

• FIFO (Fisrt In, First Out) 구조
• 삽입과 삭제 연산이 서로 다른 한군데에서 발생
• 삽입/삭제 연산에 있어 시간복잡도 O(1)
• 제일 앞/뒤의 원소확인이 O(1)
• 맨 앞을 front, 맨 뒤를 rear
• 삽입연산을 enqueue, 삭제 연산을 dequeue
• 주로 순차적으로 진행되어야 하는 일을 스케줄링 할 때 사용
• 처리 과정에서 데이터를 제거해야 하는데, 제거해야하는 위치가 맨 끝이 아닐 때

// http://boj.kr/702a66643c6245f6bc05cd760490c785
#include <bits/stdc++.h>
using namespace std;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  queue<int> Q;
  int n;
  cin >> n;
  while(n--){
    string q;
    cin >> q;
    if(q=="push"){
      int val;
      cin >> val;
      Q.push(val);
    }
    else if(q=="pop"){
      if(Q.empty()) cout << -1 << '\n';
      else{
        cout << Q.front() << '\n';
        Q.pop();
      }
    }
    else if(q=="size"){
      cout << Q.size() << '\n';
    }
    else if(q=="empty"){
      cout << Q.empty() << '\n';
    }    
    else if(q=="front"){
      if(Q.empty()) cout << -1 << '\n';
      else cout << Q.front() << '\n';
    }
    else{ // back
      if(Q.empty()) cout << -1 << '\n';
      else cout << Q.back() << '\n';
    }
  }
}

 

 

덱 (Deque)

• Queue/Stack의 구조를 합친 구조
• 양쪽에서 삽입/삭제
• 삽입/삭제 연산에 있어 시간복잡도 O(1)
• 앞쪽과 뒷쪽에서의 추가와 제거가 모두 필요하면 당연히 STL deque을 사용하는게 효율적이지만 굳이 앞쪽에서의 추가와 제거가 필요하지 않고 배열과 같은 느낌으로 쓰고싶을 땐 STL deque말고 STL vector를 쓰면 됨

// http://boj.kr/82805c43b7ff48adb21a37403d55f736
#include <bits/stdc++.h>
using namespace std;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  deque<int> DQ;
  int n;
  cin >> n;
  while (n--) {
    string q;
    cin >> q;
    if (q == "push_back") {
      int val;
      cin >> val;
      DQ.push_back(val);
    }
    else if (q == "push_front") {
      int val;
      cin >> val;
      DQ.push_front(val);
    }
    else if(q == "pop_front"){
      if(DQ.empty()) cout << -1 << '\n';
      else{
        cout << DQ.front() << '\n';
        DQ.pop_front();
      }
    }
    else if(q == "pop_back"){
      if(DQ.empty()) cout << -1 << '\n';
      else{
        cout << DQ.back() << '\n';
        DQ.pop_back();
      }
    }
    else if (q == "size")
      cout << DQ.size() << '\n';
    else if (q == "empty")
      cout << DQ.empty() << '\n';
    else if (q == "front") {
      if(DQ.empty()) cout << -1 << '\n';
      else cout << DQ.front() << '\n';
    }
    else { // back
      if(DQ.empty()) cout << -1 << '\n';
      else cout << DQ.back() << '\n';
    }
  }
}

 

 

 

참고 - https://github.com/VSFe/Algorithm_Study?tab=readme-ov-file

https://blog.encrypted.gg/