栈和队列部分伪代码

栈和队列部分伪代码

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

文字思想：
	1)设计一个求单链表表长函数CalLength
	2)创建一个链栈B，初始时B->next = NULL,若L的表长len为奇数，则L依次遍历len/2个结点并将其依次入栈B,L = L->next，L和B依次比较，在L不为空时依次比较，若元素值不等则返回false并跳出循环
	3)若len是偶数，则直接L遍历len/2个结点并将其入栈B，在L不为空时和B逐个比较，若有不相同则返回false，退出循环

typedef char ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

int CalLength(LinkList L) {
    int count = 0;
    while (L->next != NULL) {
        count += 1;
        L = L->next;
    }
    return count;
}

bool isSymmetry(LinkList L) {
    int len = CalLength(L);
    // 跳过头结点
    LNode *subHead = L->next;
    // 创建带头结点的链栈B
    LNode *B = (LNode *)malloc(sizeof(LNode));
    B->next = NULL;
    // 标志
    bool tag = true;
    while (len/2--) {
        // 使用头插法插入
        LNode *curP = subHead;
        curP->next = B->next;
        B->next = curP;
        subHead = subHead->next;
    }
    // 在链表L长度为偶数时，L不需要再后退
    if (len % 2 == 0) {
        // 此时两个指针是对齐的
        while (subHead != NULL) {
            if (subHead->data != B->data) {
                tag = false;
                break;
            }
            subHead = subHead->next;
            B = B->next;
        }
    } else {
        // 再链表长度L为奇数时，L需要再后退一位使得两个链对齐
        subHead = subHead->next;
        while (subHead != NULL) {
            if (subHead->data != B->data) {
                tag = false;
                break;
            }
            subHead = subHead->next;
            B = B->next;
        }
    }
	return tag;
}

时间复杂度：$O(n)$ 空间复杂度：$O(1)$

2、设计一个栈，包含传统的$push、pop、top$方法，此外，再设计一个函数$getMin$，用于返回当前栈内最小的元素。其中函数参数可以自行设计。

文字思想：
	1)设计一个顺序栈
	2)先初始化栈，让top = -1即栈顶指针始终指向栈顶元素的位置
	3)设计入栈函数push，先top+1再存入数据使得栈满足"先进后出"的特性
	4)设计出栈函数pop,先取数再top-1
	5)top函数获取当前栈顶元素
	6)设计函数getMin获取栈内元素最小值

typedef int ElemType;
# define MaxSize 50
typedef struct {
    ElemType datas[MaxSize];
    int top;
}SqStack;

void initSqStack(SqStack &S) {
    S.top = -1;
}

bool pushStack(SqStack &S,ElemType x) {
    // 判断栈是否已满，若满则返回false
    if (S.top == MaxSize - 1) {
        return false;
    }
  	// 使用头插法插入
    S.datas[++top] = x;
    return true;
}

bool popStack(SqStack &S,ElemType &x) {
    // 判断栈是否为空，若为空则操作失败
    if (S.top == -1) {
        return false;
    }
    x = S.datas[top--];
    return true;
}

bool getTop(SqStack S,ElemType &x) {
    // 判断栈是否为空
    if (S.top == -1) {
        return false;
    }
    x = S.datas[top];
    return true;
}

bool getMin(SqStack S,ElemType &min) {
	// 判断栈是否为空
    if (S.top == -1) {
        return false;
    }
    int i;
    min = S.datas[0];
    for (i = 0;i < S.top + 1;i++) {
        if (min > S.datas[i]) {
            min = S.datas[i];
        }
    }
    return true;
}

3、$Q$是一个队列，$S$是一个空栈，实现将队列中的元素逆置的算法

文字思想：
	1)队列特性是"先进先出"，栈特性是"先进后出"
	2)只需要将队列中元素全部入栈后，再由栈内元素出栈入队，则可实现元素逆置

typedef int ElemType;
# define MaxSize 100

