数据结构与算法-栈

如何理解“栈”？

后进先出(LIFO-last in first out):最后插入的元素最先出来。
关于“栈”，有一个非常贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。后进者先出，先进者后出，这就是典型的“栈”结构。

从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。

实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

顺序栈

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

/* 顺序栈结构 */
//Sequence Stack
typedef struct {
    SElemType data[MAXSIZE];
    int top; //栈顶指针，这里的指针（记录位置）并非c中的指针，
} SqStack;

//1.初始化空栈
Status initStack(SqStack *S) {
    S->top = -1;
    return OK;
}

//2.置空栈
Status clearStack(SqStack *S) {
    //这里不需要清空数组中的元素，编译器在编译阶段就知道该为这个数组分配多少内存了，这就叫静态分配,静态分配的内存在栈里，每进入一个函数时都会建栈，栈里会存放函数用到的参数、局部变量等信息，函数执行完以后，会出栈销毁栈，这个过程就会释放你静态分配的数组内存，这是由系统自动完成的。
    S->top = -1;
    return OK;
}

//3.判断栈空
Status stackEmpty(SqStack S) {
    //结构体点语法
    return S.top == -1;
}

//4.进栈push
Status stackPush(SqStack *s,SElemType e) {
    //判断栈满
    if (s->top == MAXSIZE-1) {
        return ERROR;
    }
    //栈顶指针加一，将新插入的元素赋值给栈顶空间
    s->data[++s->top] = e;
    return OK;
}

//5.pop出栈，并且用e带回
Status pop(SqStack *s,SElemType *e) {
    //判断栈空
    if (stackEmpty(*s)) {
        return ERROR;
    }
    //栈顶指针-1；
    *e = s->data[s->top--];
    return OK;
}

//6.获取栈顶元素
Status getTopElem(SqStack s,SElemType *e) {
    //判断栈空
    if (stackEmpty(s)) {
        return ERROR;
    }
    
     *e = s.data[s.top];
    return OK;
}

//7. 从栈底到栈顶依次打印栈中的每个元素
Status stackTraverse(SqStack s){
    int i = 0;
    printf("此栈中所有元素:\n");
    while (i<=s.top) {
        printf("%d ",s.data[i++]);
    }
    printf("\n");
    return OK;
}

int main(int argc, const char * argv[]) {
   
    printf("Hello, World!\n");
    
//    SqStack *Sq = (SqStack *)malloc(sizeof(SqStack));//若使用指针要给指针开辟内存区域
    SqStack Sq;//在函数中定义变量，系统会自动为变量分配内存保存到栈中
    printf("%p",&Sq);
    initStack(&Sq);
    for (int i=0; i<10; i++) {
        stackPush(&Sq, i);
    }
    stackTraverse(Sq);

    
    return 0;
}

链式栈

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */
//链栈节点
typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;

//定义栈
typedef struct {
    LinkStackPtr top;//栈顶指针
    int count;
}LinkStack;

//1.创建一个空栈
Status InitStack(LinkStack *s) {
    (s)->top = NULL;
    (s)->count = 0;
    return OK;
}

//2.置空
Status clearStack(LinkStack *s) {
    LinkStackPtr p,q;
    p = s->top;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    (s)->count = 0;
    return OK;
}

//3.判断栈空
Status emptyStack(LinkStack s) {
    if (s.count == 0) {
        return TRUE;
    } else {
        return FALSE;
    }
}

//4.返回栈长
int lentthStack(LinkStack s) {
    return s.count;
}

//5.取栈顶元素
Status getTopElem(LinkStack s, SElemType *e) {
    //判断栈空
    if (emptyStack(s)) {
        return ERROR;
    }
    *e = s.top->data;
    return OK;
}

//6.push入栈
Status pushStack(LinkStack *s,SElemType e) {
    //创建一个节点
    LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));
    if (temp == NULL) {
        return ERROR;
    }
    
    temp->data = e;
    //头插入栈
    temp->next = s->top;
    s->top = temp;
    s->count++;
    
    return OK;
}

//7.遍历打印栈中的元素
void traverseStack(LinkStack s) {
    LinkStackPtr p = s.top;
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
}


Status popStack(LinkStack *s,SElemType *e) {
     //判断栈空
    if (emptyStack(*s)) {
        return ERROR;
    }
    //头删
    LinkStackPtr p;
    p = s->top;
    *e = p->data;
    s->top = s->top->next;
    free(p);
    s->count--;
    return OK;
}


int main(int argc, const char * argv[]) {
    
    LinkStack p;
        
    InitStack(&p);
    
    for (int i = 0; i<10; i++) {
        pushStack(&p, i);
    }
    traverseStack(p);
    SElemType e;
    popStack(&p, &e);
    printf("\n%d", e);
    traverseStack(p);
    
    return 0;
}