대표적인 선형 자료구조(스택, 큐, 덱)

선형 자료구조

Therefore, we can traverse all the elements in single run only. Linear data structures are easy to implement because computer memory is arranged in a linear way.

스택, 큐, 데크는 모두 추상 자료형(ADT)이다. 즉, 언어에서 기본적으로 제공되는게 아니라 데이터와 연산들에 의해 정의되는 추상적인 자료구조이다. 각각을 구현하는건 프로그래머의 몫이다.

스택, 큐, 데크 모두 선형 자료 구조이며 각자 특정 방향으로 **삽입(push), 삭제(pop)**가 된다는 특징을 갖고 있다. 그리고 n개의 원소들로 이뤄진 선형 리스트이다. 그렇기 때문에 보통

• is_empty() ****: 비어있는지 여부를 반환한다.
• size() : 사이즈를 반환한다.

등의 리스트 관련 연산을 갖는다. 그리고 특정 데이터(index가 아니라 데이터 값)를 찾는 경우에는 O(n) 이 걸린다.

이 세 자료 구조들간의 차이점은, 데이터를 어느쪽 끝에서 넣고 뺄 수 있는가이다.

스택(stack)

스택은 한 방향에서만 자료를 넣고 뺄 수 있다. 이 속성에 따라서, 가장 늦게 들어간 자료를 가장 먼저 꺼내게 된다(후입선출, LIFO).

군대로 비유하면… 오마이 갓.

geeksforgeeks

스택의 연산

스택의 주요 연산은 모두 맨 위에 있는 원소(top)에 관련되어있다.

• push(e) : 스택의 top에 e를 추가
• pop() : 스택의 top에 있는 원소를 삭제하는 동시에 반환
• peek() : 스택의 top에 있는 원소를 반환

위의 연산들은 모두 상수 시간, 즉 O(1) 에 이뤄져야 한다. push, pop, peek은 모두 맨 위를 가리키는 index(top)에만 접근하므로 배열의 삽입, 삭제처럼 원소들을 이동할 필요가 없기 때문이다.

스택의 활용

프로그램의 콜 스택이 대표적이다. 함수 호출은 가장 마지막에 호출된 함수가 가장 먼저 실행이 끝나고 복귀하는 후입선출 구조이다. 어떤 함수 one이 다른 함수 two를 호출했을 때, 함수 two의 실행이 끝나고 함수 one로 돌아갈 때, 컴퓨터는 내부적으로 스택을 사용해 함수 내에 선언된 변수 등 여러 정보들로 이뤄진 맥락(context)과 전반적인 실행 순서를 관리한다.

개발하면서 자주 보는 스택 오버플로우에서 ‘스택’이 바로 콜 스택이다! 😮

그 외에도…

• 실행 취소(undo, ctrl+Z)
• 수식의 괄호식 검사(백준 문제도 있다)
• DFS

등이 있다.

큐(queue)

큐에서는 한 쪽 끝에서 자료를 넣고 반대 쪽 끝에서 자료를 꺼낼 수 있다. 이 속성에 따라서, 가장 먼저 들어간 자료가 가장 먼저 나오게 된다(선입선출, FIFO).

front (head) 는 큐에서 데이터가 삭제될 위치, rear (tail )는 큐에서 마지막 데이터가 삽입된 위치이다.

 

큐의 연산

• enQueue(e) : 큐의 rear (맨 뒤)자리에 원소 e를 삽입
• deQueue() : 큐의 front (맨 앞)자리의 원소를 삭제하고 반환
• get_front() , get_rear() : 맨앞, 맨뒤의 원소 값을 반환

위 연산 모두 특정 index (혹은 pointer)를 사용해 빠르게 접근하기 때문에 O(1) 에 수행된다.

큐의 활용

• 프로세스 레디 큐
• 스케줄링
• 캐시(Cache) 구현
• 네트워크 패킷 전송시의 버퍼 대기 큐
• 키보드 버퍼
• 프린터 큐 (스풀링)

데크(deque, double ended queue)

데크는 양쪽 방향에서 자료들을 넣고 뺄 수 있는 자료구조를 말한다. 데크에서 FIFO, LIFO는 골라서 쓰면 된다. 데크를 스택과 큐의 상위집합이라고 볼 수 있고, 데크를 이용해서 스택과 큐를 모두 구현할 수 있다.

데크의 연산

• add_front(e) : 맨 앞에 원소 e 추가
• add_rear(e) : 맨 뒤에 원소 e 추가
• delete_front(e) : 맨 앞의 원소 삭제 및 반환
• delete_rear(e) : 맨 뒤의 원소 삭제 및 반환
• get_front() , get_rear() : 맨앞, 맨뒤의 원소 값을 반환

데크의 활용

데크는 스택과 큐의 연산을 모두 쓸 수 있기 때문에, 스택과 큐로 구현할 수 있는 것들을 모두 구현할 수 있다.

끝

후기

자료구조의 개념들 자체는 어렵지 않았다. 그러나 어떤 문제가 주어지고 여기서 어떤 자료구조를 써야하는가? 라고 물었을 때 벙찌게 될 것 같다. CS 공부를 하면서 다른 개념들에서 자료구조가 활용되는걸 볼 때마다 돌아와서 자세히 적을 예정이다.

더 배울 부분들

각 자료구조의 활용 부분을 더 공부하자. 면접질문에 충분히 나올 내용들이다. 시스템 스택에 관련해서 배우면 좋을 것 같다. (서그림님 글 보면서)

참조

https://www.geeksforgeeks.org/stack-data-structure/