// 队列定义
typedef struct {
    ElemType data[MaxSize];
    // 分别是队头指针和队尾指针
    int front,rear;
}SqQueue;

// 栈定义
typedef struct {
    ElemType data[MaxSize];
    int top;
}SqStack;

// 初始化栈
void init(SqStack &S) {
    // 栈顶指针始终指向栈顶元素
    S.top = -1;
}

// 队列是队头指针管理出队，队尾指针管理入队
void deQueue(SqQueue &S,SqStack K) {
    // 在队头指针和队尾指针不相遇时
    while (S.rear != S.front) {
        int data = S.data[S.front++];
        // 入栈
        K.datas[++top] = data;
    }
}

// 再出栈并入队
void deStack(SqQueue &S,SqStack K) {
    // 再栈不为空时
    while (K.top != -1) {
        int data = K.data[top--];
        S.data[S.rear++] = data;
    }
}

4、假设一个算术表达式中包含圆括号、方括号和花括号3种类型的括号，编写一个算法来判别表达式中的括号是否配对，以字符KaTeX parse error: Undefined control sequence: \o at position 2: "\̲o̲"作为算术表达式的结束符

文字思想：
	1)创建栈A
	2)在没遇到右括号时依次将算术表达式的内容入栈A，遇到右括号时和栈A元素比较，若不匹配或者最终栈不为空，则代表括号未匹配，返回false

bool matchBrackets(char str[]) {
    // 初始化栈
    SqStack S;
    initStack(S);
    // 辅助遍历
    char aux,c;
    // 索引字符
    int index = 0;
    while (c = str[index++] != '\0') {
        // 一切左括号都入栈
        if (c == '(' || c == '[' || c == '{') {
            push(S,c);
            // 遇见的时右括号
        } else if(c == ')' || c == ']' || c == '}') {
            // 栈非空
            if (pop(S,aux) == true) {
                // 匹配失败
                if (!((aux == '(' && c == ')') || 
                      (aux == '[' && c == ']') ||
                      (aux == '{' && c == '}')) {
                    return false;
                }
            } else {
                // 栈空了，匹配失败
                return false;
            }
        } else {
            // 非法输入
            return false;
        }
    }
    // 栈空匹配成功，否则匹配失败
    return stackEmpty(S);
}

5、试设计算法，$n$为大于等于0的整数，利用栈设计下列函数的非递归算法

$$P(n)=\{\begin{array}{ll}1& \text{n = 0}\\ n\ast P(n/2)& \text{n > 0}\end{array}$$

文字思想：
	1)如果可以用递归做,写起来很简单
	2)模拟递归实现，递归调用时把相关参数压栈

int CalP(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n*CalP(n/2);
    }
}

# define MaxSize 100

// 用于模拟递归栈，保存相关参数
typedef struct {
    int n,pn;			// pn代表参数为n时的结果
    bool isCalc;		// 判断是否计算完毕
}ArgsFrame;

int calc(int n) {
    // 第一次调用，栈内参数
    ArgsFrame af;
    af.isCalc = false;
    af.n = n;
    
    // 初始化栈
    ArgsFrame stack[MaxSize];
    int top = -1;
    stack[++top] = af;
    
    // 持续处理
    while (true) {
        // 还没有求解
        if (stack[top].isCalc == false) {
            // 递归结束条件，准备返回
            if (stack[top].n == 0) {
                stack[top].isCalc = false;
                stack[top].pn = 1;
            } else {
                // 求子问题，入栈
                ArgsFrame aux;
                aux.isCalc = false;
                aux.n = stack[top].n/2;
                stack[++top] = aux;
            }
        } else {
            // 该问题已经求解，返回出栈
            ArgsFrame aux = stack[top--];
            // 栈顶元素有解了
            stack[top].pn = stack[top].n * aux.pn;
            stack[top].isCalc = true;
        }
        // 最后栈内只有一个元素且已经求解时，这就是最终结果
        if (top == 0 && stack[top].isCalc) {
            break;
        }
    }
    return stack[top].pn;
}