스택, 큐

스택

스택의 특징

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

스택의 기능

1. push : stack의 위에 항목을 삽입
2. pop : stack top의 항목 삭제
3. peek or top : stack의 가장 위를 표시
4. isempty : stack이 비어있는지 확인
5. isfull : stack이 가득 차 있는지 확인

스택의 동작

push

1. stack이 가득 찼는지 확인
2. stack이 가득 차면 오류 발생 후 종료
3. stack이 가득 차지 않으면 top 증가
4. top이 가리키는 위치에 데이터 추가

pop

1. stack이 비어 있는지 확인
2. stack이 비어 있으면 오류 발생 후 종료
3. stack이 비어 있지 않으면 top이 가리키는 데이터 제거
4. top 감소
5. 데이터 반환

시간 복잡도

Operation	Average	Worst
Access	Θ(n)	O(n)
Search	Θ(n)	O(n)
Insert	Θ(1)	O(1)
Delete	Θ(1)	O(1)

스택의 활용

• 웹 브라우저 방문기록
• 역순 문자열 만들기
• 실행 취소
• 후위 표기법 계산
• 수식의 괄호 검사

스택의 구현

1. array 사용
   • 구현하기 쉽다
   • 크기가 동적이 아니다.
2. linkedlist 사용
   • 크기가 동적이다.
   • 포인터를 위한 추가 메모리 공간이 필요

큐

큐의 특징

• rear에서 삽입, front에서 삭제 작업이 이루어진다.
• FIFO 구조를 가진다

큐의 기능

1. enqueue : queue의 rear에 항목을 추가
2. dequeue : queue의 front의 항목을 제거
3. peek : queue의 front의 항목을 반환
4. isfull : queue가 가득 찼는지 확인
5. isempty : queue가 비어 있는지 확인

큐의 동작

enqueue

1. queue가 가득 찼는지 확인
2. queue가 가득 차면 오류 발생 후 종료
3. queue가 가득 차지 않으면 rear 증가
4. rear가 가리키는 위치에 데이터 추가

dequeue

1. queue가 비어 있는지 확인
2. queue가 비어 있으면 오류 발생 후 종료
3. queue가 비어 있지 않으면 front가 가리키는 데이터 제거
4. front 감소
5. 데이터 반환

시간 복잡도

Operation	Average	Worst
Access	Θ(n)	O(n)
Search	Θ(n)	O(n)
Insert	Θ(1)	O(1)
Delete	Θ(1)	O(1)

큐의 활용

• 우선순위가 같은 작업 예약
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색 구현
• 캐시 구현

큐의 구현

1. array 사용
   • 구현하기 쉽다
   • 크기가 동적이 아니다.
2. linkedlist 사용
   • 크기가 동적이다.
   • 포인터를 위한 추가 메모리 공간이 필요