[학습 노트 - 데이터 구조 07 - 대기 열]
6589 단어 구조 알고리즘
대기 열 은 한 끝 에 만 삽입 작업 을 할 수 있 고 다른 한 끝 에 서 는 삭제 작업 을 할 수 있 는 선형 표 입 니 다.
대열 은 FIFO 라 고 부 르 는 선진 적 인 선형 표 이다.삽입 을 허용 하 는 한 끝 을 팀 끝 이 라 고 하고 삭제 할 수 있 는 한 끝 을 팀 머리 라 고 합 니 다.
대기 열의 추상 데이터 형식
마찬가지 로 선형 표 이 고 대기 열 에 도 선형 표 와 유사 한 여러 가지 조작 이 있 습 니 다. 다른 것 은 데 이 터 를 삽입 하 는 것 은 팀 끝 에서 만 할 수 있 고 데 이 터 를 삭제 하 는 것 은 팀 머리 에서 만 할 수 있 습 니 다.
ADT 대기 열 (큐)
Data
。 ，
Operattion
InitQueue(*Q) : ， Q
DestroyQueue(*Q): Q ，
ClearQueue(*Q) : Q
QueueEmpty(Q): Q ， true, false
GetHead(Q,*e): Q ， e Q 。
EndQueue(*Q,e): Q ， e Q
DeQueue(*Q,*e): Q ， e
QueueLength(Q): Q
endADT
순환 대기 열
선형 표 는 순서 저장 과 체인 저장 이 있 고 스 택 은 선형 표 이기 때문에 두 가지 저장 방식 이 있다.마찬가지 로 대기 열 은 특수 한 선형 표 로 서 이 두 가지 저장 방식 도 존재 한다.대기 열 순서 저장 부족
한 대기 열 에 n 개의 요소 가 있다 고 가정 하면 순서대로 저 장 된 대기 열 은 n 보다 큰 배열 을 만 들 고 대기 열의 모든 요 소 를 배열 의 앞 n 개의 단원 에 저장 해 야 합 니 다. 배열 아래 에 0 으로 표 시 된 것 은 바로 팀 머리 입 니 다.이른바 입 대기 열 조작 이란 사실 팀 끝 에 원 소 를 추가 하 는 것 이다. 원 소 를 이동 할 필요 가 없 기 때문에 시간 복잡 도 는 O (1) 이다.
스 택 과 달리 대기 열 요소 의 배열 은 팀 의 머리, 즉 아래 에 0 으로 표 시 된 위치 입 니 다. 그러면 대기 열 에 있 는 모든 요소 가 앞으로 이동 해 야 한 다 는 것 을 의미 합 니 다. 즉, 아래 에 0 으로 표 시 된 위치 가 비어 있 지 않 습 니 다. 이때 시간 복잡 도 는 O (n) 입 니 다.
만약 팀 이 앞장 서서 원 소 를 움 직 이지 않 는 다 면 팀 의 성능 은 크게 증가 할 것 이다.팀 헤드 가 꼭 0 으로 표 시 된 위치 에 있 을 필 요 는 없다 는 것 이다.하나의 요소 만 있 을 때 팀 머리 와 부속 이 겹 치 는 것 을 피하 기 위해 front 지침 은 팀 머리 요 소 를 가리 키 고 rear 지침 은 팀 꼬리 요소 의 다음 위 치 를 가리 키 며 front = rear 일 때 이 대기 열 은 비어 있 습 니 다.
긴 주인 이 5 인 배열, 초기 상태, 빈 대기 열 이 라 고 가정 합 니 다.front 와 rear 지침 은 모두 아래 표 시 된 0 의 위 치 를 가리킨다.그 다음 에 a1 / a2 / a3 / a4, 입단 front 지침 은 여전히 아래 표 시 된 0 위 치 를 가리 키 고 rear 지침 은 아래 표 시 된 4 위 치 를 가리킨다.
팀 을 나 가면 a1, a2 는 front 지침 이 아래 에 표 시 된 2 의 위 치 를 가리 키 고 rear 는 변 하지 않 으 며 다시 팀 에 들 어가 면 a5 가 변 하지 않 습 니 다. 이때 front 지침 은 변 하지 않 고 rear 지침 은 배열 밖으로 이동 합 니 다. 이런 현상 은 가짜 넘 침 입 니 다.순환 대기 열 정의
그래서 가짜 넘 침 을 해결 하 는 방법 은 뒤에 가득 차 면 처음부터 시작 하 는 것 이다. 즉, 머리 와 꼬리 가 연결 되 는 순환 이다.우 리 는 대열 의 끝 과 끝 이 연 결 된 순서 저장 구 조 를 순환 대열 이 라 고 부른다.
이 어 위 에 a6 가 입대 하여 아래 에 0 으로 표시 되 어 있 으 며, rear 지침 은 아래 에 1 로 표시 되 어 있 으 며, 다시 a7 에 들 어가 면 rear 지침 은 front 지침 과 겹 쳐 아래 에 2 로 표시 되 어 있 는 위 치 를 가리킨다.
우 리 는 두 번 째 방법 에 중심 을 두 고 토론 합 니 다. rear 는 front 보다 클 수도 있 고 front 보다 작 을 수도 있 기 때문에 한 위치 만 다 를 때 상황 이 가득 하지만 한 바퀴 가 다 를 수도 있 습 니 다.따라서 대기 열의 최대 크기 가 QueueSize 라면 대기 열 이 가득 찬 조건 은 (rear + 1)% QueueSize = = front 입 니 다.
일반적인 대기 열 길 이 를 계산 하 는 공식: (rear - front + QueueSize)% QueueSize
순환 대기 열의 순서 저장 구조 코드:
typedef int QElemType
typedef struct
{
QElemType data[MAXSIZE];
int front;
int rear;
}SqQueue;
//
Status InitQueue(SqQueue *Q)
{
Q->front=0;
Q->rear = 0;
return OK;
}
//
int QueueLength(QqQueue Q)
{
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
//
status EnQueue(SqQueue *Q,QElemType e)
{
if((Q->rear+1)%MAXSIZE==Q->front)
return ERROR;
Q->data[Q->rear]=e;
Q->rear = (Q-rear+1)%MAXSIZE;
return OK;
}
//
status DeQueue(SqQueue *Q,QElemType *e)
{
if(Q->front==Q->rear)
return ERROR;
*e = Q->data[Q->front];
Q->front = (Q->front+1)%MAXSIZE;
return OK;
}대기 열의 체인 식 저장 구조 및 실현
대열 의 체인 식 저장 구 조 는 사실은 선형 표 의 단일 체인 표 이다. 단지 그것 은 머리 만 들 어 갈 수 있 을 뿐 우 리 는 그것 을 체인 대열 이 라 고 부른다.
//
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
//
typedef struct
{
QueuePtr front,rear;
}LinkQueue;대기 열의 체인 저장 구조 - 입 대 조작
대열 에 들 어가 조작 할 때 사실은 링크 꼬리 에 결점 을 삽입 하 는 것 이다.
Status EnQueue (LinkQueue *Q,QElemType e)
{
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
if(!s)
exit(OVERFLOW);
s->data = e;
s->next = NULL;
Q->rear->next = s;
Q->rear = s;
return OK;
}대기 열의 체인 식 저장 구조 - 출 대 조작
팀 을 나 와 조작 할 때 바로 머리 결점 의 후계 결점 이 팀 을 나 와 머리 결점 의 후계 점 을 그 뒤의 결점 으로 바 꾸 는 것 이다. 만약 에 링크 가 머리 결점 을 제외 하고 하나의 요소 만 남 았 을 때 rear 를 머리 결점 으로 가 리 켜 야 한다.
/* ， Q ， e ， OK， ERROR*/
Status DeQueue (LinkQueue *Q,QElemType *e)
{
QueuePtr p;
if(Q->front==Q->next)
return ERROR;
p=Q->front->next; // p
*e = p->data; // e
Q->front->next=p->next; // p->next
if(Q->rear==p)
Q->rear=Q->front;
free(p);
return OK;
}좋은 웹페이지 즐겨찾기
