数据结构-栈

目录

1、栈的特点

2、顺序栈的常用操作

3、顺序栈的应用

 4、链栈的常用操作

5、链栈的应用

---

1、栈的特点

1）先进后出，后进先出

2）栈顶指针指向当前位置的元素

2、顺序栈的常用操作

#include<iostream>
using namespace std;
#define MaxSize 50typedef struct {ElemType data[MaxSize];  //存放栈中的数据元素int top;  //栈顶指针，即存放栈顶元素在data数组中的下标
}SqStack;typedef int ElemType;//初始化栈
void InitStack(SqStack*& s) {s = (SqStack*)malloc(sizeof(SqStack));  //分配一个顺序栈空间，首地址存放在s中s->top = -1;  //栈顶指针置为-1
}//销毁栈
void DestroyStack(SqStack*& s) {free(s);
}//判断栈是否为空
bool StackEmpty(SqStack* s) {return(s->top == -1);
}//进栈
bool Push(SqStack*& s, ElemType e) {if (s->top == MaxSize - 1) {  //栈满的情况，即栈上溢出return false;  }s->top++;  //栈顶指针增加1s->data[s->top] = e;  //元素e放在栈顶指针处return true;
}//出栈
bool Pop(SqStack*& s, ElemType& e) {if (s->top == -1) {  //栈为空的情况，即栈下溢出return false;}e = s->data[s->top];  //取栈顶元素s->top--;   //栈顶指针减小1return true;
}//取栈顶元素
bool GetTop(SqStack* s, ElemType& e) {if (s->top == -1) {  //栈为空的情况，即栈下溢出return false;}e = s->data[s->top];return true;
}int main() {}

3、顺序栈的应用

判断一个字符串是否为对称串

//判断一个字符串是否为对称串
bool symmetry(ElemType str[]) {ElemType e;SqStack* st;  //定义顺序栈指针InitStack(st);  //初始化栈for (int i = 0; str[i] != '\0'; i++) {  //将str的所有元素进栈Push(st, str[i]);}for (int i = 0; str[i] != '\0'; i++) {  //处理str的所有字符Pop(st, e);  //退栈元素eif (str[i] != e) {  //若e与当前字符串不同表示不是对称串DestroyStack(st);  //销毁栈return false;  //返回假}}DestroyStack(st);  //销毁栈return true;  //返回真
}

 4、链栈的常用操作

不存在栈满上溢出的情况

#include<iostream>
using namespace std;typedef struct linknode {ElemType data;  //数据域struct linknode* next;  //指针域
}LinkStNode;  //链栈结点类型typedef int ElemType;//初始化栈
void InitStack(LinkStNode*& s) {s = (LinkStNode*)malloc(sizeof(LinkStNode));s->next = NULL;
}//销毁栈
void DestroyStack(LinkStNode*& s) {LinkStNode* pre = s, * p = s->next;  //pre指向头结点，p指向首结点while (p != NULL) {  //循环到p为空free(pre);  //释放pre结点pre = p;   //pre、p同步后移p = pre->next;}free(pre);  //此时pre指向尾结点，释放其空间
}//判断栈是否为空
bool StackEmpty(LinkStNode* s) {return(s->next == NULL);
}//进栈-头插法
bool Push(LinkStNode*& s, ElemType e) {LinkStNode* p;p = (LinkStNode*)malloc(sizeof(LinkStNode));  //新建结点pp->data = e;  //存放元素p->next = s->next;  //将p结点插入作为首结点s->next = p;return true;
}//出栈
bool Pop(LinkStNode*& s, ElemType& e) {LinkStNode* p;if (s->next == NULL) {  //栈空的情况return false;  //返回假}p = s->next;  //p指向首结点e = p->data;  //提取首结点值s->next = p->next;  //删除首结点free(p);  //释放被删结点的存储空间return true;  //返回真
}//取栈顶元素
bool GetTop(LinkStNode*& s, ElemType& e) {if (s->next == NULL) {  //栈空的情况return false;  //返回假}e = s->next->data;  //提前首结点值return true;  //返回真
}int main() {}

5、链栈的应用

判断输入的表达式中括号是否匹配(只含左右括号)

//判断输入的表达式中括号是否匹配(只含左右括号)
bool Match(char exp[], int n) {int i = 0; char e;bool match = true;LinkStNode* st;InitStack(st);  //初始化链栈while (i < n && match) {  //遍历exp中所有字符if (exp[i] == '(') {  //当前字符为左括号，将其进栈Push(st, exp[i]);}else if (exp[i] == ')') {  //当前字符为右括号if (GetTop(st, e) == true) {   //成功取栈顶元素eif (e != '(') {  //栈顶元素不为左括号时match = false;  //表示不匹配}else {  //栈顶元素为左括号时Pop(st, e);  //将栈顶元素出栈}}else {  //无法取栈顶元素时表示不匹配match = false;}}i++;  //继续处理其他字符}if (!StackEmpty(st)) {  //栈不为空时表示不匹配match = false;}DestroyStack(st);  //销毁栈return match;
}