《数据结构打卡》第15天(栈篇)
栈的特点:
- 定义:栈是一种只能在一端进行插入或删除的线性表,是操作受限的线性表。
- 栈的主要特点是后进先出(LIFO),即后进来的元素先出栈,每次进栈的数据元素都放在原来栈顶元素之前成为新的栈顶元素,每次出栈的都是当前栈顶元素。
1、顺序栈的四个要素 栈空:s.top == -1; 栈满:s.top == MaxSize-1(data数组的最大下标); 入栈:先移动栈顶指针,然后将元素e入栈到栈顶; 出栈:先用元素e取出栈顶元素,再移动栈顶指针 栈的抽象数据类型:
typedef struct SqStack{ ElemType data[MaxSize]; //定义栈的存储容量,用于存储栈中元素 int top; //定义栈的栈顶指针 }//SqStack 顺序栈的类型
1.栈的初始化
void InitStack(SqStack &S){ s = (SqStack * )malloc(sizeof(SqStack)); //分配一个栈s的空间 s.top = -1; //设栈的指针指向为空 }
2.顺序栈的入栈push(&s,e)
Status Push(SqStack &S,SElemType e){ if(s.top == MaxSize-1) return error; //判断栈满 s.top++; //1.先移动栈顶指针,top指针增1 s.data[s.top] = e; //2.再存入元素 return ok; }
2.顺序栈的出栈pop(&s,&e)
Status Pop(SqStack &S,SElemType &e){ if(s.top == -1) return error; //判断栈空 *e = s.data[s.top]; //1.先取出元素 s.top--; //2.再移动栈顶指针;top指针减1 return ok; }
3.取栈顶元素GetTop(s,&e)
Status GetTop(SqStack S,SElemType &e){ if(s.top == -1) return error; //判断栈空 *e = s.data[s.top]; //取出栈顶元素 return ok; //其实取栈顶元素和顺序出栈一样,不同点在于top指针不用移动。 }
2、链式栈:
-
链式栈基本不存在栈满的情况,链栈的头指针就是栈顶 链栈为空的条件:s->next == Null 链栈中指针指向的方向与单链表的相反,s->next域通常指向其前驱结点的地址。
链式栈的入栈(n分):
Status Push(LinkStack &s,SElemType e){ p = new LinkStack; //1.生成待插入的结点p p->data = e; //2.设置p的data域的值为e p->next = s->next; //3.p结点指向其前驱结点S,将新结点插入到栈顶 s->next = p; //插入元素完以后,s指针指向新插入的结点p return ok; }
链式栈的出栈(n分): 1.生成p结点指向栈顶元素 2.用e将栈顶元素出栈 3.删除栈顶结点p
Status Pop(LinkStack &S,SElemType &e){ if(s->next == Null); return error //判断栈是否为空 LinkSNode *p; //1.生成p结点,用于后续删除它 p = s->next; //2.p指向栈顶结点 *e = s->data; //3.用元素e保留要删除的结点的值 s->next = p->next; //4.栈顶指针s下移 delete p; //5.删除p结点 }
其实也有两三天没有写博客了,这几天没有想写的太大兴趣了,因为学到这个时候,真的自己到学懂了多少;我也只是想省点力气,挑考试的重点去复习,可…害。