[자료구조] 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영역 이라 부른다.