[자료구조]스택(Stack)과 큐(Queue)

스택(Stack)이란?

스택이란 "쌓다"라는 의미로 데이터를 차곡차곡 쌓아 올린 이미지다

데이터가 순서대로 쌓이고 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조!

비스캣과자를 꺼낼때 가장아래의 과자를 꺼내려면 위에서부터 차례대로 꺼내야하는것처럼 가장 위쪽(최신)의 데이터부터 꺼낼수 있으며 이러한 스택의 구조를 후입선출이라고한다

 

스택(Stack)의 사용 사례

• 웹 브라우저 방문기록 (뒤로가기) ⇒ 가장 마지막에 열린 페이지부터 다시 보여준다
• 실행취소(undo) ⇒ 가장마지막에 실행된 것부터 실행을 취소해준다
• 역순 문자열만들기 ⇒ 가장 마지막에 입력된 문자부터 출력한다
• 후위 표기법 계산

장단점

• top을 통해 접근하기 떄문에 데이터 접근, 삽입,삭제가 빠르다
• top 위치 이외의 데이터에 접근할 수 없어 탐색이불가능. 탐색하려면 모든 데이터를 꺼내면서 진행해야함

 

큐(Queue)란?

큐(Queue)는 스택(Stack)과 다르게 먼저 들어온 것이 먼저 나가는 선입선출의 구조를 가지고있다

음식점에서 재료를 사용해 요리를 할때에는 먼저 손질된 재료를 사용해 요리하듯 큐(Queue)도 젤 첨에있던것이 먼저 사용되는것이다

 

큐의변화는 양끝에서 일어난다

큐 안에 요소를 넣는 것을 Enqueue, 요소를 빼는 것을 Dequeue라고 부른다

가장 첫 원소를 front / 가장 끝 원소를 rear 부르고 들어갈떄는 rear이지만 나올때는 front로 빠지는 특성이있다

그러므로 접근방식은 가장 첫 원소 혹은 가장 끝 원소로만 접근이가능하고 가장 먼저들어온 프론트원소가 가장먼저삭제된다

큐(Queue)의 사용 사례

• 은행업무
• 대기열 순서와 같은 우선순위의 작업 예약등
• 서비스 센터의 대기시간
• 프로세스관리

 

☂️자료구조 스터디

리스트를 이용한 스택

__satck[]. push(x), pop(), top(), isEmpty(), popAll()

 

리스트를 이용한 큐

__queue[], enque(x), dequeue(), front(), inEmpty(), dequeueAll()