Stack, Queue

1. Stack

• 후입 선출 ( Last-In First-Out )

• 사용 함수

• init() ::= 스택 초기화 함수 (top = -1 초기화)

• push() ::= 스택의 맨 위에 요소를 추가, top + 1

• pop() ::= 스택의 맨 위에 있는 요소를 반환하고 삭제, top - 1

• is_empty() ::= 스택이 비어 있는지 검사 ( top == -1 )

• is_full() ::= 스택이 가득 차 있는지 검사 ( top == MAX_STACK_SIZE - 1 )

• peek() ::= 스택의 맨 위에 있는 요소를 삭제하지 않고 반환

• 사용 예제

• 함수 호출 시 복귀 주소 기억.
• 시스템 스택 : 컴퓨터의 운영 체제만 사용, 사용자는 접근 불가
• 함수가 호출될 때마다 활성화 레코드(activation record)가 만들어지며 여기에 현재 수행되는 명령어의 주소인 프로그램 카운터(program counter) 값이 기록
• 에디터의 되돌리기(undo) 기능 구현

2. Queue

• 선입 선출 ( First-In First-Out )

• 사용 함수

• init() ::= 큐 초기화

• enqueue() ::= 큐의 뒤에 요소를 추가

• dequeye() ::= 큐의 앞에 있는 요소를 반환단 다음 삭제

• is_empty() ::= 큐가 비어 있는지 검사

• is_full() ::= 큐가 가득 찼는지 검사

• peek() ::= 큐에서 삭제하지 않고 앞에 있는 요소를 반환

• 사용 예제

• 현실 세계의 실제 상황을 시물레이션
• 은행 대기열, 데이터 패킷 모델링, 비행기 이착륙 등

• 컴퓨터와 주변기기
• 프린터 대기열, 키보드 입력 등