資料結構複習代碼——棧的順序實作以及一些基本操作

1、棧的基本結構以及順序實作下的一些基本操作

#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#include<stdlib.h>

#define ElemType int
#define STACK_INIT_SIZE 8
#define STACK_INC_SIZE 3
typedef struct SeqStack
{
    ElemType *base;     //每個節點的資料域
    int capacity;       //目前棧容量
    int top;            //棧頂指針
}SeqStack;

//初始化棧
void InitStack(SeqStack *s)
{
    s->base = (ElemType*)malloc(sizeof(ElemType)*STACK_INIT_SIZE);  //為棧配置設定記憶體空間并指派給首址
    assert(s->base != NULL);        //判斷記憶體空間是否配置設定成功
    s->capacity = STACK_INIT_SIZE;  //棧最大空間初始化指派給最大容量
    s->top = 0;                     //棧頂指針指派，指向0
}
//輔助函數--判空操作
int IsEmpty(SeqStack *s)
{
    if(s->top == 0)
    {
        return 1;
    }else{
        return 0;
    }
}
//輔助函數--判滿操作
int IsFull(SeqStack *s)
{
    if(s->top == s->capacity)
    {
        return 1;
    }else{
        return 0;
    }
}
//輔助函數--周遊棧
void Show(SeqStack *s)
{
    for(int i=s->top-1;i>=0;i--)
    {
        printf("%d \n",s->base[i]);
    }
}
//輔助函數--擷取棧頂元素
int GetElem(SeqStack *s,ElemType *e)
{
    if(IsEmpty){
        printf("該棧已空！！");
        return 0;
    }
    int i = s->top;
    e = s->base[i-1];
    return 1;
}
//輔助函數--擷取目前棧的長度
int Length(SeqStack *s){
    //由于該棧定義時，棧頂指針是從0開始的，即目前棧的長度為棧頂指針所指
    return s->top;
}
//輔助操作--增加棧記憶體空間
int Inc(SeqStack *s)
{
    //使用realloc函數為s->base配置設定新的記憶體空間
    ElemType *newbase = (ElemType*)realloc(s->base,sizeof(ElemType)*(s->capacity+STACK_INC_SIZE));
    //此磁盤中已無記憶體空間可配置設定給次棧
    if(newbase == NULL)
    {
        printf("記憶體空間已滿！無法再次申請空間！");
        return 0;
    }
    //将新配置設定的記憶體空間首址指派給棧
    s->base = newbase;
    //擴大該棧的最大容量
    s->capacity += STACK_INC_SIZE;
    return 1;
}
//入棧操作
void Push(SeqStack *s,ElemType e)
{
    if(IsFull(s)&& !Inc(s))
    {
        printf("棧空間已滿，不能入棧！！");
        return;
    }
    s->base[s->top] = e;
    s->top++;
}

//出棧操作
void Pop(SeqStack *s)
{
    if(IsEmpty(s)){
        printf("棧已空，無元素可出棧！！");
        return;
    }
    --s->top;
    //printf("出棧元素為：%d \n",s->base[s->top]);
}
//清除棧操作
void Clear(SeqStack *s)
{
    //關于清除棧操作，隻需将棧頂指針歸零即可
    //因為該棧内的相關元素已無實用價值，可以任意改變
    s->top = 0;
}
//摧毀棧操作
void Destroy(SeqStack *s)
{
    //摧毀棧，需要釋放已配置設定該棧的記憶體空間
    free(s->base);
    s->base=NULL;
    s->capacity = s->top = 0;
}

int main()
{

    SeqStack *st;       //定義一個棧
    InitStack(&st);     //實行初始化
    ElemType e;         //定義變量---實作棧頂元素取值時的存儲
    //以下隻是我簡單進行的一些操作，具體需要實作的操作可自行實作
    for(int i=1;i<10;i++)   //循環入棧
    {
        Push(&st,i);
    }
    Show(&st);
    //Destroy(&st);
    return 0;
}