2006년 05월 14일 필기시험 프로그래밍 일반

2개의 포인터를 사용하여 한쪽 끝에서 자료를 삽입하고, 반대쪽 끝에서 자료를 삭제하는 선입선출(FIFO) 방식의 자료구조는?

queue ; 큐

큐는 사람들이나 물건들이 처리를 기다리며 서있는 줄을 말하는데, 줄의 맨 앞에서부터 순서대로 처리된다. 컴퓨터 프로그래밍에서의 큐는 데이터가 들어간 순서대로 제거되는 자료구조를 말한다. 이러한 순서를 가리켜 흔히, 선입선출(FIFO)이라고 한다. 이와는 반대로 스택이라는 자료구조는 먼저 들어간 데이터가 가장 나중에 제거되는 형식인데, 이것을 LIFO라 한다.

BNF (Backus-Naur form) ; 배커스-나우어 형식

BNF는 프로그래밍 언어를 정의하기 위한 최초의 메타 언어였다. ALGOL 58 언어의 구문 기술을 위해 1959년에 John Backus에 의해 처음 도입되었으며, Peter Naur에 의해 강화되어 ALGOL 60을 정의하는데 사용되었다. BNF는 구문 요소를 나타내는 기호 < >, 둘 중 하나의 선택을 의미하는 기호 ∥, 좌변은 우변에 의해 정의됨을 의미하는 기호 ::= 등의 메타 기호들을 사용하여 규칙을 표현한다. BNF의 원형은 원래 "Backus normal form"이었으나, Peter Naur의 이름을 넣어 오늘날과 같이 바뀌었다.