數據結構之棧

棧

   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;
}