[数据结构与算法] 【2023王道数据结构】链栈-不带头结点

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【2023王道数据结构】链栈-不带头结点 -> 正文阅读

[数据结构与算法]【2023王道数据结构】链栈-不带头结点

思路：s指向第一个进栈的元素，其余的按头插法插入
另一个刚刚想到假设栈顶指针为top 初始化为null 插入节点x的操作应该是
x-next=top
top =x

#include <iostream>
#include <stdlib.h>

using namespace std;

typedef struct LinkNode {
	int data;
	struct LinkNode *next;
}*LinkStack;

void init(LinkStack &s);
void push(LinkStack &s, int x);
void pop(LinkStack &s, int &e);
int getTop(LinkStack s);
void Destory(LinkStack &s);

int main(void) {
	LinkStack s;
	init(s);
	
	push(s,1);
	push(s,2);
	push(s,3);
	
	//int e;
	//pop(s,e);
	//cout << "main:" << e << endl;
	//pop(s,e);
	//cout << "main:" << e << endl;
	//pop(s,e);
	//cout << "main:" << e << endl;
	cout << "main:" << getTop(s) << endl; 
	
	Destory(s);
	getTop(s);
}

void init(LinkStack &s) {
	s = NULL; //不带头结点 
}
//s指向最先进来的元素 
void push(LinkStack &s, int x) {
	LinkNode *t = (LinkNode*)malloc(sizeof(LinkNode));
	t->data = x;
	//如果此时栈是空栈，令s指向t 
	if (s == NULL) {
		t->next = NULL;
		s = t; 
	} 
	else {
	 	t->next = s->next;
		s->next = t; 
	}
} 
void pop(LinkStack &s, int &e) {
	if (s == NULL) {
		printf("栈空\n");
		return;
	}
	//如果此时表中只剩s，输出s 
	if (s->next == NULL) {
		e = s->data;
		s = NULL; //空栈 
		return;
	}
	
	LinkNode *t = s->next;
	e = t->data;
	
	s->next = t->next;
	free(t);
} 

int getTop(LinkStack s) {
	if (s == NULL) {
		printf("栈空！\n");
		exit(0);
	}
	if (s->next == NULL) return s->data;
	return s->next->data;
}
void Destory(LinkStack &s) {
	if (s == NULL) {
		printf("栈已经空了!\n");
		exit(0);
	}
	LinkNode *t;
	while(s->next != NULL) {
		t = s->next;
		
		s->next = t->next;
		free(t);
	}
	t = s;
	free(t);
	s = NULL;
}