数据结构之栈

2018-06-17 21:07:42来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

   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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:ccf-20171203 Crontab问题

下一篇:POJ1275 Cashier Employment(差分约束)