進(jìn)棧與出棧

1. 順序棧

typedef int Status;
typedef int SElemType; /* SElemType類型根據(jù)實際情況而定丧慈，這里假設(shè)為int */

/* 順序棧結(jié)構(gòu) */
typedef struct
{
    SElemType data[MAXSIZE];
    int top; /* 用于棧頂指針 */
}SqStack;
/*  構(gòu)造一個空棧S */
Status InitStack(SqStack *S)
{
    /* S.data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */
    S->top=-1;
    return OK;
}
/* 插入元素e為新的棧頂元素 */
Status Push(SqStack *S,SElemType e)
{
    if(S->top == MAXSIZE -1) /* 棧滿 */
    {
        return ERROR;
    }
    S->top++;                /* 棧頂指針增加一 */
    S->data[S->top]=e;  /* 將新插入元素賦值給棧頂空間 */
    return OK;
}

/* 若棧不空，則刪除S的棧頂元素，用e返回其值逃默，并返回OK鹃愤；否則返回ERROR */
Status Pop(SqStack *S,SElemType *e)
{
    if(S->top==-1)
        return ERROR;
    *e=S->data[S->top];    /* 將要刪除的棧頂元素賦值給e */
    S->top--;                /* 棧頂指針減一 */
    return OK;
}

2. 鏈?zhǔn)綏?/h3>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存儲空間初始分配量 */
typedef int Status;
typedef int SElemType; /* SElemType類型根據(jù)實際情況而定，這里假設(shè)為int */

/* 鏈棧結(jié)構(gòu) */
typedef struct StackNode
{
   SElemType data;
   struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct
{
   LinkStackPtr top;
   int count;
}LinkStack;

/*  構(gòu)造一個空棧S */
Status InitStack(LinkStack *S)
{
   S->top = (LinkStackPtr)malloc(sizeof(StackNode));
   if(!S->top)
       return ERROR;
   S->top=NULL;
   S->count=0;
   return OK;
}

/* 插入元素e為新的棧頂元素 */
Status Push(LinkStack *S,SElemType e)
{
   LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
   s->data=e;
   s->next=S->top;    /* 把當(dāng)前的棧頂元素賦值給新結(jié)點的直接后繼完域，見圖中① */
   S->top=s;         /* 將新的結(jié)點s賦值給棧頂指針软吐，見圖中② */
   S->count++;
   return OK;
}

/* 若棧不空，則刪除S的棧頂元素吟税，用e返回其值凹耙，并返回OK；否則返回ERROR */
Status Pop(LinkStack *S,SElemType *e)
{
   LinkStackPtr p;
   if(StackEmpty(*S))
       return ERROR;
   *e=S->top->data;
   p=S->top;                    /* 將棧頂結(jié)點賦值給p肠仪，見圖中③ */
   S->top=S->top->next;    /* 使得棧頂指針下移一位肖抱，指向后一結(jié)點，見圖中④ */
   free(p);                    /* 釋放結(jié)點p */
   S->count--;
   return OK;
}

空間復(fù)雜度:
不管是順序棧還是鏈?zhǔn)綏Ｒ炀桑覀兇鎯?shù)據(jù)只需要一個大小為 n 的數(shù)組就夠了意述。在入棧和出棧過程中，只需要一兩個臨時變量存儲空間吮蛹，所以空間復(fù)雜度^[1]是 O(1)荤崇。
時間復(fù)雜度:
時間復(fù)雜度也同樣，不管是順序棧還是鏈?zhǔn)綏Ｆヤ蹋霔Ｌ焓浴⒊鰲Ｖ簧婕皸ｍ攤€別數(shù)據(jù)的操作槐壳，所以時間復(fù)雜度都是 O(1)然低。

[1]:這里存儲數(shù)據(jù)需要一個大小為 n 的數(shù)組，并不是說空間復(fù)雜度就是 O(n)务唐。因為雳攘，這 n 個空間是必須的，無法省掉枫笛。所以我們說空間復(fù)雜度的時候吨灭，是指除了原本的數(shù)據(jù)存儲空間外，算法運行還需要額外的存儲空間刑巧。

應(yīng)用場景

• 函數(shù)調(diào)用棧
• 表達(dá)式求知
• 括號匹配

源碼

本文完整源碼地址

參考文獻(xiàn)

• 數(shù)據(jù)結(jié)構(gòu)與算法之美-王爭
• 大話數(shù)據(jù)結(jié)構(gòu)-程杰