栈结构解析,最简单解析一遍就会
上一章节针对于C语言最基本的数据结构链式结构体做了解析,不清楚的可以回顾一下。本章节主要针对于C语言的基础数据结构栈做以解析。数据结构之栈栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
故栈基本操作如下:
[*]创建栈
[*]入栈
[*]出栈
[*]判断栈是否为NULL
[*]返回栈顶元素
数据结构之栈分类根据实现栈的方式,我们可以把栈分为以下三种描述方式:
[*]原生数组描述
[*]动态申请内存的数组描述
[*]链式结构描述
原生数组描述栈数组描述栈,只不过多了后进先出的限制而已,它是静态分配的,即使用前,它的内存就已经以数组的形式分配好了,所以在使用时,需要注意栈顶标记的大小。
举个例子,把十进制的数字5转二进制的数字,过程大概是这样:
原生数组描述栈实现进制转换代码
动态数组实现栈动态申请内存的数组描述 不在 采用上述实用性的方法了,而是通过封装相关栈函数去描述这种结构。这是写数据结构的一种大致方法。
1.结构体定义与栈的创建过程:
[*]结构体定义:描述栈的属性栈:栈容量,栈顶标记
[*]创建栈其实就是创建结构体变量
具体代码
ps:栈顶标记初始值一般都是-1 ,为了满足栈顶标记和数组下标一致
2.入栈操作
注意: 我们的实现是将最新的元素放在了数组的末尾, 那么数组末尾的元素就是我们的栈顶元素,故可以使用栈顶标记去计算栈中的元素个数。然后每次入栈后,栈顶标记往后移动。
具体实现代码:
3.出栈操作和获取栈顶元素
注意: 出栈操作应该是将栈顶的元素删除,由于数组实现的栈无法删除,故只能 吧 栈顶标记往前移动,简称为一种"伪删除"。
具体实现代码:
4.判断栈是否为空
用户判断栈中是否有元素,通过栈顶标记去做即可
具体实现代码:
动态申请内存的数组描述栈实现进制转换代码
链式栈链式栈:链表的头插法即可
这个不做详细分析了,如果有不懂的可以转接视频教程
链式栈源码 #include <stdio.h>#include <stdlib.h>#include <limits.h> //float.h/*链式栈: 入栈:链表的表头法插入 出栈: 链表的表头删除*/typedef struct Node{int data;struct Node* next;}NODE,*LPNODE;//创建节点LPNODE createNode(int data){LPNODE newNode = (LPNODE)malloc(sizeof(NODE));newNode->data = data;newNode->next = NULL;return newNode;}typedef struct {LPNODE stackTop; //指向作用intsize; //栈的当前中的元素个数}STACK,*LPSTACK;LPSTACK createStack(){LPSTACK stack = (LPSTACK)malloc(sizeof(STACK));stack->size = 0;stack->stackTop = NULL;return stack;}void push(LPSTACK stack, int data){//入栈:无表头的链表的表头插入struct Node* newNode = createNode(data);newNode->next = stack->stackTop;stack->stackTop = newNode;stack->size++;}int top(LPSTACK stack){if (stack->size != 0) return stack->stackTop->data;return INT_MAX; //心里清楚 这个返回值代表的是没有元素}void pop(LPSTACK stack){//无表头链表的表头法删除if (stack->size != 0){ struct Node* nextNode = stack->stackTop->next; free(stack->stackTop); stack->stackTop = nextNode; stack->size--;}}int empty(LPSTACK stack){return stack->size == 0;}int size(LPSTACK stack){return stack->size;}int main(){LPSTACK stack = createStack();for (int i = 1; i <= 3; i++){ push(stack, i);}while (!empty(stack)){ printf("%d\t", top(stack)); pop(stack);}printf("\n");LPSTACK array = createStack();int num = 123;printf("123的二进制是:");while (num){ push(array, num % 2); num /= 2;}while (!empty(array)){ printf("\t%d", top(array)); pop(array);}system("pause");return 0;}
文档来源:51CTO技术博客https://blog.51cto.com/u_15297386/3289791
页:
[1]