栈的链式存储结构(带头结点的单链表实现)

最新推荐文章于 2025-03-25 17:22:58 发布

别团等shy哥发育

最新推荐文章于 2025-03-25 17:22:58 发布

阅读量3.2k

点赞数 5

分类专栏：数据结构与算法文章标签：指针链表数据结构算法 c语言

本文链接：https://blog.csdn.net/qq_43753724/article/details/106561319

版权

数据结构与算法专栏收录该内容

59 篇文章

订阅专栏

本文介绍了一种使用链式存储结构实现栈的方法，避免了传统数组实现中可能出现的栈上溢问题。通过定义链表结构和栈操作函数，如初始化、入栈、出栈和获取栈顶元素，实现了动态调整大小的栈。最后，通过一个简单的C语言程序演示了链栈的创建、元素的压入和弹出过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

一、栈的链式存储结构(Visual studio开发环境)

     要避免栈上溢，最好的办法就是使用链式存储结构，让多个栈共享所有可用的存储空间。所以，栈也可以采用链式存储结构表示，这种结构的栈简称为链栈。
      新入栈的元素即为链表新的第一个结点，只要系统还有存储空间，就不会有栈满的情况发生。一个链栈可由一个栈顶指针top唯一确定。
     采用带头结点的单链表实现栈。因为栈的插入和删除操作只在表头进行，所以链表的表头指针top就作为栈顶指针，top始终指向当前栈顶元素前面的头节点，即top->next为栈顶元素，当top->next==NULL,则代表栈空。
在这里插入图片描述
二、代码实现
stack.h

#pragma once
#include<windows.h>
typedef struct Stacknode {
	Elemtype data;
	struct Stacknode *next;
}Stacktype;
//初始化
void InitStack(Stacktype **top) {
	*top = (Stacktype *)malloc(sizeof(Stacktype));
	(*top)->next = NULL;
}
//入栈操作
int pushStack(Stacktype *top, Elemtype x) {
	Stacktype *p;
	p = (Stacktype*)malloc(sizeof(Stacktype));//申请结点
	p->data = x;
	p->next = top->next;
	top->next = p;
	return true;
}
//出栈操作
Elemtype popStack(Stacktype *top) {
	Stacktype *p;
	Elemtype x;
	if (top->next == NULL) {
		printf("空栈!!");
		return NULL;
	}
	else {
		p = top->next;
		top->next = p->next;
		x = p->data;
		free(p);
		return x;
	}
}
//取栈顶数据元素
Elemtype GetTop(Stacktype *top) {
	if (top->next == NULL) {
		return NULL;
	}
	else {
		return (top->next->data);
	}
}

源文件:

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef int Elemtype;
#include"stack.h"
int main() {
	Stacktype *stack1;
	int x;
	InitStack(&stack1);
	printf("入栈的顺序为:");
	for (int i = 0; i < 10; i++) {
		printf("%d ", i + 1);
		pushStack(stack1, i + 1);
	}
	printf("\n出栈的顺序为:");
	while (stack1->next != NULL) {
		x = popStack(stack1);
		printf("%d ", x);
	}
	system("pause");
	return 0;
}