《数据结构》—— 顺序栈、链栈、共享栈的基础知识

爱被打了一巴掌 2022-09-11 04:28 234阅读 0赞

### 栈 ###

*   *  一、栈的基本概念
     *  二、栈的基本操作
     *  三、栈的顺序存储结构
     *   *  3.1 顺序栈的基本操作
     *  四、共享栈
     *  五、栈的链式存储结构
     *   *  5.1 链栈
         *  5.2 链栈的基本操作

## 一、栈的基本概念 ##

线性表是具有相同数据类型的n(n≥0) 个数据元素的有限序列，其中n为表长，当n = 0时线性表是一个空表。若用L命名线性表，则其一般表示为 : L = (a1, a2, … , ai, ai+1, … , an)

*  **栈(Stack) 是只允许在一端进行插入或删除操作的线性表。** 首先栈是一种线性表， 但限定这种线性表只能在某一端进行插入和刪除操作；
 *  **栈顶(Top)：** 线性表允许进行插入删除的那一端；
 *  **栈底(Bottom)：** 固定的、不允许进行插入和删除的另一端；
 *  **空栈：** 不含任何元素的空表。
 *  **卡特兰数：** n个不同元素进栈，出栈元素不同排列的个数为1/(n+ 1)Cn-2n。

--------------------

## 二、栈的基本操作 ##

*  **InitStack(&S)：** 初始化栈。构造一个空栈S，分配内存空间。
 *  **DestroyStack(&S)：** 销毁栈。销毁并释放栈S所占用的内存空间。
 *  **Push(&S,x)：** 进栈，若栈s未满，则将x加入使之成为新栈顶。
 *  **Pop(&S,&x)：** 出栈，若栈S非空，则弹出栈顶元素，并用x返回。
 *  **GetTop(S, &x) ：** 读栈项元素。若栈S非空，则用x返回栈顶元素。
 *  **StackEmpty(S)：** 判断一个栈S是否为空。若S为空，则返回true，否则返回false。

--------------------

## 三、栈的顺序存储结构 ##

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

#define Maxsize 10 // 定义栈里元素的最大容量
    typedef struct{
        
    	ElemType data[Maxsize]; // 存放栈中数据
    	int top;	// 栈顶指针
    }SqStack;
    
    // 栈的初始化
    void InitStack(SqStack &S){
        
    	S.top == -1;  // 初始化栈顶指针
    }
    
    // 调用方法
    void testStack(){
        
    	SqStack S; // 声明顺序栈
    	InitStack(S);
    }

--------------------

### 3.1 顺序栈的基本操作 ###

**判断栈空** ：栈空条件:S.top==-1。

bool StackEmpty(SqStack S){
        
        if (S.top==-1)   //栈空
            return true;
        else    //不空
            return false;
    }

**进栈**：栈不满时栈顶指针先加1，再送值到栈顶元素；满条件:S.top==Maxsize-1; 栈长:S.top+1。

bool Push(SqStack &S, ElemType x){
        
        if(S.top==Maxsize-1) // 栈满报错
            return false;
        S.data[++S.top]== x; // 指针+1，再入栈
        return true;
    }

**出栈**：栈非空时，先取栈顶元素值再将栈顶指针减1。

bool Pop(SqStack &S, ElemType &x){
        
        if(S.top==-1)   // 栈空，报错
            return false;
        x = S.data[S.top--]; //先出栈，指针-1
        return true;
    }

**读栈顶元素**：栈顶指针:S.top，初始时设置S.top=-1；栈顶元素:S.data\[S.top\]。

bool GetTop(SqStack S, ElemType &x){
        
        if(S.top==-1)   // 栈空，报错
            return false;
        x = S.data[S.top]; // x记录栈顶元素
        return true;
    }

--------------------

## 四、共享栈 ##

让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。![在这里插入图片描述][35474fe1eea34f17acf8db1835f9a1cd.png]

*  两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize时1号栈为空。
 *  当两个栈顶指针相邻(topl-top0=1)时，判断为栈满。
 *  当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减1再赋值，出栈时则刚好相反。
 *  存取数据的时间复杂度均为O(1)。

