第三章 栈和队列

一 栈

单选题，填空题

栈是限定在表的一段进行插入和删除运算的线性表，通常将插入，删除的一端称为栈顶，另一端称为栈底。不含元素的空表称为空栈。栈的操作具有先进后出和后进先出的特点。栈的运算主要有置空栈，判栈空，判栈满，进栈，退栈和取栈顶元素六种。

填空题

栈的顺序存储结构为顺序栈，栈的链式存储结构为链栈。

填空题，算法阅读题

1 顺序栈，在顺序栈上实现的六种基本运算，具体算法如下：

// 以下代码为伪代码

// 1 置空栈
void InitStack(SeqStack *S)
{
    S->top=-1;
}

// 2 判栈空
int StackEmpty(SeqStack *S)
{
    return S->top==-1;
}

// 3 判栈满
int StackFull(SeqStack *S)
{
    return S->top==StackSize-1;
}

// 4 进栈（入栈）
void Push(SeqStack *s, DataType x)
{
    if (StackFull(S))
        printf("stack overflow");
    else{
        S->top=S->top+1;
        S->data[S->top]=x;
    }
}

// 5 退栈（出栈）
DataType Pop(SeqStack *S)
{
    if(StackEmpty(S)){
        printf("stack underflow");
        exit(0);
    } 
    else
        return S->data[S->top--];
}

// 6 取栈顶元素（不改变栈顶指针）
DataType GetTop(SeqStack *S)
{
    if(StackEmpty(S)){
        printf("stack empty");
        exit(0);
    } 
    else
        return S->data[S->top];
}

2 栈链，在栈链上实现四种基本运算，具体算法如下：

// 以下代码为伪代码

// 1 判栈空
int StackEmpty(LinkStack top)
{
    return top==NULL;
}

// 2 进栈（入栈）
LinkStack Push(LinkStack top, DataType x)
{
    StackNode *p;
    p=(StackNode *)malloc(sizeof(StackNode));
    p->data=x;
    p->next=top;
    top=p;
    return top;
}

// 3 退栈（出栈）
LinkStack Pop(LinkStack top, DataType *x)
{
    StackNode *p=top;
    if(StackEmpty(top)) {
        printf("stack empty");
        exit(0);
    } else {
        *x=p->data;
        top=p->next;
        free(p);
        return top;
    }
}

// 4 取栈顶元素
DataType GetTop(LinkStack top)
{
    if(StackEmpty(top)) {
        printf("stack empty");
        exit(0);
    }
    else 
        return top->data;
}

单选题，填空题

设S是SeqStack类型的顺序栈，S.data[0]是栈底元素，那么栈顶S.data[top]是正向增长的，即进栈是需要将S.top加1，退栈是需要将S.top减1。因此，S.top<0表示空栈，S.top=StackSize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”；当栈空时再做退栈运算也将产生溢出，简称“下溢”。

二 栈的应用举例

回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但是“good”不是回文，试写一个算法判定给定的字符向量是否为回文。

int IsHuiwen(char *t)
{
    SeqStack s;
    int i, len;
    char temp;
    InitStack(&s);
    len=strlen(t);
    for (i=0; i<len/2; i++)
        Push(&s, t[i]);
    while(!StackEmpty(&s))
    {
        temp=Pop(&s);
        if(temp!=t[i]) return 0;
        else i++;
    }
    return 1;
}

三 队列

单选题，填空题

队列也是一种操作受限的线性表，它只允许在表的一端进行元素插入，而在另一端进行元素删除。允许插入的一端称为队尾，允许删除的一端称为队头。队列的操作具有先进先出的特点。队列的基本操作有置空队列，判队空，入队列，出队列和取队头五种。

解答题

由于顺序队列在一定条件下会产生溢出，为了充分利用数组空间，克服上溢，可将数组空间想象为一个环状空间，并称这种环状数组表示的队列为循环队列。

单选题，填空题

1 循环队列，循环队列基本运算和各算法描述如下：

// 1 置空队列
void InitQueue(CirQueue *Q)
{
    Q->front=Q->rear=0;
}

// 2 判队空
int QueueEmpty(CirQueue *Q)
{
    return Q->rear==Q->front;
}

// 3 判队满
int QueueFull(CirQueue *Q)
{
    return (Q->rear+1) % QueneSize==Q->front;
}

// 4 入队列
void EnQueue(CirQueue *Q, DataType x)
{
    if(QueueFull(Q))
        printf("Queue overflow");
    else {
        Q->data[Q->rear]=x;
        Q->rear=(Q->rear+1)%QueueSize;
    }
}

// 5 取队头元素
DataType GetFront(CirQueue *Q)
{
    if(QueueEmpty(Q)) {
        printf("Queue empty");
        exit(0);
    } else
        return Q->data[Q->front]
}

// 6 出队列
DataType DeQueue(CirQueue *Q)
{
    DataType x;
    if(QueueEmpty(Q)){
        printf("Queue empty");
        exit(0);
    }
    else {
        x=Q->data[Q->front];
        Q->front=(Q->front+1)%QueueSize;
        return x;
    }
}

2 链队列，带头结点链队列上的基本算法如下：

// 1 构造空队列
void InitQueue(LinkQueue *Q)
{
    Q->front=(QueueNode *)malloc(sizeof(QueueNode));
    Q->rear=Q->front;
    Q->rear->next=NULL;
}

// 2 判队空
int QueueEmpty(LinkQueue *Q)
{
    return Q->rear==Q->front;
}

// 3 入队列
void EnQueue(LinkQueue *Q, DataType x)
{
    QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));
    p->data=x;
    p->next=NULL;
    Q->rear->next=p;
    Q->rear=p;
}

// 4 取队头元素
DataType GetFront(LinkQueue *Q)
{
    if(QueueEmpty(Q)) {
        printf("Queue underflow");
        exit(0);
    } else
        return Q->front->next->data;
}

// 5 出队列
DataType Dequeue(LinkQueue *Q)
{
    QueueNode *P;
    if (QueueEmpty(Q)) {
        printf("Queue underflow");
        exit(0);
    } else {
        p=Q->front;
        Q->front=Q->front->next;
        free(p);
        return (Q->front->data);
    }
}