顺序栈的概念以及实现

- 日理万妓 2022-05-28 08:06 69阅读 0赞

栈的概念：

1、栈：一种只允许在一端进行插入或删除的**线性表**

2、栈顶：线性表允许进行插入删除的那一端

3、栈底：固定的，不允许进行插入和删除的那一端

4、空栈：不含任何元素的空表

顺序栈：

栈的顺序存储成为顺序栈，他是利用一组地址连续的储存单元存放自栈底到栈顶的数据元素，同时附设一个指针(Top)指示当前栈的位置。

栈顶指针：S.top，初始值设定为S.top = -1; 栈顶元素：S.data\[S.top\]。

进栈操作：栈不满的时候，栈顶指针先加1，再送值到栈顶元素

出栈操作：栈非空的时候，先取值栈顶元素，再将栈顶指针减1

栈空操作：S.top = -1; 栈满条件：S.top == MaxSize-1; 栈长：S.top + 1;

由于顺序栈的入栈操作收到数组上界的约束，对栈的最大使用空间估计不足时候，有可能发生栈的上溢。

顺序栈的实现：

#include<iostream>
    using namespace std;
    typedef int Elemtype;
    #define MaxSize 50
    typedef struct {
    	Elemtype data[MaxSize];
    	int top;
    }SqStack;
    //初始化一个空栈
    void InitStack(SqStack &S) {
    	S.top = -1;
    }
    //判断栈是否为空，若栈为空则返回true，否则返回false
    bool StackEmpty(SqStack S) {
    	return S.top == -1;
    }
    //进栈，若栈S未满，将x加入使之成为栈顶
    bool Push(SqStack &S, Elemtype x) {
    	if (S.top == MaxSize - 1) {
    		return false;
    	}
    	S.data[++S.top] = x;
    	return true;
    }
    //出栈，若栈S非空，弹出栈顶元素，用x返回栈顶元素
    bool Pop(SqStack &S, Elemtype &x) {
    	if (StackEmpty(S)) {
    		return false;
    	}
    	x = S.data[S.top--];
    	return true;
    }
    //读栈顶元素，若栈S非空，用x返回栈顶元素
    bool GetTop(SqStack &S, Elemtype &x) {
    	if (StackEmpty(S)) {
    		return false;
    	}
    	x = S.data[S.top];
    	return true;
    }
    //销毁栈，并释放栈S占用的储存空间
    void ClearStack(SqStack &S) {
    	S.top = -1;
    	free(S.data);
    }
    int main() {
    
    }