TIL 33. What is stack / queue / dequeue?

Drageon Lee·2022년 1월 12일

TIL_DS & Algorithms

목록 보기

3/3

Today's topic

지난 번 Recursion(재귀)에 대해 정리하면서 stack에 대해 언급한적 있다. Recursion(재귀)이 stack의 예시 중 하나였는데, 이번 posting을 통해 stack / queue / dequeue에 대해 자세히 알아보고자 한다.

👉 What is "stack"?

Stack 이란 다음과 같은 제약을 가진 원소들의 리스트 이다.

데이터는 stack의 끝에만 삽입할 수 있다.

데이터는 stack의 끝에서만 삭제 할 수 있다.

Stack은 마지막 원소만 읽을 수 있다.

Stack의 특성은 한 단어로 LIFO(Last In, First Out)으로 나타낼 수 있다.

그럼 stack은 주로 어디에 쓰이는가?? 다음과 같은 경우에 주로 사용된다.

지역변수 저장

임시 데이터 백업

함수 호출의 순서 제어

interrupt 처리

수식 계산

다음은 Stack에 관련 용어에 대해 알아보자.

Top : Stack의 최상단에 위치한 data이며, 가장 최근 data

Push : Stack에 새 값을 삽입하는 것

Pop : Stack의 위에서 원소를 제거하는 것

LIFO : Last In, First Out. 나중에 들어간 data가 가장 먼저 나오는 구조

Empty : Stack이 비었는 것

Full : Stack이 가득 찬 것

이러한 stack의 시간 복잡도(Big O)은 어떻게 될까?

삽입 : Insertion O(1)

삭제 : Deletione O(1)

검색 : Search O(N)

Stack의 삽입과 삭제는 맨 위에서 일어나기에 O(1)로 고정이다.

👉 What is "queue"?

Queue 또한 stack과 마찬 가지로 임시 데이터를 처리하기 위해 디자인된 data 구조 이다. Data를 처리하는 순서만 제외하면 stack과 비슷한 개념이나, data 처리 순서에서 큰 차이가 있다.
Queue 또한 3가지 제약을 갖는다.

데이터는 Queue의 끝에만 삽입할 수 있다.(Stack과 동일)

데이터는 Queue의 앞에서만 삭제할 수 있다.(Stack과 반대)

Queue 구조는 앞쪽에 있는 원소만 읽을 수 있다.(Stack과 반대)

Queue의 특성은 stack과 반대로 FIFO(First In First Out) 특성을 가진다. 먼저 저장된 data가 먼저 처리되는 구조로 입출력이 양방향에서 이루어 진다. 그렇기 때문에 Queue는 앞과 뒤가 나뉜다.

그럼 Queue는 어디에 주로 사용될까?

Queue는 FIFO의 특성 때문에 임시로 자료를 저장하거나 buffer 같은 경우에 주로 사용된다. 추가로 사용되는 용도는 아래와 같다.

운영체제 작업 스케쥴링

대기 행렬 처리

인쇄 작업 대기 목록

이러한 용도들로 사용되나, queue는 데이터 삽입 후 계속 항목을 삭제하면 rear와 front가 만나게 되어 공백큐가 됨에도 불구하고 오버 플로우 현상이 발생한다. Queue는 이런 경우 메모리 낭비가 생기게 된다는 단점이 있다.

Queue도 마찬가지로 용어에 대해 한번 알아보자.

front : Queue의 맨 시작

rear(back) : Queue의 맨 끝

enqueue : Queue의 맨 끝에서 data를 추가

dequeue : Queue의 맨 앞에서 data를 삭제

empty : Queue가 빈 것

full : Queue가 가득 찬 것

getfront : Queue의 앞을 알려 줌

size(level) : Queue의 크기

그럼 queue의 시간 복잡도(Big O)은 어떻게 될까?

삽입 : Insertion O(1)

삭제 : Deletione O(1)

검색 : Search O(N)

Queue의 삽입과 삭제는 각각 rear과 front에서만 일어나므로 O(1)로 고정이다.

👉 What is "deque"?

앞에서 비슷한 단어가 한번 언급되었다. 맞다! Queue의 data를 삭제하는 것을 dequeue라고 했었다. 하지만 이 dequeue는 double-ended queue의 축약한 것으로 stack과 queue의 장점을 합쳐 놓은 개념이며, 양 쪽에서 삽입과 삭제가 가능한 구조이다. 따라서 양 끝이 front이자 rear 이다.
이러한 deque는 자유도가 높다는 특징을 가진다.

양쪽으로 삽입 및 삭제가 가능한 이 구조는 어디에 주로 사용이 될까?

보통 양 쪽에서 삽입과 삭제가 이루어지는 경우는 많지가 않으며, stack이나 queue로 채워진 리스트에 추가나 삭제가 필요한 경우 사용된다. 주로 scheduling에 많이 사용이 되며 scheduling이 복잡한 경우 효율이 높다.

Deque도 용어에 대해 알아보자.

front : Deque의 맨 앞

rear : Deque의 맨 뒤

scroll : 입력 제한 deque, 삭제는 양쪽에서 가능하며 삽입은 한쪽에서만 가능

shelf : 출력 제한 deque, 삽입은 양쪽에서 가능하나, 출력은 한쪽에서만 가능

empty : Deque가 빈 것

full : Deque가 가득 찬 것

size(level) : Deque의 크기