本文主要是介绍《数据结构》第3章 栈（C语言描述），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
栈是限制在一段进行插入操作和删除操作的线性表（俗称堆栈），允许进行操作的一端称为“栈顶”，另一固定端称为“栈底”，当栈中没有元素称为“空栈”。特点：先进后出（FILO）。
栈顶即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; //顺序栈类型定义
如图，我们可以看到，栈的顺序存储与顺序表的区别，顺序表数组大小是固定的，这样限制了我们的后期修改，而栈的顺序存储将数据域单独开辟了一片空间才存放，大小为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语言描述）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
