栈和队列算法 部分练习

利用一个栈实现以下递归函数的非递归计算：

\[ P_n(x)=\left\{ \begin{array}{aligned} 1, && n=0 \\ 2x, && n=1\\ 2xP_{n-1}(x)-2(n-1)P_{n-2}(x), && n>1 \end{array} \right. \]

首先我们定义栈的初始结构，栈应该要记录每次对应的n值，和函数值。

struct stack
{
    int n;
    double val;
} st[maxsize];

算法的代码描述如下：

double nonRecursive(int n, double x) {
    if (n == 0)
    {
        return 1;
    }
    stack st[maxsize];
    int top = -1; // 栈顶指针
    double funVal1 = 1, funVal2 = 2 * x;
    for (int i = n; i >= 2; i--) // 把每个递归的函数压入栈
    {                            // n越大的部分越靠近栈低
        st[++top].n = i;
    }
    while (top >= 0) // 出栈计算，栈顶是n=2的元素
    {
        st[top].val = 2 * x * funVal2 - 2 * (st[top].n - 1) * funVal1;
        funVal1 = funVal2;  // funVal2实际上代表了P(n-1), funVal1代表了P(n-2)
        funVal2 = st[top].val;
        top--; 
    }
    return funVal2;
}

假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，可以操作的序列称为合法序列,否则称为非法序列。写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false(假定被判定的操作序列已存入一维数组中)。

算法代码描述如下：

bool isLegalSq(char input[]) {
    int pop = 0, push = 0;
    int index = 0;
    while (input != '\0'){
        if (input[index] == 'I')
        {
            push++;
        } else
        {
            pop++;
        }
        if (pop>push)
        {
            return false;
        }
    }
    return (pop != push) ? false : true;
}

设单链表的表头指针为L，结点结构由 data和next两个域构成，其中 data域为字符型。试设计算法判断该链表的全部n个字符是否中心对称。例如xyx,xyyx都是中心对称。

算法代码描述如下：

// 因为已知链表长度为n，可以用一个字符栈存取前n/2个字符，后逐步出栈比较。
bool isSymmetrical(LNode *head, int n) {
    char stack[n / 2];
    int i = 0;
    while (i < n/2) //默认链表不带头节点。
    {
        stack[i] = head->data;
        head = head->next;
        i++;
    }
    i--;
    if (n % 2 != 0) //如果长度为奇数，跳过中间节点。
    {
        head = head->next;
    }
    while (head != null && stack[i] == head->data)
    {
        i--;
        head = head->next;
    }
    if (i == -1)
    {
        return true;
    } else
    {
        return false;
    }
}

设有两个栈s1，s2 都采用顺序栈方式，并共享一个存储区\([0, \ldots ,maxsize-1]\)，为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式。试设计s1，s2有关入栈和出栈的操作算法。

首先我们需要定义栈的结构：

#define maxsize 100
#define Elemtype int

typedef struct 
{
    Elemtype s[maxsize];
    int top[2]; // 定义栈顶位置，top[0]起始位置为-1，top[1]起始位置为maxsize
}stack;

入栈操作：

shareStack s;
//stack取值为1 => 左栈，2 => 右栈；
bool push(Elemtype x, int stack) { //stack取值为1 => 左栈，2 => 右栈；
    if (stack < 0 || stack > 1)
    {
        return 0;
    }
    if (s.top[0] + 1 == s.top[1]) { //栈满
        return 0;
    }
    switch (stack)
    {
    case 1:
        s.stack[++s.top[0]] = x;
        return true;
        break;

    case 2:
        s.stack[--s.top[1]] = x;
        return true;
    }
}

出栈操作：

Elemtype pop(int stack) {
    if (stack < 0 || stack > 1)
    {
        return 0;
    }
    switch (stack)
    {
    case 1:
        if (s.top[0] == -1)
        {
            return -1; //栈空
        } else
        {
            return s.stack[s.top[0]--];
        }
        break;
    
    case 2:
         if (s.top[1] == maxsize)
        {
            return -1; //栈空
        } else
        {
            return s.stack[s.top[1]++];
        }
    }
}

若希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或1来区分队头指针front和队尾指针rear相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队和出队算法。

队列的数据结构定义：

#define maxsize 100
#define Elemtype int

typedef struct 
{
    Elemtype queue[maxsize];
    int front, rear;
    int tag;
}queue;

队满：q.front = q.rear && tag == 1;

队空：q.front = q.rear && tag == 0;

入队操作后：tag = 1，出队操作后：tag = 0。

入队算法代码细节如下：

Queue q;
bool enQueue(Queue &q, Elemtype x) {
    if (q.front == q.rear && q.tag == 1)
    {
        return false;
    } else
    {
        q.queue[q.rear] = x;
        q.rear = (q.rear + 1) % maxsize;
        q.tag = 1;
        return true;
    }
}

出队操作算法细节如下：

bool deQueue(Queue &q, Elemtype &x) {
    if (q.front == q.rear && tag == 0)
    {
        return false;
    } else
    {
        x = q.queue[q.front];
        q.front = (q.front + 1) % maxsize;
        q.tag = 0;
        return true;
    }
}

利用两个栈S1，S2来模拟一个队列，已知栈的4个运算定义如下:

Push(S,x);        //元素x入栈S
Pop(S,x);         //S出栈并将出栈的值赋给x
StackEmpty(S);    //判断栈是否为空
StackOverflow(S); //判断栈是否满

/* 如何利用栈的运算来实现该队列的3个运算(形参由读者根据要求自己设计)? */
Enqueue;    //将元素x入队
Dequeue;    //出队,并将出队元素存储在x中
QueueEmpty; //判断队列是否为空

解答：

对S2的出栈操作用做出队，若S2为空，则先将S1中的所有元素送入S2。
对S1的入栈操作用做入队，若S1满，必须先保证S2为空，才能将s1中的元素全部插入S2中。

入队操作的算法实现细节如下：

bool enQueue(Stack S1, Stack S2, Elemtype x) { {
   if (!StackOverflow(S1))
   {
       Push(S1, x);
       return true;
   }
   else if (StackOverflow(S1) && !StackEmpty(S2))
   {
       return false;
   } 
   else
   {
       while (!StackEmpty(S1)) 
       {
           Pop(S1, temp);
           Push(S2, temp);
       }
       Push(S1, x);
       return true;
   }
}

出队操作的算法实现细节如下：

bool deQueue(Stack S1, Stack S2, Elemtype &x) {
    if (StackEmpty(S2) && StackEmpty(S1))
    {
        return false;
    }
    else if (!StackEmpty(S2))
    {
        Pop(S2, x);
    } 
    else
    {
        while (!StackEmpty(S1))
        {
            Pop(S1, x);
            Push(S2, x);
        }
        Pop(S2, x);
    }
}

队列判空操作的算法实现细节如下：

bool queueEmpty(Stack S1, Stack S2) {
    if (StackEmpty(S1) && StackEmpty(S2))
    {
        return true;
    }
    else
    {
        return false;
    }
}

解答：

顺序存储无法满足要求2的队列占用空间随着入队操作而增加。对于要求3,出队后的结点并不真正释放，用队头指针指向新的队头结点，新元素入队时，有空余结点则无须开辟新空间，赋值到队尾后的第一个空结点即可，后用队尾指针指向新的队尾结点，这就需要设计成一个首尾相接的循环单链表，类似于循环队列的思想。设置队头、队尾指针后,链式队列的入队操作和出队操作的时间复杂度均为O(1)。

假设一个算术表达式中包含圆括号、方括号和花括号3种类型的括号，编写一个算法来判别表达式中的括号是否配对，以字符“\0”作为算术表达式的结束符。

将遇到的全部左括号压入栈中，碰到右操作数时出栈比较，若不等，则说明不配对。

算法的代码实现细节如下：

bool bracketsCheck(char *str){
    InitStack(S);
    int i = 0;
    while (str[i] != '/0')
    {
        switch(str[i]) {
        //左括号入栈
        case '(':
            push(S, '(');
            break;
        case '[':
            push(S, '[');
            break;
        case '{':
            push(S, '{');
            break;
        //遇到右括号,检测栈顶
        case ')':
            pop(S, e);
            if (e != '(')
            {
                return false;
            }
            break;
        case ']':
            pop(S, e);
            if (e != '[')
            {
                return false;
            }
            break;
        case '}':
            pop(S, e);
            if (e != '{')
                return false;
            break;
        default:
            break;
        }
        i++;
    } 
    if(!IsEmpty(S)){
        printf("括号不匹配\n");
        return false;
    } else {
        printf("括号匹配\n");
        return true;
    }
}

算法的代码实现细节如下：

void trainArrange(char *train){
//用字符串train表示火车,H表示硬座,s表示软座
    char *p = train, *q = train, c;
    stack s;
    InitStack(s);
    while(*p != null) {
        if(*p == 'H') {
            push(s, *p); //把H存入栈中
        } else {
            *(q++) = *p; //把s调到前部
        }
        p++;
        while (!StackEmpty(s))
        {
            pop(s, c);
            *(q++) = c;
        }
    }
}

某汽车轮渡口，过江渡船每次能载10辆车过江。过江车辆分为客车类和货车类，上渡船有如下规定：同类车先到先上船；客车先于货车上船，且每上4辆客车，才允许放上1辆货车；若等待客车不足4辆，则以货车代替；若无货车等待，允许客车都上船。试设计一个算法模拟渡口管理。

算法的代码实现细节如下：

void manager(){
    Queue q;  //过江渡船载渡队列
    Queue qK; //客车队列
    Queue qH; //货车队列
    int i = 0, j = 0; //j表示渡船上的总车辆数
    while (j < 10) //不足10辆时
    {
        //客车队列不空,则未上足4辆
        if (!queueEmpty(qK) && i < 4)
        {
            deQueue(qK, x); //从客车队列出队
            enQueue(q, x);  //客车上渡船
            i++; //客车数加1
            j++; //渡船上的总车辆数加1
        }
        else if (i == 4 && !queueEmpty(qH)) //客车已上足4辆
        { 
            deQueue(qH, x); //从货车队列出队
            enQueue(q, x);  //货车上渡船
            j++; //渡船上的总车辆数加1
            i = 0; //每上一辆货车,i重新计数
        }
        else //其他情况(客车队列空或货车队列空)
        {
            //客车队列空
            while (j < 10 && i < 4 && !queueEmpty(qH))
            { 
                deQueue(qH, x); //从货车队列出队
                enQueue(q, x);  //货车上渡船
                i++; //i计数,当i>4时,退出本循环
                j++; //渡船上的总车辆数加1
            }
            i = 0;
        }
        if (queueEmpty(qK) && queueEmpty(qH))
        {
            j = 11; //若货车和客车加起来不足10辆
        } 
}

爱喝茶的仙人掌

栈和队列算法部分练习

利用一个栈实现以下递归函数的非递归计算：

设单链表的表头指针为L，结点结构由 data和next两个域构成，其中 data域为字符型。试设计算法判断该链表的全部n个字符是否中心对称。例如xyx,xyyx都是中心对称。

设有两个栈s1，s2 都采用顺序栈方式，并共享一个存储区\([0, \ldots ,maxsize-1]\)，为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式。试设计s1，s2有关入栈和出栈的操作算法。

若希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或1来区分队头指针front和队尾指针rear相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队和出队算法。

利用两个栈S1，S2来模拟一个队列，已知栈的4个运算定义如下:

假设一个算术表达式中包含圆括号、方括号和花括号3种类型的括号，编写一个算法来判别表达式中的括号是否配对，以字符“\0”作为算术表达式的结束符。