C 로 구현한 알고리즘 - 2부 자료 구조, 6장 스택과 큐(Stack and Queue)

스택과 큐도 링크드 리스트만큼 쉽다.

컨셉만 이해하고 넘어가면 될듯.

스택(Stack)

( stack.h, stack.c )

스택은 자료를 LIFO(last-in, fist-out)방식으로 처리한다.

가장 쉬운 예로는 접시가 있겠다.

접시를 쌓고(push), 접시를 꺼내는(pop) 행동에서

일반적으로 가장 마지막에 쌓은 접시를 제일 먼저 사용한다.

이것이 LIFO 인 것이다.

대표적인 사용의 예는

C 에서 함수 호출, 추상 스택 머신 등이 있다.

큐(Queue)

( queue.h, queue.c )

큐는 스택과 반대로 FIFO(fist-in, first-out)방식으로 자료를 처리한다.

줄을 서서 서비스를 받기위해 기다리는 사람들을 생각하면 되겠다.

대표적인 사용의 예는

세마포어에서 자원을 기다리는 프로세스들을 큐로 관리하는 것,

이벤트 처리, 생산자-소비자 문제등이 있다.

기타

좀 더 확장된 자료구조로는 다음과 같은 것들이 있다.

데크(double-ended queues: deques)는 head / tail 양쪽에서 삽입과 삭제가 가능한 큐이다.

원형 큐(circular queues)는 tail을 갖지 않고 마지막 항목이 head 로 연결되는 큐이다.

결론

스택과 큐는 간단하지만 매우 중요한 자료구조이다.

큐의 경우, 일반적으로 프로세스/쓰레드 간 데이터를 주고 받는데 많이 사용하는데,

두 프로세스/쓰레드가 동시에 큐에 엑세스하지 않도록 하는 장치가 필요할 것이다.

별 내용이 없네... 머 쉬운거니깐.