栈 队列专题

typedef struct {BiTree data[MaxSize];int top;
}SqStack;typedef struct {BiTree data[MaxSize];int front, rear;
}SqQueue;//初始化栈
void InitStack(SqStack& s) {s.top = -1;
}//栈判空
bool StackIsEmpty(SqStack s) {if (s.top == -1)return false;elsereturn true;
}//入栈
bool push(SqStack& s, BiTree x) {if (s.top == MaxSize - 1) {return false; //栈满}s.data[++s.top] == x;return true;
}//出栈
bool pop(SqStack& s, BiTree& x) {if (s.top == -1) {return false;}x = s.data[s.top--];return true;
}//获取栈顶元素
bool GetTop(SqStack s, BiTree& x) {if (s.top == -1)return false;x = s.data[s.top];return true;
}//初始化队列
void InitQueue(SqQueue& Q) {Q.front = Q.rear = 0;
}//判空
bool QueueIsEmpty(SqQueue Q) {if (Q.rear == Q.front) return true;else return false;
}//入队
bool EnQueue(SqQueue& Q, BiTree x) {//队满if ((Q.front + 1) % MaxSize == Q.front) {return false;}Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MaxSize;return true;
}//出队
bool DeQueue(SqQueue& Q, BiTree x) {if (Q.rear == Q.front) {return false;}x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;return true;
}

typedef struct {int data[MaxSize];int top;
} SqStack;typedef struct {int data[MaxSize];int front, rear;int tag;
} SqQueue;//初始化栈
void InitStack(SqStack *S) {(*S).top = -1;
}//判空
int StackIsEmpty(SqStack S) {if (S.top == -1) return 0;return 1;
}//入栈
int push(SqStack *S, int x) {//判断栈满if ((*S).top == MaxSize - 1) return 0;(*S).data[++(*S).top] = x;return 1;
}//出栈
int pop(SqStack *S, int *x) {//判断栈空if ((*S).top == -1) return 0;*x = (*S).data[(*S).top--];return 1;
}//初始化队列
void InitQueue(SqQueue *Q) {(*Q).rear = (*Q).front = 0;(*Q).tag = 0;
}//判空
int QueueIsEmpty(SqQueue Q) {if (Q.rear == Q.front && Q.tag == 0) return 0;return 1;
}//入队
int EnQueue(SqQueue *Q, int x) {//队满if (Q->rear == Q->front && Q->tag == 1) return 0;(*Q).data[Q->rear] = x;Q->rear = (Q->rear + 1) % MaxSize;return 1;
}//出队
int DeQueue(SqQueue *Q, int *x) {//队空if (Q->rear == Q->front && Q->tag == 0) return 0;x = Q->data[Q->front];Q->front = (Q->front + 1) % MaxSize;return 1;
}//将队列元素逆置
void Inversion(SqQueue *Q, SqStack *S) {int x;while (!QueueIsEmpty(*Q)) {DeQueue(Q, &x);push(S, x);}while (!StackIsEmpty(*S)) {pop(S, &x);EnQueue(Q, x);}
}//中心回文
int Palindrome(char t[]) {int n = strlen(t);int i = 0;char c;SqStack S;//前半段栈while (i < n / 2) {push(&S, t[i]);i++;}//长度为偶数则不用移 奇数移动一位if (n % 2 != 0)i++;//指针逐步后移 栈元素逐步出栈 依次比较while (!StackIsEmpty(S)) {pop(&S, c);if (c != t[i]) return 0;i++;}
}//括号匹配
//分析； 1.如果遇到做括号则直接入栈
//      2.如果遇到右括号 栈顶元素出栈
//              a. 进行匹配栈顶元素是否匹配 不匹配直接退出
//              b. 匹配则继续
//      3.循环结束如果栈中仍有剩余元素则括号不匹配
//        否则匹配
//
int BracketCheck(char *str) {SqStack S;int i = 0;char c;while (str[i] != '\0') {switch (str[i]) {case '(':push(&S, '(');break;case '[':push(&S, '[');break;case '{':push(&S, '{');break;case ')':pop(&S, &c);if (c != '(') return 0;break;case ']':pop(&S, &c);if (c != '[') return 0;break;case '}':pop(&S, &c);if (c != '{') return 0;break;}//switchi++;}//whileif (!StackIsEmpty(S)) {printf("括号不匹配");return 0;} else {printf("括号匹配");return 1;};
}