[알고리즘] 기본 추상자료형(3) - 설명(스택ADT, 큐ADT)

스택ADT는 후입선출(마지막에 들어간것이 가장 먼저 나온다)-LIFO(Last-In First-Out)순서를 따르는 데이터구조로, top이라 불리는 위치에서 삽입과 삭제가 행해진다

스택ADT메소드

1) 주요메소드

push(e) - 원소e를 삽입

element pop() - 가장 나중에 삽입된 원소를 삭제하여 반환

2) 보조메소드

element top() - 가장 나중에 삽입된 원소를 삭제하지 않고 반환

integer size() - 스택에 저장된 원소의 수를 반환

boolean isEmpty() - 스택이 비어 있는지 여부를 반환

iterator elements() - 스택 원소 전체를 반환

3) 예외메소드

emptyStackException() - 비어 있는 스택에 대해 pop이나 top을 시도할 경우 사용

fullStackException() - 만원 스택에 push를 시도할 경우 사용

순차스택(배열)과 연결스택(연결리스트)의 성능

	모든 각각의 작업
순차스택	O(1)
연결스택	O(1)

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

큐ADT는 선입선출(먼저 들어간것이 가장 먼저 나온다)-FIFO(First-In First-Out)순서를 따르는 데이터구조로, rear라 불리는 위치에서 삽입과 front라 불리는 위치에서 삭제가 행해진다

큐ADT메소드

1) 주요메소드

enqueue(e) - 큐의 rear에 원소e를 삽입

element dequeue() - 큐의 front에서 원소를 삭제하여 반환

2) 보조메소드

element front() - 큐의 front에 있는 원소를 삭제하지 않고 반환

integer size() - 큐에 저장된 원소의 수를 반환

boolean isEmpty() - 큐가 비어 있는지 여부를 반환

iterator elements() - 큐 원소 전체를 반환

3) 예외메소드

emptyQueueException() - 비어 있는 큐에 대해 dequeue 또는 front를 시도할 경우 사용

fullQueueException() - 만원 큐에 대해 enqueue를 시도할 경우 사용

순차큐 = 원형큐(배열)와 연결큐(연결리스트)의 성능

	모든 각각의 작업
순차큐 = 원형큐	O(1)
연결큐	O(1)

출처

제목: 알고리즘 원리와 응용

저자: 국형준

출판사: 21세기사