[algorithm] 스택(Stack), 큐(queue), 덱(deque)

스택?

스택은 간단히 말해서 한 쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조이다

구조적으로 먼저들어간 원소가 가장 마지막에 나오므로

FILO(Fist In Last Out) 라고도 불린다

 

일상 속 스택

위 사진은 접시를 쌓아올린 것이다

일상 속 스택으로 접시더미에서 접시의 추가나 제거가 맨 위에서만 가능해 스택이라고 볼 수 있다

자료구조 상에서의 스택을 그림으로 표현하면 위와 같다

 

스택은 성질로는

원소의 추가/제거가 O(1)이고

제일 상단 원소 확인이 O(1)이다

 

STL stack으로 스택을 활용할 수 있다

int main(void) {
  stack<int> S;
  S.push(10); // 10
  S.push(20); // 10 20
  S.push(30); // 10 20 30
  cout << S.size() << '\n'; // 3
  if(S.empty()) cout << "S is empty\n";
  else cout << "S is not empty\n"; // S is not empty
  S.pop(); // 10 20
  cout << S.top() << '\n'; // 20
  S.pop(); // 10
  cout << S.top() << '\n'; // 10
  S.pop(); // empty
  if(S.empty()) cout << "S is empty\n"; // S is empty
  cout << S.top() << '\n'; // runtime error 발생
}

스택이 비어있을 때 top(), pop()을 호출할 경우

runtime error가 발생하므로 주의해야 한다

 

큐?

큐는 원소를 한 쪽 끝에서 넣고 반대 쪽 끝에서 뺄 수 있는 자료구조이다

구조상 가장 먼저들어간게 가장 먼저 나오는 선입선출 구조로

FIFO(First In First Out)으로도 불린다

 

큐는 선입선출 구조로

편의점이나 식당에서 알바를 해봤다면 알법한 개념이다

 

큐의 성질로는

원소의 추가/제거가 O(1)이고,

앞,뒤의 위치한 원소 확인이 O(1)이다

 

스택은 top의 개념이 존재했다면

큐는 front와 back이 존재한다

 

원형 큐?

큐에는 단점이 한가지 존재한다

큐는 push,pop을 하다보면 점점 오른쪽으로 밀리게되는데

이러면 앞쪽에 사용하지 않는 공간이 있음에도 사용하지못하고 낭비된다

 

원형 큐라는 개념으로 이 문제를 해결할 수 있다

사진에서 알 수 있듯이

처음과 끝이 연결되어있는 구조이다

 

이렇게되면 낭비되는 메모리없이 큐를 사용할 수 있다

 

STL queue로 큐를 사용할 수 있다

int main(void) {
  queue<int> Q;
  Q.push(10); // 10
  Q.push(20); // 10 20
  Q.push(30); // 10 20 30
  cout << Q.size() << '\n'; // 3
  if(Q.empty()) cout << "Q is empty\n";
  else cout << "Q is not empty\n"; // Q is not empty
  Q.pop(); // 20 30
  cout << Q.front() << '\n'; // 20
  cout << Q.back() << '\n'; // 30
  Q.push(40); // 20 30 40
  Q.pop(); // 30 40
  cout << Q.front() << '\n'; // 30
}

스택과 마찬가지로

큐가 비어있는데 front,back,pop을 호출한다면

런타임에러가 발생하므로 주의해야한다

 

덱?

덱은 배열의 양 쪽 끝에서 모두 삽입과 삭제가 가능한 자료구조이다

스택과 큐를 덱의 특수한 종류라고 보면된다

 

덱의 성질도 스택,큐와 마찬가지로

원소의 삽입과 삭제 모두 O(1)이고

제일 앞, 뒤 원소 확인도 역시 O(1)이다

 

덱은 스택과 큐와 달리 독특한 특징이 하나 있다

바로 STL deque에서 인덱스로 원소에 접근할 수 있도록 한다는 것이다

인덱스를 통한 접근도 O(1)에 가능하다

 

STL deque로 덱을 사용가능하다

int main(void){
  deque<int> DQ;
  DQ.push_front(10); // 10
  DQ.push_back(50); // 10 50
  DQ.push_front(24); // 24 10 50
  for(auto x : DQ) cout << x << ' ';
  cout << DQ.size() << '\n'; // 3
  if(DQ.empty()) cout << "DQ is empty\n";
  else cout << "DQ is not empty\n"; // DQ is not empty
  DQ.pop_front(); // 10 50
  DQ.pop_back(); // 10
  cout << DQ.back() << '\n'; // 10
  DQ.push_back(72); // 10 72
  cout << DQ.front() << '\n'; // 10
  DQ.push_back(12); // 10 72 12
  DQ[2] = 17; // 10 72 17
  DQ.insert(DQ.begin()+1, 33); // 10 33 72 17
  DQ.insert(DQ.begin()+4, 60); // 10 33 72 17 60
  for(auto x : DQ) cout << x << ' ';
  cout << '\n';
  DQ.erase(DQ.begin()+3); // 10 33 72 60
  cout << DQ[3] << '\n'; // 60
  DQ.clear(); // DQ의 모든 원소 제거
}

 

STL deque는 위에서도 말했듯이 인덱스 접근이 가능하며

insert와 erase 기능도 제공한다

 

이 부분들이 STL vector에서 제공되는 기능과 유사하다는 느낌을 받을 수 있다

그렇다면 STL vector와 deque의 차이는 무엇일까

 

우선 STL vector는 back에서의 원소 삽입/삭제가 O(1)이지만 front에서의 삽입/삭제는 O(n)이다

반면 STL deque는 front,back에서의 삽입/삭제 모두 O(1)이다

 

이 점에서 보면 앞뒤 잦은 삽입/삭제가 필요한 경우 vector보단 deque이 유리하다

 

하지만 vector는 메모리가 하나의 연속된 공간에 저장되지만

deque는 여러 개의 작은 메모리 chunk들로 구성된다

 

이 점에서 본다면 deque은 원소들간 포인터 연산이 불가능하지만 vector는 가능하고

메모리 측면에서 vector가 이점을 가져갈 수 있게된다.

 

어떤 상황에서 어떤 자료구조를 적재적소로 사용하는 지가 중요한 역량이 될 것 같다.