第三章 栈与队列

@第三章 栈与队列
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;                   //链队类型定义

二、顺序栈的初始化、栈空判断、进栈、出栈操作

//顺序栈初始化
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;
}

三、链栈初始化、栈空判断、进栈、出栈操作

//链栈初始化
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;
}

四、循环队列的初始化、队空判断、入队、出队操作
队空状态：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;
}

五、链队的初始化、队空判断、入队、出队操作
队空状态：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;
        
}