1．堆栈与队列的基本概念与基本操作；
2．堆栈与队列的顺序存储结构与链式存储结构的构造原理；
3．在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计；
4．堆栈和队列在解决实际问题中应用。

1 堆栈

1.1 堆栈的概念

堆栈是一种只允许在表的一端进行插入操作和删除操作的线性表。允许操作的一端称为栈顶，栈顶元素的位置由一个称为栈顶指针的变量给出。当表中没有元素时，称之为空栈。（先进后出）

1.2 堆栈的基本操作

1. 插入（进栈、入栈）
2. 删除（出栈、退栈）
3. 测试堆栈是否为空
4. 测试堆栈是否已满
5. 检索当前栈顶元素

1.3 堆栈操作的特殊性

1. 其操作仅仅是一般线性表的操作的一个子集。
2. 插入和删除操作的位置受到限制。
3. 上溢——当堆栈已满时做插入操作。（top = M–1）
4. 下溢——当堆栈为空时做删除操作。（top = –1）

1.4 堆栈的顺序存储结构

1.4.1 堆栈的顺序存储结构构造原理

描述堆栈的顺序存储结构最简单的方法是利用一维数组 STACK[ 0: M–1 ] 来表示，同时定义一个整型变量（不妨取名为 top）给出栈顶元素的位置。

1.4.2 堆栈的顺序存储结构算法设计

1.4.2.1 堆栈的顺序存储结构定义

#define MAXN 10
typedef int ElemType;
ElemType stack[MAXN];
int top;

1.4.2.2 初始化堆栈

void INIT_STACK(int &top) {
    top = -1;
}

1.4.2.3 测试堆栈是否为空

int IS_EMPTY(int top) {
    return top == -1;
}

1.4.2.4 测试堆栈是否已满

int IS_FULL(int top) {
    return top == MAXN-1;
}

1.4.2.5 插入（进栈）算法

int PUSH_STACK(ElemType stack[], int &top, ElemType item) {
    if (IS_FULL(top)) {
        return 0;
    } else {
        stack[++top] = item; // 插入成功，返回 1，否则返回 0
        return 1;       
    }
}

1.4.2.6 删除（出栈）算法

int POP_STACK(ElemType stack[], int &top, ElemType &item) {
    if (IS_EMPTY(top)) {
        return 0;
    } else {
        item = stack[--top]; // 删除成功，返回 1，否则返回 0
        return 1;
    }
}

1.4.2.7 取当前栈顶元素

int GET_TOP_ELEM(ElemType stack[],int top,ElemType &item) {
    if (IS_FULL(top)) {
        return 0; /* 退栈为空，操作失败,返回 0 */
    } else {
        item = stack[top]; /* 保存栈顶元素 */
        return 1; /* 堆栈非空，操作成功，返回 1 */
    }
}

1.5 堆栈的链式存储结构

1.5.1 堆栈的链式存储结构构造原理

链接堆栈就是用一个线性链表来实现一个堆栈结构，同时设置一个指针变量（这里不妨仍用 top 表示）指出当前栈顶元素所在链结点的位置。栈为空时，有 top = NULL。

1.5.2 堆栈的链式存储结构算法设计

1.5.2.1 堆栈的链式存储结构定义

#define MAXN 10
typedef int ElemType;
typedef struct node {
    ElemType data;
    struct node *link;
}STNode, *STLink;

1.5.2.2 初始化堆栈

void INIT_LINK_STACK(STLink &top) {
    top = NULL;
}

1.5.2.3 测试堆栈是否为空

int IS_EMPTY_LINK_STACK(STLink top) {
    return (top == NULL);
}

1.5.2.4 插入（进栈）算法

int PUSH_LINK_STACK(STLink &top, ElemType item) {
    STNode *p = (STLink)malloc(sizeof(STNode));
    if (!p) {
        return 0;
    }
    p->data = item; /*将item送新结点数据域*/
    p->link = top; /*将新结点插在链表最前面*/
    top = p; /*修改栈顶指针的指向*/
    return 1;
}

1.5.2.5 删除（退栈）算法

int POP_LINK_STACK(STLink &top, ElemType item) {
    if (IS_EMPTY_LINK_STACK(top)) {
        return 0; /*删除失败*/
    } else {
        STNode *p = top; /*暂时保存栈顶结点的地址*/
        item = p->data; /*保存被删栈顶的数据信息*/
        top = top->link; /*删除栈顶结点*/
        free(top); /*释放被删除结点*/
        return 1; /*删除成功*/
    }
}

