[자료구조] 스택, 큐, 데크

 자료구조는 자료(데이터)를 효율적으로 접근하고 수정하기 위해 자료를 조직,관리,저장하는 방법을 의미한다.

자료구조가 필요한 이유는 상황에 따라 데이터를 다루는데 시간과 메모리를 효율적으로 사용해야 때문이다.

자료구조는 형태에 따라 크게 선형 자료구조와 비선형 자료구조로 나뉘어 진다. 

선형 자료구조란 자료를 구성하는 데이터들이 직선 형태로 순차적으로 나열되어 있는 구조로 전후 데이터들 간에 일대일( 1:1 ) 관계이다.

 

 

< 선형 자료구죠 >

 

 

비선형 자료구조란 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 구조로 전후 데이터들 간에 1:N 의 관계를 가진다.

 

 

< 비선형 자료구조 >

 

 

자료구조에서 선형구조에는 대표적으로 스택(stack), 큐(queue), 덱(deque), 리스트(list) 등이 있고,

비선형구조에는 트리(tree), 그래프(graph) 등이 이다. (실제로는 더 다양하다.)

 

 

< 자료구조 종류 >

 

 

 

스택(stack) 이란?

 

  스택은 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 후입 선출 (Last In First Out , LIFO)의 자료구조이다.

쉽게 생각하면 stack 의 뜻처럼 쌓는걸 의미한다 생각하고, 하노이의 탑과 같다고 생각하면 되겠다.

 

 

 

큐(queue) 란?

 

 큐는 한 쪽 끝에서 데이터가 삽입되고, 다른 한 쪽 끝으로 삭제 되는 선입 선출(First In First Out, FIFO)의 자료구조이다.

마치 차들이 1차선 터널을 통과하는 것과 같다. queue 의 뜻이 줄을 서서 기다리는걸 의미하니 음식점 앞에 줄서 있는 구조라 생각해도 되겠다.

 

 

 

덱(deque) 이란?

 덱은 스택과 큐가 결합한 자료구조로 양쪽 끝에서 데이터들을 넣고 뺄 수 있다.

 

 

 

자료구조에서는 데이터를 넣는 작업을 push , 자료를 꺼내는 작업을 pop 이라고 한다.

대부분의 프로그래밍 언어에서 표준라이브러리로 스택, 큐, 덱의 구현체를 제공하고 있다.