数据结构之栈
2018-06-17 21:07:42来源:未知 阅读 ()
栈
1.定义:栈是限定仅在表尾进行插入或删除操作的线性表。因此,对栈来说,表尾端有其特殊含义,称为栈顶,相应地,
表头端称为栈底。不含元素的空表称为空栈。
假设栈S=(a1,a2,a3,...,an),则称a1为栈底元素,an为栈顶元素。栈中元素按a1,a2,a3,...,an的次序进栈,退栈的第
一个元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的。因此栈又称为后进先出的线性表。因此数据结构
为:
#define STACK_INIT_SIZE 100 struct BinTreeNode; struct StkNode; typedef enum {L, R}Tag; typedef struct StkNode { struct BinTreeNode *ptr; Tag tag; }StkNode; #ifdef PREORIN #define ElemTypeStack BinTreeNode* #else #define ElemTypeStack StkNode #endif typedef struct Stack { ElemTypeStack *base; size_t capacity; int top; }Stack;
2.因此在栈中有以下操作:
bool IsFull(Stack *st); bool IsEmpty(Stack *st); void InitStack(Stack *st, int sz); void PushStack(Stack *st, ElemTypeStack x); void ShowStack(Stack *st); void PopStack(Stack *st); ElemTypeStack GetTop(Stack *st); void ClearStack(Stack *st);
以上的方法有以下操作:(1)判断栈是否是满状态.(2)判断栈是否是空状态.(3)初始化一个栈操作.(4)向栈中
压入元素.(5)展示栈中的内容.(6)删除栈中元素.(7)获取栈顶元素.(8)清除栈.
3.将上面声明的方法进行实现:
bool IsFull(Stack *st) { return st->top >= st->capacity; } bool IsEmpty(Stack *st) { return st->top == 0; } void InitStack(Stack *st, int sz=STACK_INIT_SIZE) { st->capacity = sz > STACK_INIT_SIZE ? sz : STACK_INIT_SIZE; st->base = (ElemTypeStack*)malloc(sizeof(ElemTypeStack)*st->capacity); assert(st->base != NULL); st->top = 0; } void PushStack(Stack *st, ElemTypeStack x) { if(IsFull(st)) { cout<<"栈已满,"<<x<<"不能入栈."<<endl; return; } st->base[st->top++] = x; } void ShowStack(Stack *st) { for(int i=STACK_INIT_SIZE-1; i>=0; --i) { cout<<i<<" : "; if(i >= st->top) cout<<"Nul."<<endl; else cout<<st->base[i]<<"."<<endl; } } void PopStack(Stack *st) { if(IsEmpty(st)) { cout<<"栈已空,不能入栈."<<endl; return; } st->top--; } ElemTypeStack GetTop(Stack *st) { assert(!IsEmpty(st)); return st->base[st->top-1]; } void ClearStack(Stack *st) { st->top = 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ 自动转换和强制类型转换(用户自定义类类型) 2020-06-10
- C++ 类 2020-06-02
- 二叉搜索树_BST 2020-05-30
- 数据结构—链表 2020-05-29
- C++ 单定义规则 2020-05-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash