http://www.cnblogs.com/longyi1234/archive/2010/03/28/1698803.html 2010.03 栈(Stack)是限定只能在表的一端进行插入和删除操作的线性表。在表中,允许插入和删除的一端称作“栈顶(top)”,不允许插入和删除的另一端称作“栈底(bottom)”。
通常称往栈顶插入元素的操作为“入栈”,称删除栈顶元素的操作为“出栈”。因为后入栈的元素先于先入栈的元素出栈,故被称为是一种“后进先出”的结构,因此又称 LIFO 表(Last In First Out的缩写)。 和线性表类似,栈也有两种存储表示:顺序栈和链栈。 顺序存储结构简称为顺序栈。和顺序表类似,对顺序栈也需要事先为它分配一个可以容纳最多元素的存储空间。用图表示顺序栈如下:
链栈即为栈的链式存储结构。
顺序栈的实现依靠数组,而数组需要事先声明长度,一次性地静态地分配内存空间。这样就给我们带来很多不便。因为我们事先并不能精确地估计栈所需的大小,估计大了浪费空间,估计小了后果就严重了,导致程序无法正常运行。所以我们通常使用链栈这种数据结构。 链栈用链表作为存储结构,栈初始化时仅需给栈顶指针分配内存空间,而后每当有数据入栈时再为该数据分配空间,这样实现了内存空间的动态分配。理论上栈的大小可以是无限大的(小心撑爆你的内存 o(∩_∩)o)。不存在顺序栈的诸多问题。 程序实现:依次把0~99压栈,再依次出栈并打印。 LinkStack.h /* LinkStack.h */ #include <stdlib.h> #define TRUE 1 #define FALSE 0 #define NULL 0 typedef int ElementType; typedef struct node { ElementType data; struct node *next; }StackNode, *LinkStack; void InitStack(LinkStack top) { top->next = NULL; } int IsEmpty(LinkStack top) { if(top->next == NULL) return TRUE; return FALSE; int Push(LinkStack top, ElementType element) {StackNode *temp; temp = (StackNode *)malloc(sizeof(StackNode)); if(temp == NULL) return FALSE; temp->data = element; temp->next = top->next; top->next = temp; return TRUE; } int Pop(LinkStack top, ElementType *element) { if(IsEmpty(top)) return FALSE; StackNode *temp = top->next; *element = temp->data; top->next = temp->next; free(temp); return TRUE; void GetTop(LinkStack top, ElementType *element) {*element = top->next->data; }
LinkStackTest.c /* LinkStackTest.c */ #include <stdio.h> #include "LinkStack.h" void main() { LinkStack s; s = (LinkStack)malloc(sizeof(StackNode)); InitStack(s); for(int i=0; i<100; i++) Push(s,i); int rslt; while (!IsEmpty(s)) { Pop(s,&rslt); printf("%d ",rslt); } } } |
|