[자료구조] 스택, 큐, 덱
[자료구조] 스택, 큐, 덱
- 자료구조에는 스택(stack), 큐(Queue), 덱(Deque)등이 있다.
- 메모리의 영역을 어떻게 처리하느냐의 기준으로 나눔
스택(Stack)
- 먼저 들어간 자료가 나중에 나옴
- 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함
- LIFO(Last In First Out) 구조
- 깊이 우선 탐색(DFS)에서 사용한다.
- 재귀적(Recursion) 함수를 호출 할 때 사용한다.
- 인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임
큐(Queue)
- 위의 자료 구조가 큐
- 스택과 반대로 먼저 들어간 자료가 먼저 나오는 구조
- 큐는 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행함
- 가장 먼저 큐에 들어온 첫번째 원소
- 다른 한 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행함
- 큐에 가장 늦게 들어온 마지막 원소
- 컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킴
일반적인 큐의 단점
- 큐에 빈 메모리가 남아 있어도 꽉 차있는것으로 판단할 수 있음(rear가 배열의 끝에 도달했을 경우)
- -> 개선된 원형 큐가 나옴
- 원형큐의 단점 : 메모리 공간은 잘 활용하나 배열로 구현되어 있기 때문에 큐의 크기가 제한되는 단점
- -> 개선된 Linked list queue가 나옴
- 큐의 크기가 제한이 없고 삽입, 삭제가 편리함
덱(deque)
- Double Ended Queue
- 자료의 입력과 출력을 양 쪽 끝에서 가능하게 해서 스텍과 큐에 비해여 자유도가 높은 자료구조
- 스크롤(scroll) : 입력이 한쪽 끝으로만 가능하도록 제한한 덱
- 셀프(Shelf) : 출력이 한쪽 끝으로만 가능하도록 제한한 덱
- 그러나 실제로 양쪽의 입력과 출력을 모두 사용하는 경우는 없다.
- 보통 두가지 이유중 하나로 사용하게 됨. (입력과 출력을 추가하는 방식으로 많이 사용)
- 큐를 구현했는데 양쪽에서 출력할 수 있어야하거나
- 스택을 구현했는데 양쪽에서 입력하고 싶은경우
덱의 용도
- 보통 스케줄링을 사용하게 됨
- 스케줄링이 복잡해질수록 큐와 스택보다 덱이 더 효율이 잘 나오는 경우가 있음
- 우선순위를 조절하게 될 때
- ex) 옛날에 있던걸 우선순위를 높이기 위해서는 앞에서 빼낼수 있어야 되는데 스택에서는 불가능함
- ex) 최근에 들어온걸 우선순위를주고 싶은데 이 역시 큐의 구조에서는 불가능함
- 결국 앞뒤로 다 인출이 가능한 덱(Deque)만이 이 조건을 충족시킴
출처
댓글
댓글 쓰기