栈和队列

栈

栈的概念及特性

• 栈是一种特殊的线性表，其特殊性体现在元素插入和删除运算上，它的插入和删除运算仅限定在线性表的某一端进行，不能在表中间和另一端进行。
• 栈的插入操作称为进栈（入栈、Push），删除操作称为出栈（退栈、Pop）。
• 允许进行插入和删除的一端称为栈顶，另一端称为栈底。
• 处于栈顶位置的数据元素称为栈顶元素。
• 不含任何数据元素的栈称为空栈。
• 栈是先进后出FILO (First In Last Out)或后进先出LIFO (Last In First Out)的线性表。

栈的基本运算：

• 初始化栈InitStack(S)。建立一个空栈S。
• 销毁栈DestroyStack(S)。释放栈S占用的内存空间。
• 进栈Push(S, x)。将元素x插入栈S中，使x成为栈S的栈顶元素。
• 出栈Pop(S, x)。当栈S不空时，将栈顶元素赋给x，并从栈中删除当前栈顶。
• 取栈顶元素GetTop(S)。若栈S不空，取栈顶元素x并返回1；否则返回0。
• 判断栈空StackEmpty(S)。判断栈S是否为空栈。

顺序栈：栈的顺序存储结构，由一个一维数组data和一个记录栈顶元素位置的变量top组成，习惯上将栈底放在数组下标小的那端，栈顶元素由栈顶指针top所指向。

顺序栈的运算

• 初始化栈算法InitStack(SqStack &S)
• 销毁栈算法DestroyStack(SqStack &S)
• 进栈算法Push(SqStack &S, ElemType e)
• 出栈运算算法Pop(SqStack &S, ElemType &e)
• 取栈顶元素算法GetTop(SqStack S, ElemType &e)
• 判断栈空算法StackEmpty(SqStack S)

代码实现：

#include <cstdio>
#include <cstdlib>

#define STACK_INIT_SIZE 100//存储空间初始分配量
#define STACK_INCREMENT 10//存储空间分配增量
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define Status int
typedef char ElemType;
typedef struct {
    ElemType* base;//栈底指针
    ElemType* top;//栈顶指针
    int stacksize;//栈的大小
}SqStack;

