栈

定义——栈( stack)是限定仅在表尾巴插入和删除操作的线性表

• 允许插入和删除的一段称为栈顶(top)，另一端称为栈底(bottom)

• 不放任何数据元素的栈称为空栈

 

特点

• 先进后出

• 后进先出

 

注意：

• 栈又被称为后进先出(Last In First Out)的线性表，简称LIFO结构

• 栈的插入操作，称为进栈，也称压栈、入栈(push)

• 栈的删除操作，称为出栈，也称为弹栈(pop)

 

栈的抽象数据结构

 

栈的链式存储结构——链栈

链栈

• 链栈的结构与链表相似

• 插入与删除操作都是在链表的头部

• 即：链栈是一个以top为头结点、从链顶指向链底的单链表

typedef struct node //栈中的节点
{
    char data; //节点数据
    struct node *next;//指向下一个结点的指针(链表)
}StackNode;

typedef struct{
    StackNode *top;//栈顶指针
    int count; //节点个数
}ListStack;