[자료구조]Stack, Queue, Deque

[자료구조]Stack, Queue, Deque

 

 

알고리즘 문제를 풀다 보면 자료구조를 활용하여 효율적인 코드를 짤 수 있는 경우들을 볼 수 있다.

 

예전에 배웠던 내용들인 자료구조에 대한 이해가 부족하고 복습을 할 겸 내용을 정리해 보려고 한다.

 

 

스택(stack)

스택은 젠가 모형과 같이 차곡차곡 쌓아 올린 자료구조를 말한다.

같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근을 할 수 있다.

즉 삽입하거나 삭제하거나 등 자료를 처리해야 하는 상황에서 top에 있는 데이터만 접근을 하여 push나 pop을 진행할 수 있다는 것이다. 따라서 후입선출방식인 Last In First Out 구조이다.

 

활용 예)

- 웹페이지 뒤로가기

- 실행 취소(undo) : 가장 나중에 실행된 것부터 실행을 취소한다.

- 수식 괄호 검사 등

 

장점)

-구현이 쉽다

-원하는 데이터의 접근 속도가 빠르다  -> 즉, 원하는 데이터가 3번째 배열에 위치하면 arr[2]로 한번에 접근 가능하다.

 

단점)

데이터 최대 개수를 미리 정해야 한다

데이터의 삽입과 삭제에 있어 매우 비효율적이다.

---

큐(Queue)

-정해진 top만 바라보는 stack과 달리 한쪽에서는 삽입(rear), 다른 쪽에서는 삭제(front) 작업이 이루어지어,

-데이터가 들어올 때는 rear로 들어오고, 나갈 때는 front로 나간다.

-접근 방법은 가장 첫 원소와 끝 원소로만 다능하다.

-가장 먼저 들어온 front원소가 가장 먼저 삭제가 되는 FIFO 선입선출 방식이다. 

활용 )

-우선순위가 같은 작업, 은행 업무(대기 번호) 등

- 프로세스 관리(운영체제의 작업 스케줄링), BFS 구현

- 캐시 구현

 

장점)

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 유리하다.

 

단점)

크기가 제한적이다.

큐의 앞 부분이 비어도 데이터를 삽입할 수 없다

큐가 비어있어도 not empty로 판단할 수 있다 (rear가 맨뒤)

---

Deque

-삽입과 삭제가 리스트이 양쪽 끝에서 모두 발생할 수 있는 자료구조이다. 

-Double Ended Queue라 하고 Stack과 Queue의 장점만 따서 구성한 것이다. 

 

참고 )In Python

멀티 쓰레드 환경을 지원하는 모듈 queue.Queue와 달리 collections.deque는 속도 측면, 편의성 면에서 훨씬 빠르다.