栈

与一般线性表的区别

栈、队列是一种特殊（操作受限）的线性表，区别仅在于运算规则不同（线性表是随机、顺序存取）

顺序栈

定义

#define MAXSIZE 100
typedef struct
{
    SElemType *base;    // 栈底指针
    SElemType *top;        // 栈顶指针
    int stacksize;        // 栈可用的最大容量
}SqStack;

解释：

base指针初始化完成后始终指向栈底的位置，为NULL则表明栈结构不存在

top指针初值指向栈底，每插入新的栈顶元素是，指针top增1，删除时减1；栈非空时，top指针始终指向栈顶元素的上一个位置

初始化

1. 为顺序栈动态分配一个最大容量为MAXZISE的数组空间，使base指向这段空间的基地址，即栈底
2. 栈顶指针top初始化为base，表示栈为空
3. stacksize置为栈的最大容量MAXSIZE

Status InitStack(SqStack &S)
{
    S.base = new SElemType[MAXSIZE];
    if(!S.base)                // 为顺序栈动态分配一个最大容量为MAXZISE的数组空间
        return OVERFLOW;    // 存储分配失败
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

判断是否为空

int StackEmpty(SqStack &S)
{
    if(S.top==S.base)
        return 1;    // 为空时返回1
    else
        return 0;    // 不空时返回0
}

求栈长

int StackLength(SqStack &S)
{
    return S.top-S.base;
}

清空

Status ClearStack(SqStack &S)
{
    if(S.base)
        S.top=S.base;
    return OK;
}

销毁

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

入栈

1. 判断栈是否满，若满返回ERROR
2. 将新元素压入栈顶，栈顶指针加1

Status Push(SqStack &S, SElemType e)
{
    if(S.top-S.base==S.stacksize)
        return ERROR;
    *s.top++=e;        // 这里是先赋值再指向下一位
    return OK;
}

出栈

1. 判断栈是否空，若空返回ERROR
2. 栈顶指针减1，栈顶元素出栈

Status Pop(SqStack &S, SElemType &e)
{
    if(S.top==S.base)
        return ERROR;
    e = *--S.top;        // 这里是先指向上一位再赋值
    return Ok;
}

取栈顶元素

Status GetTop(Sqstack S, SElemType &e)
{
    if(S.top==S.base)
        return Error;
    e = *(S.top-1);        // 这里不能使用S.top--,否则会使top指针指向的位置发生改变
    return OK;
}

链栈

运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点

定义

typedf struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStack;
LinkStack S;

初始化

void InitStack(LinkStack &S)
{
    S = NULL;
}

判断是否为空

Status StackEmpty(LinkStack S)
{
    if(S == NULL)
        return TRUE;
    else
        return FALSE;
}

进栈

Status Push(LinkStack &S, SElemType e)
{
    p = new StackNode;
    if(!p)
        exit(OVERFLOW);
    p->data = e;
    p->next = S;
    S = p;
    return OK;
}

出栈

Status Pop(LinkStack &S, SElemType &e)
{
    if(S == NULL)
        return ERROR;
    e = S->data;
    p = S;
    S = S->next;
    delete p;
    return OK;
}

取栈顶元素

SElemType GetTop(LinkStack S)
{
    if(S == NULL)
        exit(1);
    else
        return S->data;
}

栈与递归

常用到递归

• 递归定义的数学函数：阶乘函数、2阶Fibonaci数列
• 具有递归特性的数据结构：树、广义表
• 可递归求解的问题：迷宫问题、Hanoi塔问题

队列

循环队列

定义

#define MAXQSIZE 100
typedef struct
{
    QElemType *base;    // 存储空间的基地址
    int front;    // 头指针
    int rear;    // 尾指针
}SqQueue;

分析

队空：front==rear

入队：base[rear++]=x

出队：x=base[front++]

但是会存在假溢出的情况：头指针前为空，而尾指针已到达最大空间的地址

解决方案就是将队列改为循环队列，即base[0]接在base[MAXQSIZE-1]之后，若rear+1=MAXQSIZE则令rear=0

此时

队空：front==rear

入队：base[rear]=x; rear=(rear+1)%MAXQSIZE;

出队：x=base[front]; front=(front+1)%MAXQSIZE;

队满：(rear+1)%MAXQSIZE=front;

初始化

Status InitQueue(SqQueue &Q)
{
    Q.base = new QElemType[MAXQSIZE];
    if(!Q.base)
        exit(overflow);
    Q.front = Q.rear = 0;
    return OK;
}

求队列长度

int QueueLength(SqQueue Q)
{
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

入队

Status EnQueue(SqQueue &Q, QElmeType e)
{
    if((Q.rear + 1) % MAXQSIZE == Q.front)
        return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    return OK;
}

出队

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

链队列

略