스택(Stack)

• 스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조

  cf) LIFO(Last In First Out)

  • 스택의 중간을 빼내야 하는 경우는 스택을 사용하면 안되는 경우

• 시간복잡도 : $O(n)$

• 1차원 배열 하나로 구현 가능

  /*stack implement*/
  int stack[10000];
  int size = 0;
  

• 스택의 메소드

• java / c++ <STL>구현 되어 있는 거 사용

  cf) stack<int>st; (stack<자료형>변수명)

• 예제 문제

Queue(큐)

• 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조
• BFS 에서 중요한 역할
• 선입선출(FIFO : First In First Out)
• 시간복잡도 : $O(n)$
• 큐의 메소드

Deque(덱)

• 양 끝에서만 자료를 넣고 양 끝에서 뺄 수 있는 자료구조
• deque의 메소드