记得大一的时候自学数据结构，那时候却没有深入的去研究代码，只是了解了个表面的东西，不过还好有基础，并且去年的时候看了算法一书，Java实现，算是深入研究了下算法，现在再看数据结构与算法也比较熟悉了。
对于数据结构，我觉得主要第一个是理解这种数据结构的特点，然后就是用代码实现，然后尝试将这种数据结构进行应用。
另外研究数据结构，要从逻辑结构，存储结构和操作进行。

1. 栈
   允许在一端进行插入或者删除的线性表。
   栈的明显操作特性是后进先出。
   基本操作无非是初始化，出栈，入栈，读栈顶元素，判断是否为空，销毁栈，这些操作在下面都会得以实现，使用C语言。
2. 栈的顺序存储结构
   顺序栈，使用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时设指针指示当前栈顶位置。
   注意入栈出栈的时候的数组引用角标的变化，是++S.top还是S.top++。
   顺序栈的实现：

#include <stdio.h>
#include <stdlib.h>
#include "sqStack.h"
//定义bool类型
#define bool int
#define true 1
#define false 0
//顺序栈
//定义栈中元素个数
#define Maxsize 50
//定义数据类型和数据结构
typedef int ElemType;
typedef struct {
    ElemType data[Maxsize];
    //栈顶指针
    int top;
}SqStack;
//初始化操作
//通过传址(引用)来起到修改原来结构的作用
void initStack(SqStack *S){
    //初始化也就是将栈顶指针设置为－1
    S -> top = -1;
}
//判断栈是不是空
//C语言中没有bool这个类型，需要自己定义
bool emptyStack(SqStack *S){
    if(S -> top == -1){
        return true;
    }else{
        return false;
    }
}
//进栈
bool push(SqStack *S,ElemType x){
    //首先判断栈是否满了
    if (S -> top == Maxsize - 1){
        return false;
    }
    //进栈,先将栈顶指针增加，然后再赋值
    S -> data[++S->top] = x;
    return true;
}
//出栈
//ElemType &x是一个引用 下面直接用x = S -> data[S->top --];
//类似于scanf("%d",&x)
//引用就是指针，
bool pop(SqStack *S,ElemType *x){
    //判断栈是否为空
    if (S -> top == -1){
        return false;
    }
    //出栈，先将栈顶的值获取，再将指针减一
    *x = S -> data[S -> top --];
    return true;
}
//读栈顶元素
bool getTop(SqStack *S,ElemType *x){
    if(S->top == -1){
        return false;
    }
    *x = S -> data[S -> top];
    return true;
}
//销毁栈
bool clearStack(SqStack *S){
    if (S -> top == -1){
        return false;
    }
    //销毁就是将top指针置为－1
    S -> top = -1;
    return true;
}
//打印整个栈
void printStack(SqStack *S){
    if(S -> top == -1){
        printf("empty stack\n");
    }
    int x;
    printf("top");
    while(S->top != -1){
        pop(S,&x);
        printf("-> %d",x);
    }
    printf("\n");
}
int main(){
    SqStack *S;
    initStack(S);
    int x;
    for(int i=0;i<=10;i++){
        x = i;
        push(S, x);
    }
    int y;
    pop(S, &y);
    printf("poped element is %d\n",y);
    printStack(S);
}```
3. 共享栈
让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
当两个栈顶指针相邻，top1-top0＝1的时候，判断为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减一再赋值，出栈的时候相反。
4. 栈的链式存储结构
便于多个栈共享存储空间和提高其效率，不存在栈满上溢的情况，通常采用单链表实现。
实现：

include <stdio.h>

include <stdlib.h>

include "LinkStack.h"

//另外一个共享栈，就是栈底分别在数组的开始于结束处，比较简单，就不一一实现了
//共享栈是为了更有效的利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满的时候才发生上溢
//栈的链式表示
//采用的是没有头节点的单链表

define bool int

define true 1

define false 0

typedef int ElemType;
//定义无头节点的链表数据结构
typedef struct LinkNode{
//定义每个节点的数据项
ElemType data;
//定义next指针
struct LinkNode *next;
}LinkNode, *LinkStack;
//指针变量可以在函数之间传递引用，从而修改原有的结构
LinkStack initLiStack(int value){
//初始化链表栈,只需要创建第一个节点，初始化值，返回一个节点的地址
LinkStack s;
s = (LinkStack)malloc(sizeof(LinkNode));
s -> data = value;
s -> next = NULL;
return s;
}
//查询栈有多少元素
int lengthLiStack(LinkStack S){
//只要初始化了，至少有一个元素,但是如果是出栈将S出完了,S=NULL
if(S == NULL){
return 0;
}
LinkStack p = S;
int count = 0;
while(p){
p = p -> next;
count ++;
}
return count;
}
//入栈
LinkStack pushLiStack(LinkStack S,int value){
//头插法
//入栈，头插法插入,首先建立要插入的节点
LinkStack s;
s = (LinkStack)malloc(sizeof(LinkNode));
s -> data = value;
s -> next = S;
return s;
}
//出栈,返回出栈的元素
LinkStack popLiStack(LinkStack S,ElemType *x){
//判断栈中是否已经为空
if (lengthLiStack(S) == 0){
return false;
}
//出栈
LinkStack p = S;
S = p -> next;
*x = p -> data;
p -> next = NULL;
free(p);
return S;
}
//读取栈顶元素
bool getTopLiStack(LinkStack S,ElemType *x){
//首先判断是否为空
if(lengthLiStack(S) == 0){
return false;
}
//读取栈顶元素
*x = S -> data;
return true;
}
//销毁整个栈
LinkStack clearLiStack(LinkStack S){
//逐一的free掉node
while(S){
LinkStack p = S;
S = p -> next;
free(p);
}
return S;
}
//打印出整个栈
void printLiStack(LinkStack S){
if(lengthLiStack(S) == 0){
printf("empty stack!\n");
return;
}
LinkStack p = S;
int value;
printf("top");
while(p){
value = p -> data;
printf("-> %d",value);
p = p -> next;
}
printf("\n");
}
int main(){
LinkStack S;
S = initLiStack(4);
int length = lengthLiStack(S);
printf("length of the stack is %d\n",length);
//入栈
for(int i=0;i<10;i++){
S = pushLiStack(S, i);
}
printLiStack(S);
//出栈
int x;
S = popLiStack(S, &x);
printf("the element poped is %d\n",x);
printLiStack(S);
int length2 = lengthLiStack(S);
printf("length of the stack is %d\n",length2);
//获取栈顶元素
int ele;
getTopLiStack(S, &ele);
printf("the top element is %d\n",ele);
//销毁整个栈
S = clearLiStack(S);
printLiStack(S);
int length3 = lengthLiStack(S);
printf("length of the stack is %d\n",length3);
}```

Tips:

1. 排除一切不可能的事，剩下的即使再不可能，它也是真相。
2. 线性结构是一对一的结构，非线性结构是一对多的结构。
3. 卡特兰数公式。
4. 入栈，出栈，入栈，按照一定顺序入栈，但是出栈可以在任何时候发生，所以出栈顺序是不一定的。
5. 第n个元素先出栈，说明前面的元素已经按顺序入栈了，所以前面元素的出栈顺序肯定是逆序的。
6. 共享栈中存取栈中元素都只需要O(1)的时间，所以没有减小存取时间，而且共享栈只可能发生上溢。