Stack&Queue

✅ 자료 구조(Data Structure)란?

자료 구조

자료(Data)의 집합을 의미
자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 정의

목적

자료를 더 효율적으로 저장하고, 관리하기 위해 사용
잘 선택된 자료구조는 실행시간을 단축시켜주거나 메모리 용량의 절약을 이끌어 낼 수 있다.

 

---

✅ 스택(Stack)이란?

스택(stack)이란 간단하게 말해 쌓아올린다는 것을 의미한다.

따라서 스택 자료구조는 쌓아 올린 형태의 자료구조를 뜻한다.

 

특징

같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다.

즉, 자료가 들어오고 나갈 수 있는 곳이 한 곳이고, 한 번에 하나의 데이터만 처리할 수 있다.

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

가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.

자료를 지나치게 많이 쌓으면 스택의 용량을 벗어나는 경우가 생기는데, 이를 스택 오버플로우(Stack Overflow)라고 한다.

 

메서드

push : 가장 위(top)에 자료를 쌓음

pop : 가장 최근에 쌓은(top에 있는) 자료를 삭제

size : 현재 쌓인 자료의 개수

 

활용

• 웹 브라우저 방문기록 (뒤로 가기)
• 실행 취소 (undo)

---

✅ 큐(Queue)란?

큐(queue)는 줄 , 혹은 줄을 서서 기다리는 것을 의미한다.

따라서 큐 자료구조는 줄을 선 형태의 자료구조를 뜻한다.

 

특징

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

이를 FIFO(First In, First Out), 선입 선출 구조라고 한다.

이때 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)라고 한다.

 

메서드

enqueue : 가장 최근에 쌓은 값(rear에 있는) 뒤에 자료를 쌓음, 이 자료가 rear가 된다.

dequeue : 가장 먼저 들어온 값(front에 있는)을 삭제

 

활용

큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 사용한다.

• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간

(힙 우선순위 큐) 추가할 것