栈结构解析，最简单解析一遍就会

Mike

上一章节针对于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;  //指向作用  int  size;    //栈的当前中的元素个数}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;}