#define MaxSize 10 //定义栈中元素的最大个数
    typedef struct{
        
        ElemType data[MaxSize]; //静态数组存放栈中元素
        int top0;   // 0号栈栈顶指针
        int top1;   // 1号栈栈顶指针
    }ShStack;
    
    // 初始化栈
    void InitStack(ShStack &S){
        
        S.top0=-1;  // 初始化栈顶指针
        S.top1=MaxSize; 
    }
    
    // 栈满的条件: top0+1==top1
    bool ShtackEmpty(ShStack S){
        
        if (S.top0+1==S.top1)   //栈满
            return true;
        else    // 不满
            return false;
    }

--------------------

## 五、栈的链式存储结构 ##

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。

通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。

我们容易发现栈的入栈与出栈操作代表着单链表在表头进行插入与删除操作。

### 5.1 链栈 ###

*  采用单链表实现，并规定所有操作都是在单链表的表头进行；

**优点：**

1.  便于多个栈共享存储空间和提高其效率；
2.  且不存在栈满上溢的情况。

### 5.2 链栈的基本操作 ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_17_color_FFFFFF_t_70_g_se_x_16]

**代码如下：** 要事先创建一个SqStack.txt文件。

/***链栈的实现***/
    #include<iostream>
    #include<fstream>
    using namespace std;
    
    #define true 1
    #define ERROR 0
    #define OVERFLOW -2
    typedef int Status;
    typedef char ElemType;
    
    typedef struct Linknode {
        
    	ElemType data;
    	struct Linknode *next;
    } Linknode, *LinkStack;
    
    //算法3.5　链栈的初始化
    Status InitStack(LinkStack &S) {
         // 构造一个空栈 S，栈顶指针置空
    	S = NULL;
    	return true;
    }
    
    //算法3.6　链栈的入栈
    Status Push(LinkStack &S, ElemType e) {
        //在栈顶插入元素e
    	LinkStack p;
    	p = new Linknode; //生成新结点
    	p->data = e; //将新结点数据域置为e
    	p->next = S; //将新结点插入栈顶
    	S = p; //修改栈顶指针为p
    	return true;
    }
    
    //算法3.7　链栈的出栈
    Status Pop(LinkStack &S, ElemType &e) {
        //删除S的栈顶元素，用e返回其值
    	LinkStack p;
    	if (S == NULL)
    		return ERROR; //栈空
    	e = S->data; //将栈顶元素赋给e
    	p = S; //用p临时保存栈顶元素空间，以备释放
    	S = S->next; //修改栈顶指针
    	delete p; //释放原栈顶元素的空间
    	return true;
    }
    //算法3.8　取链栈的栈顶元素
    ElemType GetTop(LinkStack S) {
        //返回S的栈顶元素，不修改栈顶指针
    	if (S != NULL) //栈非空
    		return S->data; //返回栈顶元素的值，栈顶指针不变
    }
    
    // 函数算法调用实现
    int main() {
        
    	LinkStack s;
    	int choose, flag = 0;
    	ElemType j, 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://算法3.5　链栈的初始化
    			if (InitStack(s)) {
        
    				flag = 1;
    				cout << "成功对栈进行初始化\n\n";
    			} else
    				cout << "初始化栈失败\n\n";
    			break;
    		case 2: {
        //算法3.6　链栈的入栈
    			fstream file;
    			file.open("C:\\Users\\Desktop\\SqStack.txt");
    			if (!file) {
        
    				cout << "错误！未找到文件！\n\n" << endl;
    				return false;
    			}
    			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://算法3.8　取链栈的栈顶元素
    			if (flag != -1 && flag != 0)
    				cout << "栈顶元素为：\n" << GetTop(s) << endl << endl;
    			else
    				cout << "栈中无元素，请重新选择\n" << endl;
    			break;
    		case 4://算法3.7　链栈的出栈
    			if (flag) {
        
    				cout << "依次弹出的栈顶元素为:\n";
    				while (Pop(s, t))
    					cout << t << "  ";
    				cout << endl << endl;
    			} else
    				cout << "栈未建立，请重新选择\n\n";
    			break;
    		}
    	}
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16]

[35474fe1eea34f17acf8db1835f9a1cd.png]: /images/20220828/1be1e53fdf074f00b9d751a58574a8b6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/58144dcbc03243a38a80240a749e6d3f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/23b4df28b27b4aef875e4fd43610e7b6.png