목차
자료구조
왼쪽처럼 어질러져 있는 물건보다 오른쪽처럼 종류별로 정돈되어 있는 물건이 더 찾기가 수월합니다.
이처럼 컴퓨터와 프로그램도 이러한 자료의 추상화가 필요한데요.
자료구조는 효율적인 접근 및 수정을 가능케 하는 데이터 값의 모임을 말합니다.
스택(Stack)
후입선출
스택 구조는 아래가 막힌 상자에 데이터를 넣는 것과 같습니다.
데이터를 삽입할 때는 하나씩 차곡차곡 넣고, 삭제할 때는 마지막에 넣은 데이터가 먼저 삭제됩니다.
후입선출(LIFO : Last in First Out)
데이터 삽입
데이터 삭제
TOP
데이터의 삽입과 삭제가 일어나는 부분을 top이라는 변수를 사용해서 가리킵니다.
데이터 삽입
데이터의 삽입 연산이 발생할 때는 삽입될 데이터가 top이 가리키는 곳의 바로 위쪽에 저장이 됩니다.
데이터 삭제
반대로 삭제 연산이 발생할 때는 삽입될 데이터가 top이 가리키는 데이터가 삭제됩니다.
push & pop
스택 구조에서는 데이터 삽입 연산을 push, 삭제 연산을 pop이라고 합니다.
큐(Queue)
선입선출
큐는 앞뒤가 뚫린 파이프 구조와 같습니다.
한쪽에서 데이터 삽입 연산이 일어나고, 반대편에서 데이터 삭제 연산이 일어납니다.
선입선출(FIFO : First in First Out)
데이터 삽입
데이터 삭제
front & rear
큐는 데이터의 삭제 연산과 삽입 연산이 일어나는 곳을 가리키는 front 포인터와 rear포인터가 필요합니다.
front 포인터는 삭제가 일어나는 큐의 끝을 가리키고, rear 포인터는 삽입이 일어나는 큐의 끝을 가리키기 위한 것이지만 실제로 front 포인터는 실제 큐의 저장 데이터보다 하나 앞을 가리킵니다.
front가 실제 큐의 저장 데이터보다 하나 앞을 가리키는 이유는
큐의 마지막 원소의 삭제로 인해 빈(empty) 큐가 될 경우에 front와 rear의 값을 같아지게 하여 프로그래밍 작성을 편리하게 하기 위해서입니다.
rear = n - 1
rear 포인터가 마지막 데이터를 가르키고 있어도 큐가 가득 차 있다는 것을 의미하는 것은 아닙니다.
더 이상 데이터를 삽입할 수는 없지만, 이렇게 front가 0이 아니므로 front의 앞에는 빈 자리가 존재하는 경우도 있습니다.
참고 자료
이관용, 정광식 『컴퓨터과학개론』
