3.1 栈（p58）

3.1.2 顺序栈——栈的顺序存储（p59）

1.顺序栈的实现 栈的顺序存储类型可描述为

#define MaxSize 50                //定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize];        //存放栈中元素
    int top;                    //栈顶指针
}SqStack;

2.顺序栈的基本运算

(1)初始化
void InitStack(&S){
    //初始化顺序栈
    s.top=-1;                    //初始化栈顶指针
}
(2)判断空
bool StackEmpty(S){
    //判断顺序栈是否为空
    if (S.top == -1)            //栈空
        return true;
    else                        //不空
        return false;
}
(3)进栈
bool Push(SqStack &S, ElemType x) {
    //顺序栈进栈操作
    if (S.top == MaxSize - 1)    //栈满，报错
        return false;
    S.data[++S.top] = x;        //指针先加1，再入栈
    return true;
}

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

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

3.1.3 栈的链式存储结构（p61）

栈的链式存储类型可描述为

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

3.2 队列（p71）

3.2.2 队列的顺序存储结构（p71）

1.队列的顺序存储

#define MaxSize 50                //定义队列中元素的最大个数
typedef struct {                //顺序／循环队列定义
    ElemType data[MaxSize];        //存放队列元素
    int front, rear;            //队头指针和队尾指针
} SqQueue;

3.循环队列的操作

(1)初始化
void InitQueue(SqQueue &Q) {
    //初始化循环队列
    Q.rear = Q.front = 0;                //初始化队首、队尾指针
}
(2)判断空
bool isEmpty(SqQueue Q) {
    //判断循环队列是否为空
    if(Q.rear==Q.front) return true;    //队空条件
    else return false;
}
(3)入队
bool EnQueue(SqQueue &Q, ElemType x) {
    //循环队列的入队操作
    if ((Q.rear + 1) % MaxSize == Q.front) return false;//队满
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;        //队尾指针加1取模
    return true;
}
(4)出队
bool DeQueue(SqQueue &Q, ElemType &x) {
    //循环队列的出队操作
    if (Q.rear == Q.front) return false;    //队空，报错
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;      //队头指针加1取模
    return true;
}

3.2.3 队列的链式存储结构（p74）

1.队列的链式存储

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

2.链式队列的基本操作

(1)初始化
void InitQueue(LinkQueue &Q) {
    //初始化链式队列
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));//建立头结点
    Q.front->next = NULL;    //初始化为空
}
(2)判断空
bool IsEmpty(LinkQueue Q) {
    //判断链式队列是否为空
    if(Q.front==Q.rear) return true;
    else return false;
}
(3)入队
void EnQueue(LinkQueue &Q, ElemType x) {
    //链式队列入队操作
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x; s->next = NULL;        //创建新结点，插入到链尾
    Q.rear->next = s;
    Q.rear = s;
}
(4)出队
bool DeQueue(LinkQueue &Q, ElemType &x) {
    //链式队列出队操作
    if (Q.front == Q.rear) return false;//空队
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    if (Q.rear == p)
        Q.rear = Q.front;       //若原队列中只有一个结点，删除后变空
    free(p);
    return true;
}

3.3.3 栈在递归中的应用（p84）

int Fib(n){
    if(n==0)
        return 0;
    else if(n==1)
        return 1;
    else
        return Fib(n-1)+Fib(n-2);
}