1.5.2.6 取当前栈顶元素

int GET_TOP_ELEM_LINK_STACK(STLink top, ElemType &item) {
    if (IS_EMPTY_LINK_STACK(top)) {
        return 0; /* 退栈为空，操作失败,返回 0 */
    } else {
        item = top->data; /* 保存栈顶元素 */
        return 1; /* 堆栈非空，操作成功，返回 1 */
    }
}

2 队列

2.1 队列的概念

队列简称队。是一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。允许插⼊的⼀端称为队尾，队尾元 素的位置由 rear 指出； 允许删除的一端称为队头，队头元素的位置由 front 指出。

2.2 队列的基本操作

1. 队列的插入（进队、入队）
2. 队列的删除（出队、退队）
3. 测试队列是否为空
4. 检索当前队头元素
5. 创建一个空队

2.3 队列操作的特殊性

1. 其操作仅仅是一般线性表的操作的一个子集。
2. 插入和删除操作的位置受到限制。

2.4 队列的顺序存储结构

2.4.1 队列的顺序存储结构构造原理

在实际程序设计过程中，通常借助一个一维数组QUEUE[0: M–1]来描述队列的顺序存储结构，同时,设置两个变量 front与rear分别指出当前队头元素与队尾元素的位置。

1. rear 指出实际队尾元素所在的位置；
2. front 指出实际队头元素所在位置的前一个位置。

2.4.2 队列的顺序存储结构算法设计

2.4.2.1 队列的顺序存储结构定义

#define MAXN 1000
typedef int ElemType;
ElemType queue[MAXN];
int front,rear;
// front 指向实际队头元素所在位置的前一个位置
// rear 指向实际队尾元素所在的位置

2.4.2.2 初始化队列

void INIT_QUEUE(int &front, int &rear) {
    front = rear = -1;
}

2.4.2.3 测试队列是否为空

int IS_EMPTY_QUEUE(int front, int rear) {
    return front == rear;
}

2.4.2.4 插入（进队）算法

int PUSH_QUEUE(ElemType queue[], int &rear, ElemType item) {
    if (rear == MAXN-1) { /* 队列满，插⼊失败 */
        return 0;
    } else {
        queue[++rear] = item;
        return 1; /* 队列未满，插⼊成功 */
    }
}

2.4.2.5 删除（出队）算法

int POP_QUEUE(ElemType queue[], int &front,int rear, ElemType &item) {
    if (IS_EMPTY_QUEUE(front, rear)) {
        return 0; /* 队列为空，删除失败 */
    } else {
        item = queue[++front];
        return 1; /* 队列非空，删除成功 */
    }
}

2.4.2.6 取当前队头元素

int GET_FRONT_QUEUE(ElemType queue[],int front,int rear,ElemType &item) {
    if (IS_EMPTY_QUEUE(front, rear)) {
        return 0;
    } else {
        item = queue[front];
        return 1;
    }
}

2.5 循环队列线性存储结构

2.5.1 循环队列线性存储结构构造原理

把队列(数组)设想成头尾相连的循环表，使得数组前部由于删除操作而导致的无用空间尽可 能得到重复利用，这样的队列称为循环队列。

2.5.2 循环队列线性存储结构算法设计

2.5.2.1 插入（进队）算法

int PUSH_CIRCULAR_QUEUE(ElemType queue[], int front, int &rear, ElemType item) {
    if ((rear + 1) % MAXN == front) {
        return 0;        /* 循环队列已满，插入失败，返回 0 */
    } else {
        rear = (rear+1) % MAXN;
        queue[rear] = item;
        return 1;       /* 循环队列未满，插入成功，返回 1 */
    }
}

2.5.2.2 删除（出队）算法

int POP_CIRCULAR_QUEUE(ElemType queue[], int &front, int rear, ElemType &item) {
    if (front == rear) {
        return 0;
    } else {
        front = (front+1) % MAXN;
        item = queue[front];
        return 1;
    }
}

2.6 队列的链式存储结构

2.6.1 队列的链式存储结构构造原理

队列的链式存储结构是用一个线性链表表示一个队列，指针 front 与 rear 分别指向实际队头元素与实际队尾元素所在的链结点。

1. rear 指出实际队尾元素所在的位置；
2. front 指出实际队头元素所在位置的前一个位置。

