数据结构C语言-顺序栈、共享栈、链栈的定义、销毁及出入栈操作

顺序栈声明部分：

每个函数的具体定义：

共享栈声明部分：

每个函数的具体定义：

链栈声明部分：

每个函数的具体定义：

顺序栈声明部分：

#define MAX_SIZE 10

typedef struct
{
    int data[MAX_SIZE];
    int top; //栈顶指针（栈顶元素数组下标,空栈为-1）
} SqStack;   // SqStack 顺序栈

SqStack CreateStack();            //创建顺序栈
int Push(SqStack *S, int elem);   //进栈
int Pop(SqStack *S, int *temp);   //出栈，并用temp带出
int GetTop(SqStack S, int *temp); //读取栈顶元素，并用temp带出
int StackIsEmpty(SqStack S);      //判空：=1为空栈，=0为非空栈

每个函数的具体定义：

创建顺序栈：

SqStack CreateStack()
{
    SqStack S;
    S.top = -1;
    return S;
}

进栈：

int Push(SqStack *S, int elem)
{
    if (S->top == MAX_SIZE - 1)
    {
        printf("栈满，入栈失败n");
        return 0;
    }

    S->top++;
    S->data[S->top] = elem;
    return 1;
}

出栈（并用temp带出出栈元素的值）：

int Pop(SqStack *S, int *temp)
{
    if (S->top == -1)
    {
        printf("栈空，出栈失败n");
        return 0;
    }

    *temp = S->data[S->top];
    S->top--;
    return 1;
}

读取栈顶元素，并用temp带出：

int GetTop(SqStack S, int *temp)
{
    if (S.top == -1)
    {
        printf("栈空，查询失败n");
        return 0;
    }

    *temp = S.data[S.top];
    return 1;
}

判空（=1为空栈，=0为非空栈）：

int StackIsEmpty(SqStack S)
{
    return S.top == -1;
}

共享栈声明部分：

typedef struct
{
    int data[MAX_SIZE];
    int top1, top2; //1,2号栈顶指针,1号自底向上，2号自顶向下
} ShStack;          //ShStack 共享栈

ShStack CreateShStack();                       //创建共享栈
int ShPush(ShStack *S, int stack, int elem);   //elem进stack号栈
int ShPop(ShStack *S, int stack, int *temp);   //stack号栈出栈，并用temp带出
int ShGetTop(ShStack S, int stack, int *temp); //得到stack的顶指针指向的元素
int ShStackIsEmpty(ShStack S);                 //判空：=1为空栈，=0为非空栈
int ShStackIsFull(ShStack S);                  //判满: =1为满栈，=0为非满栈

每个函数的具体定义：

创建共享栈：

ShStack CreateShStack()
{
    ShStack S;
    S.top1 = -1;
    S.top2 = MAX_SIZE;
    return S;
}

入栈（elem进stack号栈）：

int ShPush(ShStack *S, int stack, int elem)
{
    if (stack != 1 && stack != 2)
    {
        printf("输入的栈非法，插入失败n");
        return 0;
    }
    if (S->top1 + 1 == S->top2)
    {
        printf("栈满，入栈失败n");
        return 0;
    }

    if (stack == 1)
    {
        S->top1++;
        S->data[S->top1] = elem;
    }
    else
    {
        S->top2--;
        S->data[S->top2] = elem;
    }
    return 1;
}

出栈（stack号栈出栈，并用temp带出）：

int ShPop(ShStack *S, int stack, int *temp)
{
    if (stack != 1 && stack != 2)
    {
        printf("输入的栈非法，入栈失败n");
        return 0;
    }
    if (stack == 1)
    {
        if (S->top1 == -1)
        {
            printf("1号栈空，出栈失败n");
            return 0;
        }
        *temp = S->data[S->top1];
        S->top1--;
    }
    else
    {
        if (S->top2 == MAX_SIZE)
        {
            printf("2号栈空，出栈失败n");
            return 0;
        }
        *temp = S->data[S->top2];
        S->top2++;
    }
    return 1;
}

