1.栈的基本概念
1.1.栈的定义
栈是只允许在一端进行插入或删除的线性表
栈顶：允许进行插入删除的那一段
栈底：不允许进行插入删除的另一端
进栈顺序：1->2->3->4->5
出栈顺序：5->4->3->2->1（后进先出：LIFO）
1.2.栈的基本操作
initStack(&S); //初始化一个空栈S stackEmpty(S); //判断栈空 push(&S, x); //进栈 pop(&S, &x); //出栈 getTop(&S, &x); //读栈顶元素 destroyStack(&S); //销毁栈
n个不同元素进栈，出栈的不同序列为
2.顺序栈栈的基本操作
2.1.顺序栈的初始化
- 采用定义一组地址连续的存储单元存放元素（数组）
- 申明一个指针指向当前栈顶元素的位置。栈空时，top的值设置为-1；每加入一个元素，top的值+1，直到栈满，即maxSize - 1（数组的特性，下标从0开始）
#define maxSize 50 //定义栈中的最大元素 typedef struct { elemType data[maxSize]; //静态数组存放栈中元素 int top; //栈顶指针 }sqStack; //初始化栈 void initStack(sqStack &S){ S.top = -1; //初始化栈顶指针 } //判断栈空 bool stackEmpty(sqStack S){ if (S.top == -1) return true; //栈空 else return false; //栈不空 } void testStack(){ sqStack S; initStack(S); //后续操作 }
2.2.进栈操作
//新元素入栈 bool push(sqStack &S, elemType e){ if(S.top == maxSize - 1) return false; //栈满，返回false else{ //等价于S.data[++S.top] = x; S.top++; //栈顶指针+1（数组特性） S.data[S.top] = x; //新元素入栈 return true } }
2.3.出栈操作
出栈操作数据实际上还存在于数组中，即内存还存有数据，但是逻辑上删除了
//出栈 bool pop(sqStack &S, elemType &e){ if (S.top == -1) return false; //栈空，返回false else { x = S.data[top--]; //先将x从栈顶取出，并带回，再对top进行--操作 return true; } }
2.4.读栈顶元素
仅读取的话，不需要对top指针进行修改
//读栈顶元素 bool getTop(sqStack S, elemType &e){ if(S.top == -1) return false; //栈空，返回false else{ e = S.data[S.top]; //读栈顶元素 return true; } }
2.5.共享栈
存元素时，top1指针往下递减，top0指针往上递增
栈满条件：top0 +1 == top1
#define maxSize 10 typedef struct{ elemType data[maxSize]; int top0; int top1; }shStack; void initStack{ S.top0 = -1; //初始化栈顶指针 S.top1 = maxSize; }
3.王道课后题
bool isLegal(string A) { int stack = 0; for (int i = 0; A[i] != '\0'; i++) { if (A[i] == 'I') stack++; else stack--; if (stack < 0) return false; } return true; }
//链表方法 bool isSymmetry(linkList L) { LNode* fast = L->next, * slow = L->next; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } //p指向后半链表的第一个节点 LNode* p = slow->next, *temp, *s; //将表分为前半链表和后半链表 slow->next = NULL; //将s指向后半链表的第一个节点，p指向后半链表的最后一个节点 s = p; while (p->next) p = p->next; //通过s和p将后半链表逆置 while (s != p) { temp = s->next; s->next = p->next; p->next = s; s = temp; } //将s指向前半链表的第一个节点 s = L->next; //依次对比前半链表和逆置后的后半链表 while (p && s) { if (p->data != s->data) break; p = p->next; s = s->next; } //如果p在指向NULL之前就跳出循环，则不对称，返回false if (p) return false; else return true; }
//栈 bool isSymmetry(linkList L, int n) { //创建数组作为栈，并初始化为0 int* arr = (int*)malloc(sizeof(int) * (n / 2)); memset(arr, 0, sizeof(char) * (n / 2)); LNode* p = L->next; int i; //遍历前半链表，并将其数据压入栈中 for (i = 0; i < n / 2; i++) { arr[i] = p->data; p = p->next; } //i退一格，使其指向栈顶元素 i--; //如果是奇数个，当前p指向的是最中间节点 //需要往后一个节点才是下半个链表的第一个节点 if (n % 2) p = p->next; //依次判断下半链表元素是否与数组内元素相等 while (p && p->data == arr[i]) { i--; p = p->next; } //判断是否提前跳出循环 if (p) return false; else return true; }
#define maxSize 10 typedef struct { elemType data[maxSize]; int s1, s2; }sqStack; sqStack S; //入栈 bool push(int i, sqStack S, elemType e) { //插入的栈号不对 if (i < 1 || i > 2) return false; //栈满 if (S.s1 + 1 == S.s2) return false; 入栈 if (i == 1) S.data[++S.s1] = e return true;; else S.data[--S.s2] = e return true;; } //出栈 bool pop(int i, sqStack S, elemType e) { //出栈的栈号不对 if (i < 1 || i > 2) return false; //栈空 if (i == 1 && S.s1 == -1) return false; else if (i == 2 && S.s2 == maxSize) return false; //出栈 if (i == 1) e = S.data[S.s1--] return true; else e = S.data[S.s2++] return true; }