2.6.2 队列的链式存储结构算法设计

2.6.2.1 队列的链式存储结构定义

#define MAXN 1000
typedef int ElemType;

typedef struct node {
    ElemType data;
    struct node *link;
}QNode, *QLink;

2.6.2.2 初始化队列

void INIT_LINK_QUEUE(QLink &front, QLink &rear) {
    front = rear = NULL;
}

2.6.2.3 测试队列是否为空

int IS_EMPTY_LINK_QUEUE(QLink front) {
    return front == NULL;
}

2.6.2.4 插⼊算法

int ADD_LINK_QUEUE(QLink &front, QLink &rear, ElemType item) {
    QLink q;
    if (!(q = (QLink)malloc(sizeof(QNode)))) { /* 申请链结点 */
        return 0;
    }
    q->data = item;
    q->link = NULL;
    if (front == NULL) {
        front = q; /* 插入空队的情况 */
    } else {
        rear->link = q; /* 插入非空队的情况 */
    }
    rear = q;
    return 1;
}

2.6.2.5 删除算法

int DELETE_LINK_QUEUE(QLink &front, ElemType &item) {
    if (IS_EMPTY_LINK_QUEUE(front)) {
        return 0; /* 队列为空，删除失败 */
    }
    QLink p = front;
    item = p->data;
    front = p->link;
    free(p);
    return 1; /* 队列非空，删除成功 */
}

2.6.2.6 取当前队头元素

int GET_FRONT_LINK_QUEUE(QLink front, ElemType &item) {
    if (IS_EMPTY_LINK_QUEUE(front)) {
        return 0;
    }
    item = front->data;
    return 1;
}

2.6.2.7 销毁队列

void DESTORY_LINK_QUEUE(QLink &front,QLink &rear) {
    while (front) { /* 队列非空时 */
        rear = front->link;
        free(front); /* 释放一个结点空间 */
        front = rear;
    }
}

3．堆栈和队列在解决实际问题中应用

3.1 请设计一算法，该算法将数组 A[0:n-1] 的所有元素循环右移 k 个位置。 要求算法的时间复杂度为 Ο(n)，辅助空间个数不超过 1。

3.1.1 算法思想：

1. 令 i，j 初始位置置为 0。
2. 找到 j 循环右移 k 位的位置，如果与 i 位置不同，则与第 i 位交换。然后 j 继续循环。直到 i == j。（一次循环之后将 i + k*n 位置上的数全部右移了 k 位。n 为本次循环移动的个数）。
3. 令 i++，j++。
4. 继续执行 第 2 步、第 3 步，直到移动个数为 n。

3.1.2 算法复杂度：$ O(n) $

void CIRCULATE(ElemType A[],int n,int k) {
    int count = 1, i = 0, j = 0;
    ElemType temp;
    while (count < n) {
        j = (j+k) % n; /* 找到 A[j] 循环右移 k 位的位置 */
        if (j != i) { /* 交换 A[i] 与 A[j] 的位置 */
            temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        } else { /* 此时 i + k*m 位置上的数已经全部移到对应位置，m 为移动次数 */
            i++;
            j++;
        }
        count++; /* 计数器count做一次累加 */
    }
}

3.2 已知一个无符号十进制整数 num，写一算法，依次输出其对应的八进制数的各位数字。

3.2.1 栈的顺序存储结构实现

#define MAXN 1000

void CHANGE(int num) {
    int top,stack[MAXN];
    top = -1;
    do {
        stack[++top] = num % 8; /* 余数进栈 */
        num /= 8;
    } while (num != 0);

    while (top >= 0) {
        printf(" %d",stack[top--]); /* 退栈 */
    }
    printf("\n");
}

3.2.1 栈的链式存储结构实现

void CHANGE_2(int num) {
    STLink p,top = NULL;
    do {
        p = (STLink)malloc(sizeof(STNode));
        p->data = num % 8;
        p->link = top;
        top = p;
        num /= 8;
    } while (num != 0);

    while (top != NULL) {
        printf(" %d",top->data);
        p = top;
        top = top->link;
        free(p);
    }
    printf("\n");
}

3.3 算术表达式的变换 —— —— 将中缀形式的算术表达式转换为后缀形式的表达式。

3.3.1 算法设计

只涉及 +、-、*、/、(、) 六个运算符。其中 +、- 优先级别低，*、/ 优先级别高，而括号单独处理。
从左至右依次读中缀表达式中的元素，并设置一个堆栈保存读到的表达式中的运算符。

