文章目录
- 1.顺序栈
- 1.1初始化
- 1.2判空
- 1.3进栈
- 1.4出栈
- 1.5读取栈顶
- 1.6销毁栈
- ❗1.7顺序栈c++实例
- 2.共享栈
- 2.1初始化
- 2.2判满
1.顺序栈
用顺序存储实现的栈
顺序栈的缺点:栈的大小不可变。
#define MaxSize 10 //定义栈中元素的最大个数 typedef struct{ ElemType data[MaxSize]; //静态数组存放栈中元素 int top; //栈顶指针 } SqStack; //Sq即sequence:顺序的意思
有的顺序栈结构还有栈的大小stackSize:
typedef struct{ ElemType* base; //栈底指针:base指针不动、top往上移 ElemType* top; //栈顶指针 int stackSize; //当前已分配的存储空间大小,即顺序栈的大小 } SqStack; //顺序栈的结构体定义
顺序存储:给各个数据元素分配连续的存储空间,大小为 MaxSize * sizeof(ElemType)。
1.1初始化
InitStack(&S):初始化栈。构造一个空栈S,分配内存空间。
#define MaxSize 10 //定义栈中元素的最大个数 typedef struct { ElemType data[MaxSize]; //静态数组存放栈中元素 int top; //栈顶指针 } SqStack; //初始化 void InitStack(SqStack &S) { S.top = -1; //初始化栈顶指针 } void main() { SqStack S; //声明一个顺序栈(分配空间) InitStack(S); //后续操作... }
初始化有两种方式:
栈顶指针top指向栈顶元素,一般存储的是数组的下标。(一般初始化时top=-1)
初始化时top=-1,那么元素从0开始。top当前指向的位置就是栈顶。
如果有abcde,5个元素,那么满栈top=4。
- 入栈:S.data[++S.top]=x;
- 出栈:x=S.data[S.top-];
- 获得栈顶元素:x=S.data[S.top];
初始化时top=0。top当前指向的位置是栈顶上面的一个没有元素的空位置。
- 入栈:S.data[S.top++]=x;
- 出栈:x=S.data[–S.top];
- 获得栈顶元素:x=S.data[S.top-1];
1.2判空
StackEmpty(S):判断一个栈S是否为空。若S为空,则返回true,否则返回false。
时间复杂度:O(1)
//判断栈空 bool StackEmpty(SqStack S) { if(S.top == -1) //栈空 return true; else //不空 return false; }
1.3进栈
Push(&S,x):插入,进栈。若栈S未满,则将x加入使之成为新栈顶。
时间复杂度:O(1)
//新元素入栈 bool Push(SqStack &S, ElemType x) { if (S.top == MaxSize-1) //栈满,报错 return false; S.top = S.top+1; //指针先加1 S.data[S.top] = x; //新元素入栈 return true; }
上述代码中,指针+1,然后新元素入栈的两段代码可以等价于:
S.data[++S.top] = x;
注意是++S.top先加再用,而不是S.top++先用再加。
1.4出栈
Pop(&S,&x):删除,出栈。若栈S非空,则弹出栈顶元素,并用x返回。
时间复杂度:O(1)
//出栈操作 bool Pop(SqStack &S, ElemType &x) { if(S.top == -1) //栈空,报错 return false; x = S.data[S.top]; //栈顶元素先出栈 S.top = S.top-1; //指针再减1 return true; }
注意:这里top-1,数据其实还残留在内存中,只是逻辑上被删除了。
上述代码中也可以等价于:
x = S.data[S.top--];
注意是S.top--先用再减,而不是--S.top先减再用。
1.5读取栈顶
GetTop(S,&x):读取栈顶元素。若栈S非空,则用x返回线顶元素。
时间复杂度:O(1)
//读栈顶元素 bool GetTop(SqStack S, ElemType &x) { if(S.top == -1) //栈空,报错 return false; x = S.data[S.top]; //×记录栈顶元素 return true; }
读取栈顶元素和出栈操作十分相似,唯一不同是不需要出栈之后top指针-1。
1.6销毁栈
顺序栈是在声明栈时直接分配内存,并没有使用malloc函数,所以不需要手动free,函数运行结束后系统自动回收空间。
但是如果使用了动态分配那么就需要手动释放空间:
//销毁栈、释放栈的内存 void DestroyStack(SqStack& stack){ if(stack.base) { //若栈底指针分配有地址,则释放 delete stack.base; //释放栈底指针的地址 stack.top = -1; //令栈顶位置为0 stack.base = NULL; //将栈底指针指向空 cout ElemType* base; //栈底指针 int top; //栈顶的位置 如 0、1、2、3、4....MaxSize } SqStack; //顺序栈的结构体定义 bool InitStack(SqStack& stack); //初始化栈 bool StackEmpty(SqStack stack);//判断是否为空 bool StackFull(SqStack stack); //判断是否已满 int GetStackSize(SqStack& stack);//获取顺序栈中元素个数 bool Push(SqStack& stack, ElemType value);//入栈 bool Pop(SqStack& stack, ElemType& value);//出栈 bool GetTop(SqStack& stack, ElemType& value);//获取栈顶的元素 void DestroyStack(SqStack& stack);//销毁栈、释放栈的内存 //-------------------------------------------------- void CreatStack(SqStack stack){ int number, value = 0; cout 0){ cin >> value; Push(stack, value); //放入栈 number--; value++; } } int main() { SqStack stack; //创建顺序栈 InitStack(stack); //初始化顺序栈 //例如插入 int value = 5; //插入5个元素 while (value > 0){ Push(stack, value); //放入栈 value--; } //获取栈顶的元素 GetTop(stack, value); cout Pop(stack, value); cout //注意:这里使用new进行空间分配,所以在后面摧毁栈的时候需要delete释放空间 //动态分配一个ElemType类型MaxSize长度的空间,将地址给顺序栈Stack的栈底指针 stack.base = new ElemType[MaxSize]; //判断顺序栈的栈底指针(stack.base)是否为空,若无地址,则分配失败 if(!stack.base){ return false; } stack.top = -1; //初始化栈顶指针的位置为-1 return true; } //判断栈空 bool StackEmpty(SqStack stack){ if (stack.top == -1) return true; else return false; } //判断栈满 bool StackFull(SqStack stack){ if (stack.top == MaxSize-1) //top的位置值等于MaxSize-1时栈满,因为是从0开始的 return true; else return false; } //顺序栈中元素个数 int GetStackSize(SqStack& stack){ return stack.top+1; //栈顶位置即top的数值,就是栈中元素的个数 } /** * @brief 顺序栈入栈: * 开辟一个新的空间,栈顶+1,然后将数据存入stack.base[stack.top]所在的位置. * * @param stack * @param value * @return true * @return false */ bool Push(SqStack& stack, ElemType value){ if (StackFull(stack)){ cout if (StackEmpty(stack)){ cout if (StackEmpty(stack)){ cout if(stack.base) { //若栈底指针分配有地址,则释放 delete stack.base; //释放栈底指针的地址 stack.top = -1; //令栈顶位置为0 stack.base = NULL; //将栈底指针指向空 cout ElemType data [MaxSize];//静态数组存放栈中元素 int top0; //0号栈线顶指针 int top1; //1号栈线顶指针 } ShStack; //初始化栈 void InitStack(ShStack &S) { S.top0 = -1; //初始化栈顶指针 S.top1 = MaxSize; }
还没有评论,来说两句吧...