记得大一的时候自学数据结构，那时候却没有深入的去研究代码，只是了解了个表面的东西，不过还好有基础，并且去年的时候看了算法一书，Java实现，算是深入研究了下算法，现在再看数据结构与算法也比较熟悉了。
对于数据结构，我觉得主要第一个是理解这种数据结构的特点，然后就是用代码实现，然后尝试将这种数据结构进行应用。
另外研究数据结构，要从逻辑结构，存储结构和操作进行。
- 栈
允许在一端进行插入或者删除的线性表。
栈的明显操作特性是后进先出。
基本操作无非是初始化，出栈，入栈，读栈顶元素，判断是否为空，销毁栈，这些操作在下面都会得以实现，使用C语言。 - 栈的顺序存储结构
顺序栈，使用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时设指针指示当前栈顶位置。
注意入栈出栈的时候的数组引用角标的变化，是++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:
- 排除一切不可能的事，剩下的即使再不可能，它也是真相。
- 线性结构是一对一的结构，非线性结构是一对多的结构。
- 卡特兰数公式。
- 入栈，出栈，入栈，按照一定顺序入栈，但是出栈可以在任何时候发生，所以出栈顺序是不一定的。
- 第n个元素先出栈，说明前面的元素已经按顺序入栈了，所以前面元素的出栈顺序肯定是逆序的。
- 共享栈中存取栈中元素都只需要O(1)的时间，所以没有减小存取时间，而且共享栈只可能发生上溢。
