个数 urn nbsp bottom height enter isp 头指针
栈的基本概念
定义:栈 (Stack) 是限制仅在表的一端进行插入和删除操作的线性表。
允许进行插入和删除的一端称为栈顶 (top)
不允许插入和删除的一端称为栈底 (bottom)
不含元素的栈称为空栈。
往栈中存入元素称为入栈
从栈中删除元素称为出栈
特点:后进先出 (LIFO) 或先进后出(FILO)
顺序栈的类型说明:
- //顺序栈的类型说明:
- #defineMAXSIZE 100
- typedef struct
- {
- int data[MAXSIZE];
- int top;
- }SqStack;
双向栈:
- //双向栈
- //为了充分利用栈的空间,采用多个栈共享同一空间。
- //双向栈用一个大数组表示。
- //两个栈共享一个数组的数据结构定义如下:
- #defineMAX 100
- typedef struct
- {
- int data[MAX];
- int top1,top2;
- }SStack2;
链栈
栈的链式存储结构称为链栈,它是运算受限的单链表,其插入和删除操作仅限制在表头位置上进行.
由于只能在链表头部进行操作,故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。
其类型说明为:
- //链栈
- typedef struct SNode
- {
- int data;
- structSNode *next;
- }SNode,*LinkStack;
- LinkStack *top;
(1) 初始化栈 top=NULL;
(2) 判断空栈 top==NULL;
(3) 取栈顶 top–>data;
(4) 入栈:
- voidpush(PSTACK S,int val)
- {
- PNODE pNew=(PNODE)malloc(sizeof(NODE));
- if(pNew==NULL)
- {
- printf("分配失败程序终止");
- exit(-1);
- }
- else
- {
- pNew->data=val;
- pNew->pNext=S->pTop;
- S->pTop=pNew;
- }
- }
(5) 出栈:
- boolpop(PSTACK S,int* val)
- {
- if(empty(S))
- {
- return false;
- }
- else
- {
- PNODE p=S->pTop;
- *val=p->data;
- S->pTop=p->pNext;
- free(p);
- p=NULL;
- return true;
- }
- }
数据结构之栈
来源: http://www.bubuko.com/infodetail-2075866.html