[c/c++]자료구조 - 큐(Queue)...

프로그래밍/C/C++/etc 2009. 5. 26. 14:46 posted by 야매코더


함수포인터를 쓰고도 순간이동은 계속 된다.
의견을 구한 바로는 네트워크에 멀티쓰레드를 쓰지 않아서 란다..
이런.. 어째 자꾸 늘어난다. 멀티쓰레드를 구현하기 전에 데이타구조 부터 좀 바꿔야 할듯하네..
워낙 단순한 서버 구조다 보니 자료구조를 그냥 뿌려주는거로 작업을 했는디..

어쩔수 없이 큐로 데이타를 받고 보내는 구조로 바꿔야 하겠다.
링크드리스트 도 있고 또 최근에는 링버퍼를 쓴다지만 결국 원리는 비슷한거라 빨라보이는 큐 것중에 원형큐로 해보고자 한다.

자...그럼 큐에 대해서 대충 해보자..

1. 큐(Queue) 란?

(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.

나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

프린터의 출력처리나 윈도우 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.  
출처: http://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

라고 쓰여 있다.. 암튼 먼저 입력한넘부터 출력하기 좋은 자료구조란다.

2. 완전 간단 구현 큐 소스


#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>

#define MAX 100

char *p[MAX], *pop(void);
int spos = 0;
int rpos = 0;
void add(void), push(char *q), print(void), remove(void);


void add(void)
{
  char s[256], *p;

  do {
    printf("spos %d: ", spos+1);
    gets(s);
    if(*s==0) {
       break;
    }
    p = (char *malloc(strlen(s)+1);
    if(!p) {
      printf("Out of memory.\n");
      return;
    }
    strcpy(p, s);
    if(*s) {
       push(p);
    }
  while(*s);
}

void print(void)
{
  int t;

  for(t=rpos; t < spos; ++t)
    printf("%d. %s\n", t+1, p[t]);
}

void remove(void)
{
  char *p;

  if((p=pop())==NULL) {
     return;
  }
  printf("%s\n", p);
}

void push(char *q)
{
  if(spos==MAX) {
    printf("List Full\n");
    return;
  }
  p[spos= q;
  spos++;
}

char *pop(void)
{
  if(rpos==spos) {
    printf("No more.\n");
    return NULL;
  }
  rpos++;
  return p[rpos-1];
}

int main(void)
{
  char s[80];
  register int t;

  for(t=0; t < MAX; ++t) {
     p[t= NULL;
  }

  while(1) {
    printf("Add(A), Print(P), Remove(R), Quit(Q): ");
    gets(s);
    *s = toupper(*s);

    switch(*s) {
      case 'A':
        add();
        break;
      case 'P':
        print();
        break;
      case 'R':
        remove();
        break;
      case 'Q':
        exit(0);
    }
  }
  return 0;
}


출처 : http://www.java2s.com/Code/C/Data-Structure-Algorithm/QueueinC.htm

뭐 어찌 보면 링그드리스트와 비슷한거 같기도 하고.

암튼 그냥  선형큐 는 오버플로 가 날 문제를 안고 있는 구조라 하니 조금 수정된 원형큐로 해보자...


3. 원형큐

 
01.#include <string.h>
02.#include <stdlib.h>
03.#include <stdio.h>
04.#include <ctype.h>
05. 
06.#define MAX 100
07. 
08.char *p[MAX];
09.int spos = 0;
10.int rpos = 0;
11. 
12.void push(char *q) {
13.    p[spos++] = q;
14.    spos = spos % MAX;
15.}
16. 
17.char * pop() {
18.    rpos = rpos % MAX;
19.    return p[rpos++];
20.}

간단하다...
구조체로 해도 되고..뭐... 생각보단 쉽다..해보라..
 

To be continued.    -夜昧-