[자료구조] Queue, Deque, Stack

김희성의 개발자 면접 cs 강의/ 스터디

 

 

Queue

• 데이터가 연속적(논리적)으로 저장되어있는 선형 자료구조이다. (메모리상에서 연속적x)
• FIFO 자료구조
• Enqueue (Add) : Queue에 데이터 넣음
• Dequeue (Poll) : Queue에서 데이터 꺼냄
• 시간복잡도
  • i번째 데이터 접근 O(N)
  • 맨 앞 데이터 접근/삭제 O(1)
  • 맨 뒤 데이터 추가 O(1)
  • x 라는 데이터 있는지 탐색 O(N)

 

 

Deque ( Double Ended Queue)

• 한 방향이 아니라 양쪽 끝에서 데이터 추가하거나 꺼낼 수 있는 자료구조
• FIFO 구조라고 할 수 없음 
• 시간복잡도
  • i번째 데이터 접근 O(N)
  • 맨 앞/뒤 데이터 접근/추가/삭제 O(1)
  • x 라는 데이터 있는지 탐색 O(N)
  • queue.addFirst() , queue.pollLast() : O(1)
  • queue.contains() : O(N)

 

 

Stack

• 데이터가 연속적(논리적)으로 연결되어있는 선형 자료구조
• LIFO 
• push : stack 에 데이터 넣음 
• pop : stack 에서 데이터 꺼냄
• 시간복잡도       
  • i 번째 데이터 접근 O(N)
  • 맨 위(뒤) 데이터에 접근/삭제 O(1)
  • x 데이터 탐색 O(N)

• stack메모리를 초과하면 stack overflow error 발생
• 비어있는 stack 에 pop하면 empty stack error 발생
• 대표적으로 프로세스 메모리 영역에 사용되며, 해당 영역을 stack영역 이라 부른다.