[Java] 스택(Stack) / 큐(Queue)

자료구조 중에서 가장 기본적이고 대표적인 자료구조에 대해서 정리를 하고자 한다.

정보처리기사 시리즈 자격증들을 취득할 때 항상 나오던 개념일 뿐만 아니라 실무에서도 해당 개념은 기본적인 베이스로 잡고가는 자료구조라고 생각한다.

 

---

스택(Stack)

스택이라는 것은 말 그대로 쌓아올린다는 뜻이다.

흔히 볼 수 있는 게임에서도 스택이라는 형태로 경험치를 쌓거나 혹은 스킬 포인트를 쌓듯이 스택은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 뜻한다.

 

[스택의 특징]

스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고,

top으로 정한 곳을 통해서만 접근할 수 있다.

top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며,

삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.

스택에서 자료를 삭제할 때도 top을 통해서만 가능하다.

스택에서 top을 통해 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'이라고 한다.

 

따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는

구조적 특징을 가지게 된다.

 

이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조이라고 한다.

 

그리고 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하며,

스택이 넘치는 경우 stack overflow라고 한다

 

 

 

큐(Queue)

큐는 스택과 조금 다른 형태의 자료구조이다.

큐는 정해진 방향으로 데이터가 삽입되고, 스택과 다르게 먼저 삽입된 데이터가 먼저 삭제 혹은 출력되는 형태의 자료구조아다.

놀이동산이나 맛집의 줄이 생기게 되는 것처럼 먼저 줄을 선 데이터들이 가장 먼저 출력이되는 형식인 것이다.

 

[큐의 특징]

정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리

큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.

이를 선입선출(FIFO, First in first out) 방식의 자료구조라고 말한다

이때 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여

각각의 연산작업만 수행된다. 이때, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue)

프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라고 부른다.

 

• 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
• 큐는 들어올 때 rear로 들어오지만 나올때는 front부터 빠지는 특성
• 접근방법은 가장 첫 원소와 끝 원소로만 가능
• 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제

즉, 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되는 것이며,

리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.

 

 

 

# 스택과 큐의 java 코드 및 실행결과