顺序栈的表示和实现，新人请进

落日映苍穹つ 2023-01-20 04:57 4阅读 0赞

顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈做中的位置。通常习惯的做法是top=0表示空栈，鉴于C语言中数组的下标约定从0开始，则当以C语音作描述语言时，如此设是会部来很大不便，因此另设指针base指示栈底元素在顺序栈中的位置。当top和base 的值相等时，表示空栈。顺序栈的定义如下：  
**顺序栈的存储结构**

#define MAXSIZE  100//顺序栈存储空间的初始分配量
    typedef struct {
        
    	SElemType *base;//栈底指针
    	SElemType *top;//栈顶指针
    	int stacksize;//栈可用的最大容量
    } SqStack;

（1）base表示栈底指针，初始化完成之后，栈底指针base始终指向栈底的位置，若base的值为NULL，则表明栈结构不存在。top为栈顶指针，其初值指向栈底。每当插入新的元素时，栈top+1，每当删除栈顶元素，指针top-1。因此，栈空时top=base，都指向栈底，栈非空时，top始终指向栈顶元素的上一个位置  
（2）stacksize指示栈使用的最大容量，栈的初始化操作为顺序栈动态分配MAXSIZE大小的数组空间，将stacksize置为MAXSIZE.

头文件解释
    
    include<iostream>
    
    包含c++的标准输入输出头文件iostream
    也就是编译器先把头文件iostream中的所有内容COPY到
    #include的位置，再进行编译
    注意c++的这个标准输入输出头文件的名称就是iostream，没有.h的后缀
    跟c的标准输入输出头文件stdio.h不一样。

include<fstream>
    
    #include 是C++的预编译语句，作用是包含对应的文件，在这里是包含C++的STL头文件fstream。
    在包含了这个文件后，就可以使用fstream中定义的类及各种成员函数了。
    fstream是C++ STL中对文件操作的合集，包含了常用的所有文件操作。在C++中，所有的文件操作，都是以流(stream)的方式进行的，fstream也就是文件流file stream。

using namespace std指调用命名空间std内定义的所有标识符。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODQ4MzYx_size_16_color_FFFFFF_t_70]  
栈中元素和栈指针之间的关系  
由于顺序栈的插入和删除只在栈顶进行，因此顺序栈的基本操作比顺序表要简单的多

## 初始化 ##

Status InitStack(SqStack &S) {
        
    	//构造一个空栈S
    	S.base = new SElemType[MAXSIZE];//为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
    	if (!S.base)
    		exit(OVERFLOW); //存储分配失败
    	S.top = S.base; //top初始为base，空栈
    	S.stacksize = MAXSIZE; //stacksize置为栈的最大容量MAXSIZE
    	return OK;
    }

## 顺序表的入栈 ##

Status Push(SqStack &S, SElemType e) {
        
    	// 插入元素e为新的栈顶元素
    	if (S.top - S.base == S.stacksize)
    		return ERROR; //栈满
    	*(S.top++) = e; //元素e压入栈顶，栈顶指针加1
    	return OK;
    }

## 顺序表的出栈 ##

Status Pop(SqStack &S, SElemType &e) {
        
    	//删除S的栈顶元素，用e返回其值	
    	if (S.base == S.top)
    		return ERROR;//栈空
    	e = *(--S.top); //栈顶指针减1，将栈顶元素赋给e
    	return OK;
    }

## 取栈顶元素 ##

char GetTop(SqStack S) {
        //返回S的栈顶元素，不修改栈顶指针
    	if (S.top != S.base) //栈非空
    		return *(S.top - 1); //返回栈顶元素的值，栈顶指针不变
    }

完整代码，运行前要加入txt文本，里面装有栈中元素可以是ABCD，以回车键隔开

/***顺序栈的实现***/
    
    #include<iostream>
    #include<fstream>
    using namespace std;
    
    //顺序栈定义
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    #define MAXSIZE  100//顺序栈存储空间的初始分配量
    typedef int Status;
    typedef char SElemType;
    
    typedef struct {
        
    	SElemType *base;//栈底指针
    	SElemType *top;//栈顶指针
    	int stacksize;//栈可用的最大容量
    } SqStack;
    
    //顺序栈的初始化
    Status InitStack(SqStack &S) {
        
    	//构造一个空栈S
    	S.base = new SElemType[MAXSIZE];//为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
    	if (!S.base)
    		exit(OVERFLOW); //存储分配失败
    	S.top = S.base; //top初始为base，空栈
    	S.stacksize = MAXSIZE; //stacksize置为栈的最大容量MAXSIZE
    	return OK;
    }
    //顺序栈的入栈
    Status Push(SqStack &S, SElemType e) {
        
    	// 插入元素e为新的栈顶元素
    	if (S.top - S.base == S.stacksize)
    		return ERROR; //栈满
    	*(S.top++) = e; //元素e压入栈顶，栈顶指针加1
    	return OK;
    }
    //顺序栈的出栈
    Status Pop(SqStack &S, SElemType &e) {
        
    	//删除S的栈顶元素，用e返回其值	
    	if (S.base == S.top)
    		return ERROR;//栈空
    	e = *(--S.top); //栈顶指针减1，将栈顶元素赋给e
    	return OK;
    }
    //取顺序栈的栈顶元素
    char GetTop(SqStack S) {
        //返回S的栈顶元素，不修改栈顶指针
    	if (S.top != S.base) //栈非空
    		return *(S.top - 1); //返回栈顶元素的值，栈顶指针不变
    }
    
    int main() {
        
    	SqStack s;
    	int choose, flag = 0;
    	SElemType j, e, t;
    	cout << "1.初始化\n";
    	cout << "2.入栈\n";
    	cout << "3.读栈顶元素\n";
    	cout << "4.出栈\n";
    	cout << "0.退出\n\n";
    
    	choose = -1;
    	while (choose != 0) {
        
    		cout << "请选择:";
    		cin >> choose;
    		switch (choose) {
        
    		case 1://顺序栈的初始化
    			if (InitStack(s)) {
        
    				flag = 1;
    				cout << "成功对栈进行初始化\n\n";
    			} else
    				cout << "初始化栈失败\n\n";
    			break;
    		case 2: {
        //算法3.2　顺序栈的入栈
    			fstream file;
    			file.open("SqStack.txt");//
    			if (!file) {
        
    				cout << "错误！未找到文件！\n\n" << endl;
    				exit(ERROR);
    			}
    			if (flag) {
        
    				flag = 1;
    				cout << "进栈元素依次为：\n";
    				while (!file.eof()) {
        
    					file >> j;
    					if (file.fail())
    						break;
    					else {
        
    						Push(s, j);
    						cout << j << "  ";
    					}
    				}
    				cout << endl << endl;
    			} else
    				cout << "栈未建立，请重新选择\n\n";
    			file.close();
    		}
    			break;
    		case 3://顺序栈的出栈
    			if(flag != -1 && flag != 0)
    				cout << "栈顶元素为：\n" << GetTop(s) << endl << endl;
    			else
    				cout << "栈中无元素，请重新选择\n" << endl;
    			break;
    		case 4://取顺序栈的栈顶元素
    			cout << "依次弹出的栈顶元素为:\n";
    			while (Pop(s, t)){
        
    				flag = -1;
    				cout << t << "  ";
    			}
    			cout << endl << endl;
    			break;
    		}
    	}
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODQ4MzYx_size_16_color_FFFFFF_t_70]: /images/20221021/fe02934ffd3a4379bd1a21699a96b4f3.png