
#define MaxSzie 10            //定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize];   //静态数组存放栈中元素
    int top;                  //栈顶指针
}SqStack;    
 
//初始化栈
void InitStack(SqStack &S){
    S.top = -1;               //初始化栈顶指针
}
 
void testStack(){
    SqStack S;            //声明一个顺序栈（分配空间）
    InitStack(S);
    .....
}
 
//判空操作
bool StackEmpty(SqStack S){
    if(S.top == -1)
        return true;
    else
        return false;
}

2、（增）进栈


//新元素入栈
bool Push(SqStack &S,ElemType x){
    if(S.top == MaxSize - 1)        //栈满报错
        return false;
    S.top = S.top + 1;    //指针先加1
    S.data[S.top] = x;    //新元素入栈
    return true;
}

3、（删）出栈


//出栈操作
bool Pop(SqStack &S,ElemType &x){
    if(S.top == -1)    //栈空报错
        return false;
    x = S.data[S.top];        //栈顶元素先出栈
    S.top = S.top - 1;        //指针再减一
    return true;
}

3、读取栈顶元素


//读取栈顶元素
bool GetTop(SqStack S,ElemTpe &x){
    if(S.top == -1)        //栈空报错
        return false;
    x = S.data[S.top];        //x记录栈顶元素
    return true;
}

4、共享栈


#define MaxSzie 10            //定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize];   //静态数组存放栈中元素
    int top0;                  //0号指针
    int top1;                  //1号指针
 
}SqStack;    
 
//初始化栈
void InitStack(SqStack &S){
    S.top0 = -1;               //初始化栈顶指针
    S.top1 = MaxSize; 
}

5、小结

三、链栈的实现

知识总览

1、链栈的定义


typedef struct Linknode{
    ElemType data;            //数据域
    struct Linknode *next;    //指针域
}*LiStack;                    //栈类型定义

2、小结

四、队列

知识总览

1、定义

队列（Queue）是只允许在一端进行插入，在另一端删除的线性表

重要术语：队头、队尾、空队列

2、队列的基本操作

InitQueue(&Q): 初始化队列。构造一个空队列Q。

DestroyQueue(&Q): 销毁队列。销毁并释放队列Q所占用的内存空间。

EnQueue(&Q,x): 入队。若队列Q未满，将x加入，使之成为新的队尾。

DeQueue(&Q,&x): 出队。若队列Q非空，删除队头元素，并用x返回。

GetHead(Q,&x): 读队头元素。若队列Q非空，则将队头元素赋值给x。

3、小结

五、队列的顺序实现

知识总览

1、初始化判空


#define MaxSize 10    //定义队列元素的最大个数
typedef struct{
    ElemType data[MaxSize];    //使用静态数组存放队列元素
    int front,rear;            //队头指针和队尾指针
}SqQueue;
 
void testQueue(){
    SqQueue Q;    //声明一个队列
    //....后续操作
}
 
//判空
bool QueueEmpty(SqQueue Q){
    if(Q.rear == Q.front)    //队空条件
        return true;
    else
        return false;
 
}

2、入队操作-循环队列


//入队
bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1) %MaxSize == Q.front)
        return false;    
    Q.data[Q.rear] = x;    //将x插入队尾
    Q.rear = (Q.rear + 1) % MaxSize;    //队尾指针加1，取模
    return true;
}

3、出队操作-循环队列


//出队（删除一个队头元素，并使用 x 返回）
bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear == Q.front)
        return false;
    x = Q.data[Q.front];
    Q.front = (Q.front +1) % MaxSize;    //队头指针后移，取模使其变为可循环
    return true;
}

4、获取队头元素


//获取队头元素的值，用x返回
bool GetHead(SqQueue Q,ElemType &x){
    if(Q.rear == Q.front)
        return false;
    x = Q.data[Q.front]
    return true;
}

5、队列元素个数

（rear + MaxSize - front）% MaxSize

6、判断队满/队空

方法一、

方法二、

7、其他出题方式

8、小结

六、队列的链式实现

知识总览

1、初始化


typedef struct LinkNode{    //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;
 
typedef struct{        //链式队列
    LinkNode *front,*rear;    //队列的队头和队尾的指针
}LinkQueue;

带头结点


//初始化队列
void InitQueue(LinkQueue &Q){
    //初始时 front 、 rear 都指向头结点
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front -> next = NULL;
}
 
void testLinkQueue(){
    LinkQueue Q;    //声明一个队列
    InitQueue(Q);    //初始化队列
    //...后续操作...
}

2、入队（带头结点）


//新元素入队
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s = (LinkNode)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear -> next = s;    //新结点插入到rear之后
    Q.rear = s;        //修改表尾指针
}

3、入队（不带头结点）


void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    if(Q.front == NULL)    //在空队列当中插入第一个元素
        Q.front = s;        //修改队头队尾的指针
        Q.rear = s;         //不带头结点的队列，第一个入对的元素需要特殊处理
    }else{
        Q.rear->next = s;    //新结点插入到rear结点之后
        Q.rear = s;            //修改rear指针
    }
}

4、出队（带头结点）


//出队带头结点
void DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front == Q.rear)
        return false;    //空队
    LinkNode *p = Q.front -> next;
    x=p->data;    //用变量x返回队头元素
    Q.front->next = p->next;    //修改头结点的next指针
    if(Q.rear == p)    //此次是最后一个结点出队
        Q.rear = Q.front;    //修改rear指针
    free(p);    //释放结点空间
    return true;
}

5、出队（不带头结点）


//出队不带头结点
void DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front == NULL)
        return false;    //空队
    LinkNode *p = Q.front;    //p指向此次出队的结点
    x=p->data;    //用变量x返回队头元素
    Q.front = p->next;    //修改front指针
    if(Q.rear == p){    //此次是最后一个结点出队
        Q.front = NULL;    
        Q.rear = NULL；
    }
    free(p);    //释放结点空间
    return true;
}