[데이터 구조 엄 울 민 판] 순환 대기 열 기본 조작

3237 단어 데이터 구조
벡터 공간 을 충분히 이용 하기 위해 '가짜 넘 침' 현상 을 극복 하 는 방법 은 벡터 공간 을 수미 가 연 결 된 링 이 라 고 상상 하고 이런 벡터 를 순환 벡터 라 고 부른다.그 안에 저 장 된 대기 열 을 순환 대기 열 (Circular Queue) 이 라 고 합 니 다.이런 순환 대기 열 은 단일 체인 테이블 의 방식 으로 실제 프로 그래 밍 응용 에서 실 현 될 수 있다.순환 대기 열 에서 대열 에 들 어 갈 때 꼬리 지침 이 앞 을 향 해 머리 지침 을 쫓 기 때 문 입 니 다.팀 을 나 갈 때 머리 지침 이 앞으로 꼬리 지침 을 쫓 아 팀 의 공백 과 팀 이 꽉 찼 을 때 머리 와 꼬리 지침 이 모두 같다.따라서 조건 frontrear 를 통 해 대기 열 이 '빈' 인지 '만' 인지 판별 할 수 없다.이 문 제 를 해결 하 는 방법 은 적어도 두 가지 가 있다. ① 다른 불 변 수 를 설정 하여 대열 의 빈 칸 과 만 칸 을 구별 한다.② 다른 방식 은 데이터 구조 에서 자주 사용 되 는 것 입 니 다. 팀 이 꽉 찼 을 때: (rear + 1)% nfront, n 은 대기 열 길이 (사용 하 는 배열 크기) 입 니 다. rear, front 는 모두 사용 하 는 공간의 지침 이 고 순환 은 논리 적 인 순환 일 뿐 이 므 로 나머지 연산 이 필요 합 니 다.그림 과 같이 팀 이 꽉 찼 습 니 다. 하지만 rear (5) + 1 = 6! =front (0), 공간 길이 에 여 유 를 구하 고 역할 은 여기에 6% 6 = 0 = front (0).
형식 정 의 는 링 모델 로 대기 열 을 실현 합 니 다. 각 데이터 구성원 의 의 미 는 다음 과 같 습 니 다. front 지정 팀 의 첫 번 째 위 치 는 하나의 요 소 를 삭제 하면 front 를 시계 방향 으로 이동 합 니 다.rear 는 요소 가 삽입 할 위 치 를 가리 키 며 요 소 를 삽입 하면 rear 를 시계 방향 으로 이동 합 니 다.count 는 대기 열 에 있 는 요소 의 개 수 를 저장 합 니 다. count 가 MaxQSize 와 같 을 때 대기 열 에 요 소 를 삽입 할 수 없습니다.대기 시간: count = 0 대기 시간: count = MaxQ Size \ # define QueueSize 100 / / 이 값 은 구체 적 인 상황 에 따라 typedef char DataType 을 정의 해 야 합 니 다. /DataType 의 유형 은 type: def struct {int front; / 헤드 포인터 에 의존 합 니 다.
/*   :    (    )
  :                 
  :11-17
  :  2320417326*/

#include
#include
using namespace std;
#define T 1
#define F 0
#define OK 1
#define ERROR 0
#define MaxSize 10

typedef int Status ;
typedef int ElementType;
typedef int Position;

struct QNode {//     
    ElementType *Data;     /*         */
    Position Front;
	Position Rear;
};

typedef struct QNode *Queue;
 
Status InitQueue(Queue &Q)//       MaxSize    
{
	Q = (Queue)malloc(sizeof(struct QNode));
	if(!Q){
		cout<Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    if(!Q->Data){
    	cout<Front = Q->Rear = 0;
    return OK;
}
 
bool IsFull(Queue Q)//     
{
	 return ((Q->Rear+1)%MaxSize == Q->Front);
    //if(((Q->Rear+1)%Q->MaxSize) == Q->Front){
    	
	//	return OK; 
//	}
//	else
	//	return ERROR;
}

int IsEmpty( Queue Q )//     
{
    if(Q->Front == Q->Rear){
    	return OK;
	}
	else{
		return ERROR; 
	};
}
 
int EnQueue(Queue &Q,ElementType e)//     
{
    if ( IsFull(Q) ) {
        cout<Rear = (Q->Rear+1)%MaxSize;
        Q->Data[Q->Rear] = e;
        cout<Front =(Q->Front+1)%MaxSize;
        e=Q->Data[Q->Front];
        return OK;
    }
}

Status DestoryQueue(Queue &Q){//     
	free(Q->Data);
	free(Q);
	cout<Data[MaxSize]={0};
    	Q->Front=Q->Rear=-1;
			cout<Data[Q->Front+1];
	return OK;
} 

int QueueLength(Queue Q){//     
	return (Q->Rear - Q->Front + MaxSize) % MaxSize;
}

Status QueueTraverse(Queue Q){//   
	int i;
	int t;
	t=Q->Rear; 
	if(IsEmpty(Q)){
		cout<Front =(Q->Front+1)%MaxSize;
			cout<Data[Q->Front]<Front=0;
	Q->Rear=t;
	return T;
}

void Menu()//   
{
	cout<>i;
		switch(i){
			case 1:{
				ClearQueue(Q);
				break;
			} 
			case 2:{
						if(IsEmpty(Q))
						 	cout<>e;
					 if ( IsFull(Q) ) 
       					 cout<

좋은 웹페이지 즐겨찾기