數據結構——棧

定義

限定僅在表尾進行插入和刪除操作的線性表。（先入後出）

順序結構

C定義
[cpp]
#define MAXSIZE 20  
 
#pragma mark 順序棧  
 
typedef int SElemType; 
typedef struct { 
    SElemType data[MAXSIZE]; 
    int top; 
}SqStack; 

#define MAXSIZE 20

#pragma mark 順序棧

typedef int SElemType;
typedef struct {
    SElemType data[MAXSIZE];
    int top;
}SqStack;

壓棧操作
[cpp]
int Push(SqStack *S, SElemType e) 
{ 
    if (S->top == MAXSIZE -1) 
        return 0; 
    S->data[++S->top] = e; 
    return 1; 
} 

int Push(SqStack *S, SElemType e)
{
    if (S->top == MAXSIZE -1)
        return 0;
    S->data[++S->top] = e;
    return 1;
}

彈棧操作
[cpp]
int Pop(SqStack *S, SElemType *e) 
{ 
    if (S->top == -1) 
        return 0; 
    *e = S->data[S->top--]; 
    return 1; 
} 

int Pop(SqStack *S, SElemType *e)
{
    if (S->top == -1)
        return 0;
    *e = S->data[S->top--];
    return 1;
}

共享棧

共享棧可以看做是兩個順序棧倒下，棧尾相對的數據結構。通常在兩個棧空間需求有相反關系時使用，例如買入就要賣出等等。

C定義
[cpp]
typedef struct { 
    SElemType data[MAXSIZE]; 
    int top1; 
    int top2; 
}SqDoubleStack; 

typedef struct {
    SElemType data[MAXSIZE];
    int top1;
    int top2;
}SqDoubleStack;

壓棧
[cpp]
int PushDouble(SqDoubleStack *S, SElemType e, int stackNumber) 
{ 
    //棧滿  
    if (S->top1 + 1 == S->top2) 
        return 0; 
    if (stackNumber == 1) 
        S->data[++S->top1] = e; 
    else if (stackNumber == 2) 
        S->data[--S->top2] = e; 
    return 1; 
} 

int PushDouble(SqDoubleStack *S, SElemType e, int stackNumber)
{
    //棧滿
    if (S->top1 + 1 == S->top2)
        return 0;
    if (stackNumber == 1)
        S->data[++S->top1] = e;
    else if (stackNumber == 2)
        S->data[--S->top2] = e;
    return 1;
}

彈棧
[cpp]
int PopDouble(SqDoubleStack *S, SElemType *e, int stackNumber) 
{ 
    if (stackNumber == 1) 
        if (S->top1 == -1)  
            return 0; 
        *e = S->data[S->top1--]; 
    if (stackNumber == 2) 
        if (S->top2 == MAXSIZE)  
            return 0; 
        *e = S->data[S->top2++]; 
    return 1; 
} 

int PopDouble(SqDoubleStack *S, SElemType *e, int stackNumber)
{
    if (stackNumber == 1)
        if (S->top1 == -1)
            return 0;
        *e = S->data[S->top1--];
    if (stackNumber == 2)
        if (S->top2 == MAXSIZE)
            return 0;
        *e = S->data[S->top2++];
    return 1;
}

鏈棧

棧的鏈式存儲結構類似於線性表中的鏈式存儲結構。

C定義
[cpp]
typedef struct StackNode{ 
    SElemType data; 
    struct StackNode *next; 
}StackNode, *LinkStackPtr; 
 
typedef struct LinkStack{ 
    LinkStackPtr top; 
    int count; 
}LinkStack; 

typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPtr;

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

壓棧
[cpp]
int PushLink(LinkStack *S,SElemType e) 
{ 
    LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode)); 
    p->data = e; 
    p->next = S->top; 
    S->top = p; 
    S->count++; 
    return 1; 
} 

int PushLink(LinkStack *S,SElemType e)
{
    LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
    p->data = e;
    p->next = S->top;
    S->top = p;
    S->count++;
    return 1;
}

彈棧
[cpp]
int PopLink(LinkStack *S,SElemType *e) 
{ 
    LinkStackPtr p; 
    *e = S->top->data; 
    p = S->top; 
    S->top = S->top->next; 
    free(p); 
    S->count--; 
    return 1; 
} 

int PopLink(LinkStack *S,SElemType *e)
{
    LinkStackPtr p;
    *e = S->top->data;
    p = S->top;
    S->top = S->top->next;
    free(p);
    S->count--;
    return 1;
}

對比順序棧和鏈棧

兩個數據結構操作都不復雜，時間復雜度相同為O(1)。
順序棧需要固定的長度，但是存取時定位方便。
鏈棧要求有指針域，因此需要增加一些內存開銷，但不同於順序棧限制長度。

棧的應用 —— 遞歸
例如比較有名的斐波那契數列：
[cpp]
int Fbi(int i) 
{ 
    if (i < 2) 
        return i == 0? 0: 1; 
    return Fbi(i - 1) + Fbi(i - 2); 
} 

int Fbi(int i)
{
    if (i < 2)
        return i == 0? 0: 1;
    return Fbi(i - 1) + Fbi(i - 2);
}