《数据结构》第3章 栈（C语言描述）

本文主要是介绍《数据结构》第3章 栈（C语言描述），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

栈是限制在一段进行插入操作和删除操作的线性表（俗称堆栈），允许进行操作的一端称为“栈顶”，另一固定端称为“栈底”，当栈中没有元素称为“空栈”。特点：先进后出（FILO）。

图1

栈顶即top，这里top有两种定义方式：

• 满栈（Full Stack）,top指向最后一个使用的空间；
• 空栈（Empty Stack），top指向下一个可用的空间；

栈也是线性表，所以也分顺序存储和链式存储。

3.1顺序存储

栈是顺序表的一种，具有顺序表同样的存储结构，由数组定义，配合用数组下表表示的栈顶指针top(相对指针)完成各种操作。
typedef int data_t; //定义栈中数据元素的数据类型

typedef struct  
{  date_t *data;  //用指针指向栈的存储空间  int maxlen;    //当前栈的最大元素个数  int top;  //指向栈顶位置（数组下标）的变量  
}seqstack_t;  //顺序栈类型定义  

图2

如图，我们可以看到，栈的顺序存储与顺序表的区别，顺序表数组大小是固定的，这样限制了我们的后期修改，而栈的顺序存储将数据域单独开辟了一片空间才存放，大小为maxlen*sizeof(data_t), 下面是栈的基本运算：
1、创建栈

seqstack_t *CreateEmptyStack(int max_len)  
{  seqstack_t *stack;  stack = (seqstack_t *)malloc(sizeof(seqstack_t));  stack->data = (data_t *)malloc(sizeof(data_t)*max_len);  stack->top = -1;  stack->max_len = max_len;  return stack;  
}  

2、摧毁一个栈

void DestroyStack(seqstack_t *stack)  
{  if(stack != NULL)  {  if(stack->data != NULL)  free(stack->data);  free(stack);  }  
}  

3、清空一个栈

void ClearStack(seqstack_t *stack)  
{  if(stack != NULL)  stack->top = -1;  
}  

4、判断栈是否为空

int EmptyStack(seqstack_t *stack)  
{  if(stack == NULL)  return -1;  return(stack->top == -1 ? 1 : 0);  
} 

5、判断栈是否为满

int FullStack(seqstack_t *stack)  
{  if(stack == NULL)  return -1;  return(stack->top == (stack->max_len - 1) ? 1 : 0);  
}

6、进栈

int PushStack(seqstack_t *stack ,data_t x)  
{  if(FullStack(stack))  return -1;  else  {  stack->top++;  stack->data[stack->top] = x;  }  return 0;  
}  

7、出栈

int PopStack(seqstack_t *stack,data_t *x)  
{  if(EmptySqstack(stack))  return -1;  else  {  *x = stack->data[stack->top];  stack->top--;  }  return 0;  
}  

8、取栈顶元素

int GetTop(seqstack_t *stack,data_t *x)  
{  if(EmptyStack(stack))  return -1;  else  *x = stack->data[stack->top];  return 0;  
}  

3.2链式存储

若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作"链栈"。链栈通常用一个无头结点的单链表表示。如图所示：
插入操作和删除操作均在链表头部进行，链表尾部就是栈底，栈顶指针就是头指针；

typedef int data_t;  
typedef struct node_t  
{  data_t data;  //数据域  struct node_t *next;  //链接指针域  
}linkstack_t; //链栈类型定义  

栈（链式存储）基本运算如下：
1、创建空栈：

linkstack_t *CreateLinkstack()  
{  linkstack_t *top;  top = (linkstack_t *)malloc(sizeof(linkstack_t));  top->next = NULL;  return top;  
}  

2、判断是否为空栈：

int EmptyStack(linkstack_t *top)  
{  return (top->next == NULL ? 1 : 0);  
}  

3、入栈

void PushStack(linkstack_t *top,data_t x)  
{  linkstack_t *p;  p = (linkstack_t *)malloc(sizeof(linkstack_t));  p->data = x;  p->next = top->next;  top->next = p;  return;  
}  

4、出栈

int PopStack(linkstack_t stack,data_t *x)  
{  if(stack->next == NULL || stack == NULL)  return -1;  linkstack_t p;  p = stack->next;  stack->next = p->next;  if(x != NULL)  *x = p->data;  free(p);  return 0;  
}  

3.3链表、队列及堆栈的区别

1、栈是个有底的口袋，像袜子
队列是没底的口袋，像通心粉。
所以：栈的特点是先进后出，队列的特点是先进先出。
2、主要区别是适用的地方不一样
链表实际上可以认为是一种数据的物理组织形式,是用指针或对象的引用组织起的一种数据的存储方式.
队列和堆栈是一个更高层次的概念,其底层可以是用链表也可以是用数组来实现.
队列和堆栈的主要区别是进出的顺序不一样,
队列是先进先出,堆栈是后进先出.

3、cooled(经典中–经过非典中)
队列和堆栈是一种特殊的数据组织形式。可以把他们看成是一系列的集合。
队列可以看成是有2个口的集合一个口叫队头一个叫队尾，只能在对头进行删除操作，在队尾做插入。根据这样的操作。队列特点是先进先出。

堆栈可以看成是有1个口的集合，这个口叫栈顶。插入和删除操作只能在栈顶操作。根据这样的操作。堆栈的特点是是后进先出.

链表是一种存储方式，它可以在非连续的内存空间里面存储一个集合的元素。和它对应的是数组，数组要在连续的空间里存储集合的元素

这篇关于《数据结构》第3章 栈（C语言描述）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---