제3 장 창고 와 대열

@ 제3 장 스 택 과 대기 열 1, 스 택: 스 택 은 한 끝 에 만 삭제 작업 을 삽입 할 수 있 는 선형 표 입 니 다.스 택 은 저장 구조 에 따라 두 가지 로 나 뉜 다. 순서 스 택 과 체인 스 택 은 그 중에서 삽입 (스 택 에 들 어가 기) 또는 삭제 (스 택 에서 나 오기) 작업 을 할 수 있 는 한 끝 을 스 택 지붕 (Top) 이 라 고 부 르 고 다른 한 끝 은 스 택 바닥 이 라 고 부 르 며 스 택 바닥 은 고정 적 으로 변 하지 않 는 다.스 택 지붕 은 스 택 꼭대기 포인터 라 고 불 리 는 위치 표시 기 에 의 해 표시 되 고 순서 스 택 은 스 택 꼭대기 요소 가 있 는 배열 위치 표 시 를 기록 하 는 정형 변수 입 니 다.체인 스 택 은 스 택 꼭대기 요소 가 있 는 노드 주 소 를 기록 하 는 지침 입 니 다.창고 의 주요 특징 은 선진 후 출 (FILO) 이다.2. 팀: 팀 의 특징 은 먼저 나 가 는 것 (FIFO) 이다. 그 제한 은 표 의 한 끝 에 만 삽입 (파티 에 들 어 가 는 것) 을 허용 하고 표 의 다른 한 끝 에서 삭제 (파티 에 나 가 는 것) 하 는 것 이다.삽입 할 수 있 는 한 끝 을 팀 끝 (Rear) 이 라 고 하고 삭제 할 수 있 는 한 끝 을 팀 머리 (Front) 라 고 합 니 다.대기 열 은 저장 구조 에 따라 순서 팀 과 체인 팀 두 가지 로 나 눌 수 있다.구조 체 정의

//     
typedef struct 
{
    int data[maxSize];  //      ，maxSize       
    int top;            //    
}SqStack;               //       
//      
typedef struct LNode
{
   int data;            //   
   struct LNode *next;  //   
}LNode;         //      
//      
typedef struct
{
    int data[maxSize];
    int front;      //    
    int rear;       //    
}SqQueue;           //       
//    
//       
typedef struct QNode
{
    int data;               //   
    struct QNode *next;     //   
}QNode;                     //       
typedef struct
{ 
    QNode *front;           //    
    QNode *rear;            //    
}LiQueue;                   //      

2. 순서 스 택 의 초기 화, 스 택 빈 판단, 스 택 에 들 어가 기, 스 택 작업

//      
void initStack(SqStack &st) 
{
    st.top=-1;      //          -1
}/* int stack[maxSize];int top=-1; */

//    ，    1，    0
int isEmpty(SqStack st)
{
    if(st.top==-1)
        return 1;
    else
        return 0;
    
}

//    stack[++top]=x;
int push(SqStack &st,int x)
{
    if(st.top==maxSize-1)  //      
        return 0;
    ++(st.top);             //        
    st.data[st.top]=x;
        return 1;
}

//    x=stack[top--];
int pop(SqStack &st,int &x)
{
    if(st.top==-1)          //      
        return 0;
    x=st.data[st.top];      //          
    --(st.top);
    return 1;
}

3. 체인 스 택 초기 화, 스 택 빈 판단, 스 택 에 들 어가 기, 스 택 작업

//     
void initStack(LNode *&lst)
{
    lst=(LNode *)malloc(sizeof(LNode));     //       
    lst->next=NULL;
}
//
int isEmpty(LNode *lst)
{
    if(lst->next=NULL)
        return 1
    else 
        return 0;
}
void push(LNode *lst,int x)
{
    LNode  *p;
    p=(LNode *)malloc(sizeof(LNode)); //           
    p->next=NULL;
    p->data=x;
    p->next=lst->next;
    lst->next=p;
}
int pop(LNode *lst,int &x)
{
    LNode *p;
    if(lst->next==NULL)  //       ，  0
        return 0;
    p=lst->next;        //    
    x=p->data;
    lst->next=p->next;
    free(p);
    return 1;
}

4. 순환 대열 의 초기 화, 팀 의 공중 판단, 입대, 팀 의 빈 상태: qu.rear==qu.front 팀 의 만 상태: (qu.rear+1)%maxSize==qu.front; 요소 x 진 팀 작업: qu.rear=(qu.rear+1)%maxSize;data[qu.rear]=x; 요소 x 출 팀 작업: qu.front=(qu.front+1)%maxSize;x=qu.data[qu.front];

void initQueue(SqQueue &qu)
{
    qu.front=qu.rear=0;     //         ，   0
}
int isQueueEmpty(SqQueue qu)
{
    if(qu.front==qu.rear)       //    、              
        return 1;               //      ，    
    else
        return 0;
}
int enQueue(SqQueue &qu,int x)
{
    if((qu.rear+1)%maxSize==qu.front)   //       ，       
        return 0;
    qu.rear=(qu.rear+1)%maxSize;        //    ，      
    qu.data[qu.rear]=x;     //     
    return 1;
}
int deQueue(SqQueue &qu,int &x)
{
    if(qu.front==qu.rear)       //   ，     
        return 0;
        qu.front=(qu.front+1)%maxSize;  //    ，      
        x=qu.data[qu.front];    //     
        return 1;
}

5. 체인 팀 의 초기 화, 팀 의 공중 판단, 입대, 팀 의 빈 상태: lqu->rear==NULL or lqu->front==NULLL 요소 의 파티 작업 (p 파티): lqu->rear->next=p;lqu->rear=p; 요소 의 파티 작업 (x 팀 요소 저장): p=lqu->front;lqu->front=p->next;x=p->data;free(p);

//       
void initQueue(LiQueue *&lqu) //     
{
    lqu=(LiQueue*)malloc(sizeof(LiQueue));
    lqu->front=lqu->rear=NULL;
}
int isQueueEmpty(LiQueue *lqu)  //    
{
    if(lqu->rear==NULL||lqu->front==NULL)
        return 1;
    else
        return 0;
}
void enQueue(LiQueue *lqu,int x)    
{
    QNode *p;
    p=(QNode*)malloc(sizeof(QNode));
    p->data=x;
    p->next=NULL;
    if(lqu->rear==NULL)//     ，         ，      
        lqu->front=lqu->rear=p;
    else
    {
        lqu->rear->next=p;  //         ，rear   
        lqu->rear=p;
    }
}
int deQueue(LiQueue *lqu,int &x)    //    
{
    QNode *p;
    if(lqu->rear==NULL)//      
        return 0;
    else
        p=lqu->front;
        if(lqu->fornt==lqu->rear) //                    
            lqu->front=lqu->rear=NULL;
        else
            lqu->front=lqu->front->next; 
        x=p->data;
        free(p);
        return 1;
        
}