Stack(스택), Queue(큐), Deque(데크)

Stack(스택)

---

 

삽입(push)과 삭제(pop)이 한쪽 끝(top)에서만 일어나는 자료구조다.

• top : 가장 상단에 위치한 원소를 가리키는 용어
• push() : top 위치에 데이터를 삽입하는 기능
  • 시간복잡도 : O(1)
  • 용량이 꽉 찬 스택에 push()를 시도하면 Stack Overflow 에러가 발생한다.
• pop() : top 위치의 데이터를 삭제/반환 하는 기능
  • 시간복잡도 : O(1)
  • 데이터가 없는 스택에 pop()을 시도하면 Stack Underflow 에러가 발생한다.

특징

• 후입선출 LIFO(Last In First Out)
• 특정 데이터를 찾기 위해서는 해당 값을 찾을 때 까지 pop()을 반복해야 한다 - O(N)
• JAVA 에서는 Stack 라이브러리를 제공한다.

 

 

Queue(큐)

---

삽입(enqueue)은 한 쪽(rear)에서, 삭제(dequeue)는 반대 쪽(front)에서 일어나는 자료구조

• front : 큐의 맨 앞 부분
• rear : 큐의 맨 뒷 부분
• enqueue() : 큐의 맨 뒤(rear) 위치에 데이터를 추가하는 기능
  • 시간복잡도 : O(1)
  • 용량이 꽉 찬 큐에 enqueue()를 시도하면 Queue Overflow 에러가 발생한다.
• dequeue() : 큐의 맨 앞(front) 위치의 데이터를 삭제/반환 하는 기능
  • 시간복잡도 : O(1)
  • 데이터가 없는 큐에 dequeue()을 시도하면 Queue Underflow 에러가 발생한다.

특징

• 선입선출 FIFO(First In First Out)
• 특정 데이터를 찾기 위해서는 해당 값을 찾을 때 까지 dequeue()을 반복해야 한다 - O(N)
• Java에서는 인터페이스 형태로 Queue 라이브러리를 제공한다.
  • 주로 LinkedList를 사용해 구현한다.

 

 

Deque(데크)

---

Double Ended Queue의 약자로, 양방향 Queue 이다.

• 양쪽 끝 위치에서의 삽입/삭제/반환 모두 O(1)의 시간복잡도를 가진다.

 

 

참고

[Java(자바)] Deque(덱/데크) 자료구조

[스택] Stack 이란?

[큐] Queue란?