栈的链式存储（单链表实现）

布满荆棘的人生 2022-12-04 07:51 170阅读 0赞

## 栈的链式存储（带有头结点） ##

与单链表的创建以及基本操作相似，大家自行脑补 哈哈 （最重要的是理清楚指针的变动以及变动的原因）

## 存储结构 ##

typedef struct stackNode{
        
    	int data;   //数据域 
    	struct stackNode *next;  //指向下一个结点的指针域 
    }*linkStack;

## 基本操作 ##

初始化

bool initstack(linkStack &S){
        
    	S = NULL;
    	return true;
    }

入栈

//入栈
    bool push(linkStack &S,int e){
        
        linkStack p = new stackNode;
        p->data = e;  //修改新建结点的数据域 
        p->next = S;  //将新建的节点的指针域指向前一个入栈的结点，以便出栈 
        S = p;        //修改栈顶指针 
        return true;
    }

出栈

//出栈
    bool pop(linkStack &S) {
        
    	if(S == NULL)    //判空 
    	return false; 
    	linkStack temp;   //建立临时结点，便于后续的释放 
    	temp = S;         //将临时结点指向栈顶元素 
    	S = S->next;      //修改栈顶指针 
    	delete temp;      //释放临时指针指向的空间 
    }

取栈顶元素

//取栈顶元素
    int getTop(linkStack &S){
        
    	if(S == NULL)
    	return false;
    	int temp = S->data;    //建立临时元素存储数据 ，也可直接返回元素 
    	return temp;           //返回元素 
    }

总结测试

#include <iostream>
    using namespace std;
    typedef struct stackNode{
        
    	int data;   //数据域 
    	struct stackNode *next;  //指向下一个结点的指针域 
    }*linkStack;
    //初始化
    bool initstack(linkStack &S){
        
    	S = NULL;
    	return true;
    }
    //入栈
    bool push(linkStack &S,int e){
        
        linkStack p = new stackNode;
        p->data = e;  //修改新建结点的数据域 
        p->next = S;  //将新建的节点的指针域指向前一个入栈的结点，以便出栈 
        S = p;        //修改栈顶指针 
        return true;
    }
    //出栈
    bool pop(linkStack &S) {
        
    	if(S == NULL)    //判空 
    	return false; 
    	linkStack temp;   //建立临时结点，便于后续的释放 
    	temp = S;         //将临时结点指向栈顶元素 
    	S = S->next;      //修改栈顶指针 
    	delete temp;      //释放临时指针指向的空间 
    }
    //取栈顶元素
    int getTop(linkStack &S){
        
    	if(S == NULL)
    	return false;
    	int temp = S->data;    //建立临时元素存储数据 ，也可直接返回元素 
    	return temp;           //返回元素 
    }
    int main()
    {
        
    	linkStack L;
    	initstack(L);
    	push(L,1);
    	push(L,2);
    	push(L,3);
    	int temp = getTop(L);
    	cout<<temp<<endl;
    	pop(L);
    	temp = getTop(L);
    	cout<<temp<<endl;
    	pop(L);
    	pop(L);
    	return 0;
    }