【脚踢数据结构】深入理解栈-Toy模板网

这篇具有很好参考价值的文章主要介绍了【脚踢数据结构】深入理解栈。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

(꒪ꇴ꒪ )，Hello我是祐言QAQ
我的博客主页：C/C++语言,Linux基础,ARM开发板，软件配置等领域博主🌍
快上🚘，一起学习，让我们成为一个强大的攻城狮！
送给自己和读者的一句鸡汤🤔：集中起来的意志可以击穿顽石!
作者水平很有限，如果发现错误，可在评论区指正，感谢🙏

一、什么是栈？

栈是一种重要的数据结构。它是一种特殊的线性表，特殊在它只允许在表的一端进行插入和删除操作，这一端被称为栈顶，相对的，另一端被称为栈底。在这篇博客中，我们将详细地介绍栈的概念，包括顺序栈和链栈的实现。

【脚踢数据结构】深入理解栈,脚踢数据结构,数据结构,链表,算法

栈是一种线性数据结构，它遵循 "先入后出"（Last-In-First-Out，LIFO）的原则。这意味着最后插入栈的元素将首先被移除，而最早插入的元素将最后被移除。就像如果1先进入了栈底，你想再拿到它，那么就要先把 6 5 4 3 2依次拿出来才能拿到 1。

【脚踢数据结构】深入理解栈,脚踢数据结构,数据结构,链表,算法

二、顺序栈

顺序栈是栈的一种实现方式，它是用一组连续的存储单元存储栈中的元素，并需要一个栈顶指针 *top指出栈顶元素，初始化为-1，栈的大小 size则决定了最多可以放多少数据。

【脚踢数据结构】深入理解栈,脚踢数据结构,数据结构,链表,算法

顺序栈结构体

1.顺序栈的管理结构体

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int Datatype;

//顺序栈结构体
typedef struct Sequent_stack
{
	Datatype *stack;		//存放数据的位置
	int size;				//栈的大小
	int top;				//栈顶偏移
}S_stack;

2.初始化

//初始化顺序栈
S_stack *init_stack(int size)
{
	S_stack *s1= malloc(sizeof(S_stack));
	if (s1 != NULL)
	{
		s1->stack = calloc(size, sizeof(Datatype));
		s1->size = size;
		s1->top = -1;
	}
	return s1;
}

3.判断栈空栈满

//是否栈空
bool isempty(S_stack *s)
{
	return (s->top == -1);
}

//是否栈满
bool isfull(S_stack *s)
{
	return (s->top == s->size-1);
}

4.压栈（入栈）

//压栈
bool push(S_stack *s, Datatype data)
{
	if (isfull(s))
	{
		return false;
	}
	//将栈顶往上偏移一个
	s->top++;
	//将数据，放到栈顶指向的位置
	s->stack[s->top] = data;  //*(s->stack+s->top) = data;
	return true;
}

5.弹栈（出栈）

//弹栈
bool pop(S_stack *s, Datatype *data)
{
	if (isempty(s))
	{
		return false;
	}
	//先拿到栈顶指向的数据
	*data = s->stack[s->top];//data = *(s->stack+s->top);
	//栈顶在往下偏移一个
	s->top--;
	return true;
}

6.遍历顺序栈

//遍历栈
void display(S_stack *s)
{
	for (int i = 0; i <= s->top; ++i)
	{
		printf("%d ", s->stack[i]);
	}
	printf("\n");
}

练习：

输入一个大于零的十进制数，转化为八进制，转化过程中使用顺序栈结构来实现。输入： 123 输出：转化为八进制是 0173。

【脚踢数据结构】深入理解栈,脚踢数据结构,数据结构,链表,算法

完整代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int Datatype;

//顺序栈结构体
typedef struct Secqune_stack
{
	Datatype *stack;		//存放数据的位置
	int size;				//栈的大小
	int top;				//栈顶偏移
}S_stack;

//初始化顺序栈
S_stack *init_stack(int size)
{
	S_stack *s1= malloc(sizeof(S_stack));
	if (s1 != NULL)
	{
		s1->stack = calloc(size, sizeof(Datatype));
		s1->size = size;
		s1->top = -1;
	}
	return s1;
}

//栈空
bool isempty(S_stack *s)
{
	return (s->top == -1);
}

//栈满
bool isfull(S_stack *s)
{
	return (s->top == s->size-1);
}

//压栈(入栈)
bool push(S_stack *s, Datatype data)
{
	if (isfull(s))
	{
		return false;
	}
	//将栈顶往上偏移一个
	s->top++;
	//将数据，放到栈顶指向的位置
	s->stack[s->top] = data;  //*(s->stack+s->top) = data;
	return true;
}

//弹栈(出栈)
bool pop(S_stack *s, Datatype *data)
{
	if (isempty(s))
	{
		return false;
	}
	//先拿到栈顶指向的数据
	*data = s->stack[s->top];//data = *(s->stack+s->top);
	//栈顶在往下偏移一个
	s->top--;
	return true;
}