1. 若当前读到的是运算对象（操作数），则将该运算对象作为后缀表达式中的一个元素输出；
2. 若当前读到的是运算符，则根据它与当前栈顶运算符（若栈为空直接将运算符入栈）的优先关系分别做以下动作：
   1. 若读到的运算符的优先级高于当前栈顶元素（运算符）的优先级，则读到的运算符进栈；
   2. 若读到的运算符的优先级低于或等于当前栈顶元素（运算符）的优先级,则将栈顶元素（运算符）作为后缀表达式中的一个元素输出（退栈）；
   3. 若读到的运算符为右括号，则将栈顶元素依次输出，直至左括号（左括号出栈不输出）；
   4. 若读到的运算符为右分界符 #，则将栈顶元素依次输出，直至左分界符 #。

# define max 100
char RPNStack[max];  /* RPNStack*/ 用来存放后缀表达式

/*将算术表达式转化为后缀表达式*/
void Trans(char *RPNStack) {
    char str[max]; /*存储原算术表达式*/
    char stack[max]; /*作为栈使用*/
    char ch;
    int sum, i, j, t, top = 0;
    printf("******************************************\n");
    printf("*输入一个求值的表达式，以#结束。*\n");
    printf("******************************************\n");
    printf("算数表达式：");
    i = 0;
    do { /*获取用户输入的表达式*/
        i++;
        scanf("%c",&str[i]);
    } while(str[i] != '#' && i!= max);
    sum = i;
    t = 1;
    i = 1;
    ch = str[i];
    i++;
    while(ch != '#') {
        switch(ch)
        {
            case'(': /*判定为左括号*/
                top++;
                stack[top] = ch;
                break;
            case')': /*判定为右括号*/
                while(stack[top] != '(') {
                    RPNStack[t] = stack[top];
                    top--;
                    t++;
                }
                top--;
                break;
            case'+': /*判定为加减号*/
            case'-':
                while(top != 0 && stack[top] != '(') {
                    RPNStack[t] = stack[top];
                    top--;
                    t++;
                }
                top++;
                stack[top] = ch;
                break;
            case'*': /*判定为乘除号*/
            case'/':
                while(stack[top] == '*' || stack[top] == '/') {
                    RPNStack[t] = stack[top];
                    top--;
                    t++;
                }
                top++;
                stack[top] = ch;
                break;
            case' ':
                break;
            default:
                while(ch>='0' && ch<='9') { /*判定为数字*/
                    RPNStack[t] = ch;
                    t++;
                    ch = str[i];
                    i++;
                }
                i--;
                RPNStack[t] = ' ';
                t++;
                break;
        }
        ch = str[i];
        i++;
    }
    while(top != 0) {
        RPNStack[t] = stack[top];
        t++;
        top--;
    }
    RPNStack[t] = ' ';
    printf("\n\n原来表达式：");
    for(j = 1; j < sum; j++) {
        printf("%c",str[j]);
    }
    printf("\n逆波兰式：");
    for(j = 1; j < t; j++) {
        printf("%c",RPNStack[j]);
    }
    printf("\n\n");
}

/*计算后缀表达式的值*/
void CompValue(char *RPNStack) {
    float stack[max],d;/*作为栈使用*/
    char ch;
    int t = 1,top = 0;/*t为RPNStack下标，top为stack下标*/
    ch = RPNStack[t]; t++;
    while(ch!=' ') {
        switch(ch)
        {
            case'+':
                stack[top-1] = stack[top-1] + stack[top];
                top--;
                break;
            case'-':
                stack[top-1] = stack[top-1] - stack[top];
                top--;
                break;
            case'*':
                stack[top-1] = stack[top-1] * stack[top];
                top--;
                break;
            case'/':
                if(stack[top] != 0) {
                    stack[top-1] = stack[top-1] / stack[top];
                } else {
                    printf("\n\t除零错误!\n");
                    exit(0);/*异常退出*/
                }
                top--;
                break;
            default:
                d = 0;
                while(ch >= '0' && ch <= '9') {
                    d = 10*d + ch-'0';/*将数字字符转化为对应的数值*/
                    ch = RPNStack[t];
                    t++;
                }
                top++;
                stack[top] = d;
        }
        ch = RPNStack[t];
        t++;
    }
    printf("\n\t计算结果:%g\n",stack[top]);
}