[자료구조] 스택과 큐, 데크(Stack, Queue, Deque)

스택(Stack)

스택이란

스택은 쉽게 생각하면 박스에 차곡차곡 물건을 정리하는 형태이다.

먼저 들어간 것이 밑에 위치하기 때문에 나중에 나오게 되고

나중에 들어간 것이 위에 위치하기 때문에 먼저 나오는 형태의 자료구조이다.

그렇기 때문에 스택의 모든 연산은 스택의 최상단에서 일어난다.

※LIFO(Last In First Out, 후입선출)

 

그럼 이렇게 처음 들어간 값을 쉽게 빼서 쓰지도 못하는

불편한 형태의 자료구조를 쓰는 이유는 무엇이며 어디에 쓰이는가

스택은 주로 컴퓨터 연산에 사용하는 자료구조로

연산의 우선 순위에 따라 쉽게 연산할 수 있도록 도와준다.

숫자와 연산자가 들어오면 연산자의 우선 순위에 따라

스택에 쌓아 두거나 스택의 위에서 나오면서 연산이 이루어 지는 것이다.

 

스택 관련 용어

- Top(peek): 스택의 최상단을 의미, 가장 최근에 들어온 데이터

- Push: 스택에 top에 데이터를 넣는 행위

- Pop: 스택의 top에서 데이터를 빼는 행위

- empty/full: 스택이 비었는지 가득 찼는지 검사

- size(level): 스택의 크기 리턴

 

스택 시간복잡도 Big O

- 삽입: Insertion O(1)

- 삭제: Deletion O(1)(pop) / O(N)(remove)

- 검색: Search O(N)

※스택의 삽입과 삭제 연산은 항상 top에서만 일어나므로

삽입과 삭제에 소요되는 시간복잡도는 O(1)로 고정

 

 

큐(Queue)

큐란

큐는 단어의 뜻 그대로 대기 줄을 생각하면 이해가 쉽다

대기 줄에서는 먼저 온 사람이 먼저 나가듯

큐에서도 먼저 들어온 데이터가 먼저 나가고

나중에 들어온 데이터가 나중에 나가는 형태의 자료구조이다.

이처럼 데이터의 삽입과 삭제가 큐의 양끝에서 각각 일어나므로

큐의 앞과 뒤를 명확하게 구분지을 필요가 있다.

※FIFO(First In First Out, 선입선출)

 

큐는 이러한 선입선출의 특징 때문에 임시로 자료를 저장하거나

버퍼와 같은 경우에 주로 사용하는 자료구조 형태이다

 

큐 관련 용어

- front: 큐의 맨 앞, 데이터가 나가는 곳

- rear: 큐의 맨 뒤, 데이터가 들어오는 곳

- enqueue: 큐의 뒤에 데이터 추가

- dequeue: 큐의 앞에 데이터 삭제

- empty/full: 큐가 비었는지 가득 찼는지 검사

- getfront: 큐의 맨 앞을 알려주는 것 (스택의 peek)

- size(level): 큐의 크기 리턴

 

큐 시간복잡도 Big O

- 삽입: Insertion O(1)

- 삭제: Deletion O(1)(dequeue) / O(N)(remove)

- 검색: Search O(N)

※큐의 삽입은 front에서만 일어나고 삭제는 항상 rear에서만 일어나므로

삽입과 삭제에 소요되는 시간복잡도는 O(1)로 고정

 

 

 

데크(Deque)

데크란

데크는 Double Ended Queue의 약어로

말그대로 큐의 양끝이 front이면서 rear인 형태의 자료구조이다.

이 말의 뜻은 큐처럼 한쪽에서만 데이터가 들어오는 오고

한쪽으로만 데이터가 나가는 것이 아닌

양쪽 끝에서 데이터의 삭제와 삽입 모두 가능한 것이다.

이러한 특성 때문에 데이터가 삽입과 삭제의 자유도가 높다.

 

그러나 실제로 양쪽에서 삽입과 삭제가 필요한 경우는 많지 않고

큐나 스택을 구현한 후 추가적으로 삽입, 삭제가 필요한 경우 사용한다.

보통은 스케줄링에 많이 사용하며, 스케줄링이 복잡할 수록

큐와 스택보다 더 나은 효율을 보여주곤 한다.

 

데크 관련 용어

- front/rear: 데크의 맨 앞, 데크의 맨 뒤(혹은 L-bottom, R-bottom)

- append, pop: 데크에 데이터 삽입, 삭제

- scroll: 입력제한데크, 삭제 양쪽 가능, 삽입은 한쪽만 가능

- shelf: 출력제한데크, 삽입 양쪽 가능, 삭제는 한쪽만 가능

- empty/full: 데크가 비었는지 가득 찼는지 검사

- size(level): 데크의 크기 리턴

 

데크 시간복잡도 Big O

- 삽입: Insertion O(1)

- 삭제: Deletion O(1)(pop) / O(N)(remove)

- 검색: Search O(N)

 

 

 

※참고한 글

https://m.blog.naver.com/justkukaro/220503515118

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=justkukaro&logNo=220510730704 

https://m.blog.naver.com/justkukaro/220515795433

https://velog.io/@mindol/%ED%8C%8C%EC%9D%B4%EC%8D%AC-deque%EC%9D%98-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%EC%A0%91%EA%B7%BC-%EC%97%B0%EC%82%B0-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84