int main(int argc, char const *argv[])
{
	//初始化顺序栈
	S_stack *s = init_stack(22);
	int num;
	scanf("%d", &num);
	while(num)
	{
		push(s, num%8);
		num/=8;
	}
	printf("十进制数转为八进制数等于：0");
	int data;
	while(!isempty(s))
	{
		pop(s, &data);
		printf("%d", data);
	}
	printf("\n");

	return 0;
}

三、链式栈

链式栈是栈的另一种常见实现方式，它通过链表来表示栈的结构。链式栈相对于顺序栈的一个主要优势是它可以动态地调整大小，适用于栈容量需求不确定或需要频繁的插入和删除操作的情况。与之相对应的是链式栈也需要更多的内存空间用于存储节点指针。

【脚踢数据结构】深入理解栈,脚踢数据结构,数据结构,链表,算法

在具体的指针操作方面与单项链表相似。

1.链式栈的管理结构体


typedef int Datatype;

typedef struct Node
{
	Datatype data;			//数据
	struct Node *prev;		//指向上一个节点
}node;

//链式栈的节点
typedef struct List_stack
{
	node *stack;		//每一个节点的数据
	int size;			//长度
}Lstack;

2.初始化

//初始化链式栈
Lstack *init_list_stack()
{
	Lstack *s = malloc(sizeof(Lstack));
	if (s!=NULL)
	{
		s->stack = NULL;
		s->size = 0;
	}
	return s;
}

3.判断栈空

由于链式栈独特的结构使之不会出现栈满的情况，而是根据需要随时动态调整栈容量，因此我们无需判断链式栈是否栈满。

//链式栈的栈空判断
bool isempty(Lstack *s)
{
	return (s->size == 0);
}

4.压栈

//压栈（入栈）
bool push(Lstack *s, Datatype data)
{
	node *new = malloc(sizeof(node));
	if (new != NULL)
	{
		//如果new不为空
		new->data = data;
		//新节点的prev指向栈原来的尾部
		new->prev = s->stack;
		//新节点现在是不是就变为现在链式栈的尾部
		s->stack = new;
		//栈的大小+1
		s->size++;
		return true;
	}
	else
	{
		return false;
	}
}

5.弹栈

//弹栈（出栈）
bool pop(Lstack *s, Datatype *data)
{
	//栈空
	if (isempty(s))
	{
		return false;
	}
	//先将栈的尾部（栈顶）的节点的地址拿到
	*data = s->stack->data;
	//将尾部（栈顶）的节点往前挪一个
	s->stack = s->stack->prev;
	//链式栈的节点个数-1
	s->size--;
	return true;
}

练习：

输入一个大于零的十进制数，转化为十六进制，转化过程中使用链式栈结构来实现。输入： 123 输出：转化为八进制是 0x7B。

【脚踢数据结构】深入理解栈,脚踢数据结构,数据结构,链表,算法

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int Datatype;

typedef struct Node
{
	Datatype data;			//数据
	struct Node *prev;		//指向上一个节点
}node;

//链式栈的节点
typedef struct List_stack
{
	node *stack;		//每一个节点的数据
	int size;			//长度
}Lstack;

//初始化链式栈
Lstack *init_list_stack()
{
	Lstack *s = malloc(sizeof(Lstack));
	if (s!=NULL)
	{
		s->stack = NULL;
		s->size = 0;
	}
	return s;
}

//链式栈的栈空判断
bool isempty(Lstack *s)
{
	return (s->size == 0);
}

//压栈（入栈）
bool push(Lstack *s, Datatype data)
{
	node *new = malloc(sizeof(node));
	if (new != NULL)
	{
		//如果new不为空
		new->data = data;
		//新节点的prev指向栈原来的尾部
		new->prev = s->stack;
		//新节点现在是不是就变为现在链式栈的尾部
		s->stack = new;
		//栈的大小+1
		s->size++;
		return true;
	}
	else
	{
		return false;
	}
}

//弹栈（出栈）
bool pop(Lstack *s, Datatype *data)
{
	//栈空
	if (isempty(s))
	{
		return false;
	}
	//先将栈的尾部（栈顶）的节点的地址拿到
	*data = s->stack->data;
	//将尾部（栈顶）的节点往前挪一个
	s->stack = s->stack->prev;
	//链式栈的节点个数-1
	s->size--;
	return true;
}

int main(int argc, char const *argv[]) {
    Lstack *s = init_list_stack();
    int num;
    Datatype data;
    char hexDigits[] = "0123456789ABCDEF";  // 十六进制字符表示
    printf("请输入一个十进制数：");
    scanf("%d", &num);

    while (num > 0) {
        int num1 = num % 16;
        push(s, num1);
        num /= 16;
    }

    printf("转化为十六进制是：0x");
    while (!isempty(s)) {
        pop(s, &data);
        printf("%c", hexDigits[data]);
    }
    printf("\n");

    // 释放内存
    while (pop(s, &data)) {
        free(s->stack);
        s->stack = s->stack->prev;
    }
    free(s);

    return 0;
}