배열 Queue

자료구조 & 알고리즘에서 많이 나오는 이슈 이고, 자료도 이곳 저곳 많이 있다.

다시 한번 정리할려고 한다.

대표적인 자료구조 중에서 Stack과 Queue 가 있다.

Stack 은 프링글스 통이고, Queue 는 밑둥아리가 뚫린 프링글스 통이라고 생각하면 쉽다.

구현을 어떻게 하느냐에 따라 다르겠지만, Stack 은 First In Last Out 이고 Queue 는 First In First Out 이다.

구현도 여러 가지 방법이 있겠지만, 임베디드의 한정된 자원에서 동적 할당은 위험을 안고 가기 때문에 피하고 

배열로 구현한 Queue 를 정리한다.

설계/구조는 간단하다.

1. 배열을 미리 정의한 크기만큼 할당한다.

2. 초기화 한다.

3. queue 에 삽입 또는 꺼냄

잡설.

Head, Tail 이란 말은 Stack 에서 많이 쓰이는거 같고, Front, Rear 란 말은 Queue 에서 많이 쓰이는거 같은데

그냥 기분 탓인가. -ㅅ-;; 본인은 그냥 Head, Tail 로 쓴다.

잡설.

임베디드에서 int 그대로 쓰는 사람은 거의 없다고 생각한다.

대부분 unsigned char 로 쓰고 unsigned char 로 쓰는 사람들 보다 typedef 로 새로 정의해 쓰는 사람이 더 많을거라고 생각한다. 아닌가? -ㅅ-

잡설. 

헤더와 소스코드를 분리해서 작성하는건 옵션이다. 

그전에 공용으로 쓰이는 헤더 파일

pch.h

#ifndef _PCH_H_ #define _PCH_H_ #define TRUE 1 #define FALSE 0 typedef unsigned char U8; #endif

먼저 queue 의 헤더 파일

que.h

#ifndef _QUE_H_ #define _QUE_H_ #define MAX_QUE_NUM 5 typedef struct EventQue { U8 HEAD ; // Head 는 다음 배열 인덱스를 가르킴 U8 TAIL ; // TAIL 은 U8 que[ MAX_QUE_NUM ]; } EventQue ; /** * Que 초기화 */ void queInit(); /** * 뒤에서 삽입 */ U8 pushQue( U8 data ); /** * 앞에서 빼기 */ U8 popQue(); #endif

다음은 queue 의 소스 파일

que.c

/** * que.c */ #include "pch.h" #include "que.h" // 디버깅을 위해서 전역으로 선언 // 실제 코드를 위해선 static 으로 쓰는게 안전 //static EventQue _event_que; EventQue _event_que; static U8 isFull() { // TAIL + 1 == HEAD 일때 가득 찬 것으로 정의 return ( ((_event_que.TAIL + 1) % MAX_QUE_NUM ) == _event_que.HEAD ) ? TRUE : FALSE ; } static U8 isEmpty() { return (_event_que.TAIL == _event_que.HEAD) ? TRUE : FALSE ; } void queInit() { U8 i; _event_que.HEAD = 0; _event_que.TAIL = 0; for ( i = 0 ; i < MAX_QUE_NUM ; i++ ) _event_que.que[ i ] = 0; } U8 pushQue( U8 data ) { // 배열이 꽉차면 if(isFull()) return FALSE ; // 꽉 차면 FALSE else // 꽉 차지 않으면 QUE 에 집어 넣음 { // 배열 큐이기 때문에 배열 끝으로 갔을 경우 고려 _event_que.que[ _event_que.TAIL ] = data ; _event_que.TAIL = (_event_que.TAIL + 1) % MAX_QUE_NUM ; } return TRUE; } U8 popQue() { U8 rtn; if(isEmpty()) return FALSE; // 비어 있으면 FALSE; else { rtn = _event_que.que[ _event_que.HEAD ] ; _event_que.HEAD = (_event_que.HEAD + 1 ) % MAX_QUE_NUM ; } return rtn; }

뭐 이것도 잡설이지만,

static 함수는 그 파일에서만 참조되고 외부에서 참조할수 없게 한거다.

static 전역 변수도 역시 그렇다.

static 지역 변수는 다른 개념이다. 항상 메모리에 상주 하도록 되어 있다.

배열에서 꺼내서 쓰고 지우는거 보다 메모리 참조하는 부분의 헤드 테일 부분만 변경하는게 효율이 높다.

그래서 환영 큐로 구현.

참고 : http://www.winapi.co.kr/clec/cpp2/19-4-1.htm