棧的順序儲存和鍊式儲存

棧

##順序棧的定義

• 棧是一種先進後出的結構，屬于一種線性結構
• 棧頂指針用于控制資料的壓入與彈出
• 當棧為空時top == -1

#define max 20
typedef struct  
{
    int data[20];
    int top;
}stack;
           

##順序棧的壓入與彈出

int push(stack *p , int data)
{
    if (p ->top == max - 1) return 0;
    p ->top ++;
    p ->data[p->top] = data;
    return 1;
}
int pop (stack *p, int *s)
{
    if (p ->top == -1) return 0;
    *s = p ->data[p->top];
    p->top --;
    return 1;
}
           

倆個順序棧共享一個數組空間的實作

###存儲

• top1是第一個棧的頭指針，top2是第二個棧的頭指針
• top1為-1時，表示第一個棧為空， top2為max時，表示第二棧為空
• top1 + 1 == top2 表示棧已經滿了

#define max 20
typedef struct 
{
    int data [max];
    int top1;
    int top2;
}doublestack;
           

彈入與壓出

int push (doublestack *p , int data , int number)
{
    if (p->top1 + 1 == p->top2) return 0;

    if (number == 1){
        p->data[++ p->top1] = data;
    }
    else{
        p->data[-- p->top2] = data;
    }
    return 1;
}

int pop(doublestack *p , int *data , int number)
{
    if (number == 1){
        if (p->top1 == -1) return 0;
        else {
            *data = p->data[p->top1 --];
        }
    }

    else {
        if (p->top2 == max) return 0;
        else {
            *data = p->data[p->top2 ++];
        }
    }
    return 1;
}
           

鍊式棧

儲存

typedef struct node
{
    int data;
    struct node *next;
}stacknode , *linkstackptr;

struct linkstack
{
    linkstackptr top;
    int count;
};
           

###壓入與彈出

• 彈出與壓入的方式與連結清單的操作類似，将頭指針看作棧頂指針
• 不存在頭結點

void push (linkstack *p , int data)
{
    linkstackptr newnode = (linkstackptr)malloc(sizeof(stacknode));
    newnode->data = data;
    newnode->next = p->top;
    p->top = newnode;
    p->count ++;
}
int pop (linkstack *p , int *data)
{
    linkstackptr temp;
    if (p->top == NULL) return ;
    *data = p->top->data;
    temp = p->top;
    p->top = p->top->next;
    free(temp);
    p->count --;
    return 1;
}