[알고리즘] 선형구조- 스택, 큐 그리고 후위표기법

- 선형구조 : 자료 간의 관계가 1:1 관계, 스택과 큐가 선형구조에 해당됨. 비선형구조의 예는 트리.

 

- 스택

• 후입선출(LIFO, Last-In-First-Out) : 마지막에 삽입한 자료를 가장 먼저 꺼냄
• 연산 : push(삽입), pop(삭제), isEmpty(비어있는지), peek(top 원소값 보기)
• 맨 위 원소 top이라고 함
• Java 는 java.util.Stack 사용

 

- 후위 표기법 : 연산자가 뒤에 있는 수식 표기법

                    ex) (6+((5*(2-8))/2)) -> 6528-*2/+

 

 

- 큐

• 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
• 큐의 뒤에서는 삽입만, 큐의 앞에서는 삭제만
• 선입선출(FIFO, First-In-First-Out) : 먼저 삽입된 원소가 먼저 삭제됨
• 저장된 원소 중 첫번째 원소를 Front, 마지막 원소를 Rear 이라고 함
• 삽입 : enQueue, 삭제 : deQueue
• 큐 생성 : createQueue(), 비어있는지: isEmpty(), 가득 찼는지 : isFull(), front 반환 : Qpeek()
• Java 는 java.util.Queue 사용 -> 주요 연산 : offer(삽입), poll(삭제)

 

- 우선순위 큐

• 우선순위를 가진 항목들을 저장하는 큐
• FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나감
• Java는 java.util.PriorityQueue -> Heap 자료구조(트리)
• 우선순위를 큰 값으로 설정하면 최대 Heap
• 우선순위를 작은 값으로 설정하면 최소 Heap