栈
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; }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
