Algorithm Study (스택, 큐)

이전내용 링크

 

완전탐색

정렬

문자열

배열,리스트

 

일렬로 늘어선 자료들을 표현하는 자료구조로 배열/리스트를 알아봤다.

일렬로 늘어선 자료를 특정 순서로 넣고 꺼내는 자료구조로 스택/큐가 존재한다.

스택/큐는 배열/리스트로 쉽게 구현 가능하지만 흔히 사용되는 자료구조이며 개발자 간의 원활한 의사소통을 위해서 이름이 붙었다고 한다.

 

7. 스택

한쪽 끝에서만 자료를 넣고 뺄 수 있다.

가장 늦게 들어간 자료가 가장 먼저 나오는 특성을 갖고 있다(후입선출, LIFO, Last In First Out)

컴퓨터 내부적으로 스택을 사용해 함수의 문맥(context)를 다룬다.

 

8. 큐

한쪽 끝에서 자료를 넣고 반대쪽에서 뺀다.

처음 들어간 자료가 먼저 나오는 특성을 갖고 있다(선입선출, FIFO, First In First Out)

일상생활의 대부분이 큐 형태로 이루어져있다(음식점의 대기줄 등)

 

9. 데크(Double-Ended Queue)

양쪽 끝에서 자료를 빼고 넣을 수 있는 자료구조이다.

데크를 이용하면 스택, 큐 모두 구현 가능하다.

 

세 자료구조 모두 연결리스트, 동적 배열로 구현이 가능하다.

자료를 넣고 빼는 연산에 상수시간이 걸린다(O(1))

대부분의 언어의 표준 라이브러리에서 구현제를 제공한다.