[数据结构与算法]数据结构之栈——C语言描述

数据结构之栈——C语言描述

• 栈是一种操作受限的数据结构，其特点是后进先出
• 基于动态内存分配实现栈
• 数据结构包括栈底指针，栈顶指针以及以及一个记录栈大小的整型量

#include "stdio.h"
#include "stdlib.h"

const int MAXSIZE=10;

//数据类型
typedef struct student{
    int age;
    char name[20];
} Student;

//栈数据结构
typedef struct {
    Student* base;   //栈底指针
    Student* top;    //栈顶指针
    int size;       //栈容量
}SqStack;

//初始化栈
void InitStack(SqStack &s){
    s.base=(Student *)malloc(MAXSIZE* sizeof(Student));   //动态分配内存空间
    s.top=s.base;
    s.size=MAXSIZE;
}

//入栈
void Push(SqStack &s,Student e){
    if(s.top-s.base==s.size)
        return ;
    *s.top=e;
    s.top++;
}

//出栈
void Pop(SqStack &s){
    if(s.top=s.base)
           return;
    s.top--;
}

//取栈顶
Student GetTop(SqStack s){
    if(s.top!=s.base)
        return *(s.top-1);
}

int main(){
    SqStack s;
    InitStack(s);
       return 0;
}

• 基于定容数组实现栈
• 数据结构包括一个定容数组以及一个整型变量，用来记录栈顶指针所指向的位置，但实际上其并不是一个真正的指针

#include "stdio.h"
#include "stdlib.h"

const int MAXSIZE=10,ERROR=0,OK=1;

//数据类型
typedef struct student{
    int age;
    char name[20];
} Student;

//栈数据结构
typedef struct {
   Student student[MAXSIZE];  //定容数组栈
    int top;       //栈容量
}SqStack;

//初始化栈
int InitStack(SqStack &s){
    s.top=-1;      //top指针指向-1
    return OK;
}

//入栈
int Push(SqStack &s,Student e){
    if(s.top>=MAXSIZE-1)  //判满
        return ERROR;
    s.student[++s.top]=e;
}

//出栈
int Pop(SqStack &s){
    if(s.top==-1)        //判空
        return ERROR;
    s.top--;
}

//取栈顶
Student GetTop(SqStack s){
    if(s.top!=-1) 
        return s.student[s.top];
}

int Destroy(SqStack &s){
    s.top=-1;
}

int main(){
    SqStack s;
    InitStack(s);
       return 0;
}