Algorithm (스택 / 큐 / 덱)

김정욱·2020년 10월 13일

Algorithm - 문제

목록 보기

13/249

스택(stack)

: 한 쪽 끝에서만 삽입 / 삭제가 가능한 자료구조

[ 특징 ]

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

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

제일 상단이 아닌 나머지 원소들의 확인 / 변경이 원칙적으로 불가능

[ 구현 ]
const int MX = 1000005;
int dat[MX];
int pos = 0;

void push(int x){
 dat[pos++] = x; // 꽉 찼을 때에는 push전에 예외처리!
}

void pop(int x){
  pos--; // 비어있을때에는 pop전에 예외처리!
}

int top(){
 return dat[pos-1]; // 비어있을 때에는 top전에 예외처리!
}
[ STL stack ]

push / pop
 stack<int> s;

 s.push(10); 
 s.pop(); // 10
top / empty / size
 /* 10, 20, 30 */
   s.top();  // 30
   s.empty(); // false
   s.size(); // 3

큐(queue)

: 한 쪽 끝에서 삽입 / 다른 한 쪽 끝에서 삭제가 가능한 자료구조

[ 특징 ]

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

제일 앞/뒤 원소 확인 O(1)

제일 앞/뒤가 아닌 나머지 원소들의 확인 / 변경이 원칙적으로 불가능

[ STL stack ]

push / pop
 queue<int> q;

 q.push(10); 
 q.pop(); // 10
front / back / empty / size
 /* 10, 20, 30 */
   q.front();  // 10
   q.back();   // 30
   q.empty();  // false
   q.size();   // 3

덱(deque)

: 양 끝쪽에서 삽입 / 삭제가 가능한 자료구조

[ 특징 ]

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

제일 앞/뒤 원소 확인 O(1)

제일 앞/뒤가 아닌 나머지 원소들의 확인 / 변경이 원칙적으로 불가능

[ STL deque ]

push_front / push_back
  deque<int> DQ;
  DQ.push_front(10);
  DQ.push_back(20);
pop_front / pop_back
  DQ.pop_front(); // 10
  DQ.pop_back(); // 20
front / back / empty
  /* 10 20 30 */
  DQ.front(); // 10
  DQ.back(); // 30
  DQ.empty(); // false
insert / erase (vector가 가지고 있는 내장함수 지원)