Status InitStack(SqStack& S)
{
    S.base = (ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (!S.base)
        return ERROR;//分配失败
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

Status DestroyStack(SqStack& S)
{
    if (!S.base)
        return ERROR;
    free(S.base);
    S.stacksize = 0;
    S.base = NULL;
    S.top = NULL;
    return OK;
}

Status Push(SqStack& S, ElemType e)
{
    if (S.top - S.base >= S.stacksize) {//栈是否满
        if (S.base = (ElemType*)realloc(S.base, (S.stacksize + STACK_INCREMENT) * sizeof(ElemType)))
            return ERROR;
        S.top = S.base + S.stacksize;
        S.stacksize += STACK_INCREMENT;
    }
    *(S.top)++ = e;
    return OK;
}

Status Pop(SqStack& S, ElemType& e)
{
    if (StackEmpty(S))
        return ERROR;
    e = *--S.top;
    return OK;
}

Status GetTop(SqStack S, ElemType& e)
{
    if (S.top == S.base)
        return ERROR;
    e = *(S.top - 1);
    return OK;
}

Status StackEmpty(SqStack S)
{
    if (S.base == S.top)
        return TRUE;
    else
        return FALSE;
}

链栈：栈的链式存储结构，通常用一个无头结点的单链表表示，将单链表的头指针作为栈顶指针。

链栈的运算

• 初始化栈运算算法InitStack(LinkStack *&top)
• 销毁栈算法DestroyStack(LinkStack *&top)
• 进栈算法Push(LinkStack *&top,ElemType x)
• 出栈算法Pop(LinkStack *&top,ElemType &x)
• 取栈顶元素算法GetTop(LinkStack *top,ElemType &x)
• 判断栈空算法StackEmpty(LinkStack *top)

代码实现：

#include <cstdio>
#include <cstdlib>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef char ElemType;
typedef struct node {
    ElemType data;
    struct node* next;
}LinkStack;

Status InitStack(LinkStack*& top)
{
    top = NULL;
    return OK;
}

Status Destory(LinkStack*& top)
{
    LinkStack* pre = top, * p;
    if (pre == NULL) return ERROR;//空栈
    p = pre->next;
    while (p != NULL) {
        free(pre);
        pre = p;
        p = p->next;
    }
    free(pre);//释放尾结点
    return OK;
}

Status Push(LinkStack*& top, ElemType e)
{
    LinkStack* p;
    p = (LinkStack*)malloc(sizeof(LinkStack));
    p->data = e;
    p->next = top;
    top = p;
    return OK;
}

Status Pop(LinkStack*& top, ElemType& e)
{
    LinkStack* p;
    if (top == NULL)
        return ERROR;
    p = top;
    e = p->data;
    top = p->next;
    free(p);
    return OK;
}

Status GetTop(LinkStack* top, ElemType& x)
{
    if (top == NULL)//空栈
        return ERROR;
    x = top->data;
    return OK;
}

Status StackEmpty(LinkStack* top)
{
    if (top == NULL)
        return TRUE;
    return FALSE;
}

顺序栈与链栈的区别：栈的使用中数据元素变化不可预料，有时小，有时大，用链栈。如果变化在可控范围之内，用顺序栈。

递归：在定义一个过程或函数时出现调用本过程或本函数。若调用自身称为直接递归，若使用过程或函数调用本过程本函数为间接递归。如果一个递归函数在执行语句最后一句时称为尾递归。

递归模型：有递归体与递归出口两部分构成。

表达式求值

中缀表达式： 中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。

前缀表达式 (波兰式)：前缀表达式的运算符位于操作数之前。

前缀表达式求值： 从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。

中缀表达式转换为前缀表达式 ：

• 初始化两个栈：运算符栈S1和储存中间结果的栈S2
• 从右至左扫描中缀表达式遇到操作数时，将其压入S2。遇到运算符时，比较其与S1栈顶运算符的优先级 。如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈 。否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1 。否则，将S1栈顶的运算符弹出并压入到S2中，再次转到S1中与新的栈顶运算符相比较 。
• 遇到括号时，如果是右括号“)”，则直接压入S1。如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃。
• 重复步骤，直到表达式的最左边，将S1中剩余的运算符依次弹出并压入S2，依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。

后缀表达式(逆波兰式)：后缀表达式与前缀表达式类似，只是运算符位于操作数之后。

后缀表达式的求值： 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈中次顶 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。

中缀表达式转换为后缀表达式 ：

• 初始化两个栈：运算符栈S1和储存中间结果的栈S2
• 从左至右扫描中缀表达式遇到操作数时，将其压入S2。遇到运算符时，比较其与S1栈顶运算符的优先级。如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈 。否则，若优先级比栈顶运算符的较高也将运算符压入S1。否则，将S1栈顶的运算符弹出并压入到S2中，再次转到S1中与新的栈顶运算符相比较 。
• 遇到括号时，如果是左括号“(”，则直接压入S1。如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃。
• 重复步骤，直到表达式的最右边，将S1中剩余的运算符依次弹出并压入S2，依次弹出S2中的元素并输出，结果的倒序即为中缀表达式对应的前缀表达式。

队列

队列的概念及特性：

• 队列（简称队）也是一种运算受限的线性表。
• 队列的插入操作称为进队，删除操作称为出队。
• 允许插入的一端称为队尾，允许删除的一端称为队头。
• 新插入的元素只能添加到队尾，被删除的只能是排在队头的元素。
• 是一种先进先出(First In First Out ，简称FIFO)的线性表。

队列的基本运算：

• 初始化队列InitQueue(Q)。建立一个空队Q。
• 销毁队DestroyQueue(Q)。释放队列Q占用的内存空间。
• 进队EnQueue(Q, x)。将x插入到队列Q的队尾。
• 出队DeQueue(Q, x)。将队列Q的队头元素出队并赋给x。
• 取队头元素GetHead(Q, x)。取出队列Q的队头元素并赋给x，但该元素不出队。
• 判断队空QueueEmpty(Q)。判断队列Q是否为空。

顺序队列：队列的顺序存储结构，由一个一维数组（用于存储队列中元素）及两个分别指示队头和队尾的变量组成，这两个变量分别称为“队头指针”和“队尾指针”。初始化建空队列时，令front=rear=0。在非空队列中，头指针始终指向队列头元素，而尾指针始终指向rear队列尾元素的下一个位置。

循环队列：为了能够充分地使用数组中的存储空间，可以把数组的前端和“假想地”连接起来，形成一个环形的表，即把存储队列元素的表从逻辑上看成一个环，这个环形的表叫做循环队列或环形队列。

• 出队：front=(front+1) MOD MAXSIZE；
• 入队：rear=(rear+1) MOD MAXSIZE；
• 队空条件：front==rear ；
• 队满条件：(rear+1) MOD MAXSIZE==front
• 队中最多只能进队MAXSIZE-1个元素

顺序循环队列的运算

• 初始化队列算法InitQueue(SqQueue &Q)
• 销毁队列运算算法DestroyQueue(SqQueue &Q)
• 入队列算法EnQueue(SqQueue &Q, ElemType e)
• 出队列算法DeQueue(SqQueue &Q, ElemType &e)
• 取队头元素运算算法GetHead(SqQueue Q, ElemType &e)
• 判断队空算法QueueEmpty(SqQueue Q)

代码实现：

#include <cstdio>
#include <cstdlib>

#define MAXQSIZE 100//实际最大存储100-1
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;
typedef struct {
    ElemType* base;//初始化动态分配存储空间
    int front;//头指针,若队列不空,指向队列头元素
    int rear;//尾指针,若队列不空,指向队列尾元素的下一个位置
}SqQueue;

Status InitQueue(SqQueue& Q)
{
    Q.base = (ElemType*)malloc(MAXQSIZE * sizeof(ElemType));
    if (!Q.base)
        return ERROR;
    Q.front = Q.rear = 0;
    return OK;
}

Status DestroyQueue(SqQueue& Q)
{
    if (!Q.base)
        return ERROR;
    free(Q.base);
    Q.front = Q.rear = 0;
    return OK;
}

Status EnQueue(SqQueue& Q, ElemType e)
{
    if (Q.front == (Q.rear + 1) % MAXQSIZE)
        return ERROR;//是否队满
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    return OK;
}

Status DeQueue(SqQueue& Q, ElemType& e)
{
    if (Q.front = Q.rear)
        return ERROR;//空队列
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    return OK;
}

Status GetHead(SqQueue Q, ElemType& e)
{
    if (Q.front == Q.rear)
        return ERROR;//空队列
    e = Q.base[Q.front];
    return OK;
}

Status QueueEmpty(SqQueue Q)
{
    if (Q.front == Q.rear)
        return TRUE;
    return FALSE;
}

链队列：队列的链式存储结构，是一个同时带有队头指针front和队尾指针rear的链表。队头指针指向头结点，队尾指针指向队尾结点即单链表的尾结点，并将队头和队尾指针结合起来构成链队结点。

• 队空条件：Q.front->next == NULL
• 队满条件：不考虑（因为每个结点是动态分配的）
• 进队操作：创建结点p，将其插入到队尾，并由Q.rear指向它
• 出队操作：删除队头的结点。

单链表队列的运算

• 初始化队列算法InitQueue(LinkQueue &Q)
• 销毁队列算法DestroyQueue(LinkQueue &Q)
• 入队列算法EnQueue(LinkQueue &Q, ElemType e)
• 出队列算法DeQueue(LinkQueue &Q, ElemType &e)
• 取队头元素算法GetHead(LinkQueue Q, ElemType &e)
• 判断队空算法QueueEmpty(LinkQueue Q)

代码实现：

#include <cstdio>
#include <cstdlib>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
//数据结点
typedef struct QNode {
    ElemType data;//存放队中元素
    struct QNode* next;//指向下一个结点
}QNode,*QueuePtr;//数据结点类型

//链队结点
typedef struct {
    QNode* front;//队头指针
    QNode* rear;//队尾指针
}LinkQueue;//链队结点类型

Status InitQueue(LinkQueue& Q)
{
    if (!(Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode))))
        return ERROR;
    Q.front->next = NULL;
    return OK;
}

Status DestroyQueue(LinkQueue& Q)
{
    while (Q.front) {
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    return OK;
}

Status EnQueue(LinkQueue& Q, ElemType e)
{
    QueuePtr p;
    if(!(p = (QueuePtr)malloc(sizeof(QNode))))
        return ERROR;//分配失败
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}

Status DeQueue(LinkQueue& Q, ElemType& e)
{
    if (Q.front == Q.rear)
        return ERROR;//队空
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p)
        Q.rear = Q.front;
    free(p);
    return OK;
}

Status GetHead(LinkQueue Q, ElemType& e)
{
    if (Q.front == Q.rear)
        return ERROR;
    QueuePtr p = Q.front->next;
    e = p->data;
    return OK;
}

Status QueueEmpty(LinkQueue Q)
{
    if (Q.front->next == Q.rear)
        return TRUE;
    return FALSE;
}