得到stack的顶指针指向的元素的值：

int ShGetTop(ShStack S, int stack, int *temp)
{
    if (stack != 1 && stack != 2)
    {
        printf("输入的栈非法，入栈失败n");
        return 0;
    }
    if (stack == 1)
    {
        if (S.top1 == -1)
        {
            printf("1号栈空，出栈失败n");
            return 0;
        }
        *temp = S.data[S.top1];
    }
    else
    {
        if (S.top2 == MAX_SIZE)
        {
            printf("2号栈空，出栈失败n");
            return 0;
        }
        *temp = S.data[S.top2];
    }
    return 1;
}

判空（=1为空栈，=0为非空栈）与判满（=1为满栈，=0为非满栈）：

int ShStackIsEmpty(ShStack S) //判空
{
    return (S.top1 == -1 && S.top2 == MAX_SIZE);
}

int ShStackIsFull(ShStack S) //判满
{
    return (S.top1 + 1 == S.top2);
}

链栈声明部分：

typedef struct Linode
{
    int data;
    struct Linode *next; //用单链表结点定义栈元素
} Linode, *LiStack;      // LiStack 链栈,通过对头结点后继节点的插入删除实现出入栈

//以下链栈为带头结点的链栈
LiStack CreateLiStack();            //创建链栈
void DestoryLiStack(LiStack *L);    //销毁链栈
int LiPush(LiStack L, int elem);    //通过单链表头插法入栈
int LiPop(LiStack L, int *temp);    //通过单链表后删头结点的后继结点操作出栈
int LiGetTop(LiStack L, int *temp); //读取栈顶元素，并用temp带出
int LiStackIsEmpty(LiStack L);      //判空：=1为空栈，=0为非空栈

#endif

每个函数的具体定义：

创建链栈：

LiStack CreateLiStack()
{
    LiStack L = (Linode *)malloc(sizeof(Linode));
    L->data = 0;
    L->next = NULL;
    return L;
}

销毁链栈：

void DestoryLiStack(LiStack *L)
{
    Linode *p = (Linode *)malloc(sizeof(Linode));
    while((*L))
    {
        p = *L;
        (*L) = (*L)->next;
        free(p);
    }
}

通过单链表头插法入栈：

int LiPush(LiStack L, int elem)
{
    if (L == NULL) 
    {
        printf("输入的栈非法，入栈失败n");
        return 0;
    }

    Linode *new = (Linode *)malloc(sizeof(Linode));
    if (new == NULL)
    {
        printf("内存不足，无法入栈");
        return 0;
    }

    new->data = elem;
    new->next = L->next;
    L->next = new;
    return 1;
}

通过单链表后删头结点的后继结点操作出栈：

int LiPop(LiStack L, int *temp)
{
    if (L == NULL) 
    {
        printf("输入的栈非法，入栈失败n");
        return 0;
    }

    Linode *p = (Linode *)malloc(sizeof(Linode));
    if (p == NULL)
    {
        printf("内存不足，无法入栈");
        return 0;
    }

    p = L->next;
    if(p == NULL)
    {
        printf("空栈，无元素可出栈n");
        return 0;
    }
    *temp = p->data;
    L->next = p->next;
    free(p);
    return 1;
}

读取栈顶元素，并用temp带出：

int LiGetTop(LiStack L, int *temp)
{
    if (L == NULL) 
    {
        printf("输入的栈非法，入栈失败n");
        return 0;
    }
    if (L->next == NULL)
    {
        printf("空栈，无元素n");
        return 0;
    }
    else
    {
        *temp = L->next->data;
    }
    return 1;
}

判空（=1为空栈，=0为非空栈）：

int LiStackIsEmpty(LiStack L)
{
    return (L->next == NULL);
}

个人代码，如有误请指出。

数据结构C语言-顺序栈、共享栈、链栈的定义、销毁及出入栈操作

C/C++/C#相关栏目本月热门文章