[ 자료구조 ] 선형 자료구조 - 스택, 큐, 덱

스택(Stack)

---

• LIFO(Last in First Out)
• 나중에 들어간 원소가 먼저 나온다.
• 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 구조
• push : 데이터를 top 위치에 넣기
• pop : 가장 최근에 푸시한 데이터가 나옴
• stack underflow : 자료가 없을 때 pop 하면 발생하는 오류
• stack overflow : 스택의 크기 이상 자료를 push 하면 발생하는 오류
• 삽입, 삭제의 시간 복잡도 : O(1) → 장점

 

큐(Queue)

---

• FIFO(First in First Out)
• 먼저 들어간 원소가 먼저 나온다.
• front : 데이터가 삽입(push)되는 곳
• back : 제거(pop)되는 곳
• 삽입, 삭제의 시간 복잡도 : O(1) → 장점

 

덱(Deque)

---

• 양쪽 끝에서 입출력이 가능한 자료구조
• 크기가 가변적이다.
• 삽입, 삭제, 탐색의 시간 복잡도 : O(1)