一.栈（Stack）基本概念

• 定义——“逻辑结构”
• 基本操作——“运算”
  数据结构三要素——逻辑结构，数据的运算，存储结构（物理结构）存储结构不同，运算的实现方式也不同
  栈是仅允许在一端进行插入或删除操作的线性表

插入和删除和线性表有区别

1.栈的基本操作

2.栈的常考题型

所以有42种

二.顺序栈的实现

1.顺序栈的定义

和顺序表类似

#define MaxSize 10
typedef struct{ElemType data[MaxSize];//静态数组存放栈中元素int top;//栈顶指针
}SqStack;

void testStack(){SqStack S;//声明一个顺序栈......
}

顺序存储，给各个数据元素分配连续的存储空间，大小为：MaxSize*sizeof(ElemType)

//初始化
void InitStack(SqStack &s){S.top=-1;//初始化栈顶指针
}
void test Stack（）{SqStack S;//声明一个顺序栈（分配空间）InitStack(S);
}
//判断栈空
bool StackEmpty(SqStack S){if(S.top==-1)//栈空return true;elsereturn false;
}

2.增（进栈操作）

bool Push(SqStack &s,ElemType x){if(S.top==MaxSize-1)//栈满，报错return false;S.top=S.top+1;//指针先加一S.data[S.top]=x;//新元素入栈return true;
}

3.删（出栈操作）

bool Pop(SqStack &s,ElemType &x)
{if(S.top==-1)//栈空，报错return false;x=S.data(S.top);//栈顶元素先出栈S.top=S.top-1;//指针再-1return true;
}

读栈操作

bool GetTop(SqStack S,ElemTy0pe &x){if(S.top==-1)return false;x=S.data[S.top];//x记录栈顶元素return true;
}

注意审题top指针到底指那个位置

4.共享栈（两个栈共享同一片空间）

typedef struct{ElemType data[MaxSize];int top0;int top1;
}ShStack;
void InitStack(ShStack &S){S.top0=-1;S.top1=MaxSize;
}

栈满条件：top0+1==top+1

三.链栈的实现

• 用链式存储方式实现的栈
• 基本操作（增，删等）

1.头插法建立单链表->对应：进栈

//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){if(p==NULL)return false;LNode* s=(LNode *)malloc(sizeof(LNode));if(s==NULL)//内存分配失败return false;s->data=e;//用结点s保存数据元素es->next=p->next;p->next=s;//将结点s连接在p之后return true;
}

头插法建立单链表：
初始化单链表
while 循环
{
每次取一个数据元素e；
InsertNextNode（L，e）；
}

2.单链表删除操作（出栈）

链头=栈顶
链栈的定义

typedef struct Linknode{ElemType data;//数据域struct Linknode * next;//指针域
}*Listack;//栈类型定义

四.队列（Queue）

• 定义
• 基本操作
  存储结构不同，运算方式也不同
  队列：只允许在一端插入（入队），另一端删除（出队）的线性表
  
  先进先出

1. 队头：
2. 队尾
3. 空队列：队列中无任何数据元素
4. FIFO
   
   

#define MaxSize 10typedef struct data[MaxSize];//静态数组存放队列元素int front,rear;//队头和队尾指针
}SqQueue;

//变量声明
vid testQueue(){SqQueue Q;
}

//初始化队列
void InitQueue(SqQueue &Q){//初始时，队头队尾指针指向0Q.rear=Q.front=0;
}
void testQueue(){SqQueue Q;InitQueue(Q);
}
//判断队头队尾是否为空
bool QueueEmpty(SqQueue Q){if(Q.rear==Q.front)//队空return true;elsereturn false;
}

1.入队操作

//从队尾入队
bool Insert(SqQueue &Q,ElemType x)
{if((Q.rear)+1%MaxSize==Q.front)return false;Q.data[Q.rear]=x;//x插到队尾Q.rear=（Q.rear+1）%MaxSize;///环状return true;
}

2.循环队列

用模运算将存储空间在逻辑上变成“环状”

3.循环队列（出队操作）

//出队：删除一个队头元素，用x返回
bool DeQueeu(SqQueue &Q,ElemType &x)
{if(q.rear==Q.front)return false;//队空x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;return true;
}

//查,获得头元素的值，用x返回
bool GetHead (SqQueue Q,ElemType &x){if(Q.rear==Q.front)return false;x=Q.data[Q.front];return true;
}

方案一：判断队列已满/已空
队列元素个数：(rear +MaxSize -front)%MaxSize;

方案二：判断队列已满/已空

#define MaxSize 10
typedef struct{Elemtype data[MaxSize];int front,rear;int size;//队列当前长度，插入：size++，删除：size--.初始化时rear=front=0;size=0;
}SqQueue;

方案三：判断队列已满/已空

#define MaxSize 10
typedef struct{ElemType data[MaxSize];int rear,front;int tag;//最近进行的是删除/插入
}SqQueue; 

删除：tag=0
插入：tag=1
只有删除才可能导致队空
只有插入操作才有可能导致队满
队满：front == rear && tag ==1

队空：front == rear && tag ==0

4.队列的链式实现

typedef struct LinkNode{//链式队列节点ELemType data;struct LinkNode *next;
}LinkNode;typedef struct{//链式队列LinkNode *front,*rear;//队列的队头指针和队尾指针
}LinkQueue;

链式存储实现的队列：链队列

typedef struct LinkNode{ElemType data;struct LinkNode *next;
}LinkNode;typedef struct{	LinkNode *front,*rear;
}LinkQueue;//初始化带头结点
void InitQueue(LinkQueue &L){//初始时，rear和front都指向头结点L.rear=L.front=(LinkNode*)malloc(sizeof(LinkNode));L.front->next=NULL;
}void testLinkNode(){LinkQueue Q;InitQueue(Q);
}

//判断队列是否为空
bool IsEmpty(){if(L.rear==L.front)return true;elsereturn false;
}

//初始化不带头结点
bool InitQueue(LinkQueue &L){L.rear=NULL;L.front=NULL;
}

//入队，插入节点（带头结点）
bool InsertQueue(LinkQueue &L,ElemType e){LinkNode*s=(LinkNode*)malloc(sizeof(LinkNode));s->data=e;s->next=NULL;L->rear->next=s;//新节点插入到rear之后L.rear=s;//修改表尾指针
}

//入队，不带头结点
bool InsertQueue(LinkQueue &L,ElemType e){LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));s->data=e;s->next=NULL;if(L.front==NULL){//在空队列中插入第一个元素L.front=s;//修改队头队尾指针L.rear=s;}else{L.rear->next=s;//新节点插入到rear之后L.rear=s;//修改rear指针}
}

//出队，带头结点
bool DeleteQueue(LinkQueue &L,ElemType &e)
{if(L.rear==L.front)return false;LinkNode *p=L.front->next;e=p->data;//用e返回队头元素L.front->next=p->next;//修改头结点的next指针if(L.rear==p)//最后一个结点出队L.rear=L.front;//修改rear指针free(p);//释放节点空间return true;
}

//出队，不带头结点
bool DeleteQueue(LinkQueue &L,ELemType &e){if(L.front==NULL)return false;LinkNode*p=L.front;//p指向此次出队的节点e=p->data;//用e返回队头元素L.front=p->next;//修改front指针if(L.rear==p){L.front=NULL;L.rear=NULL;}free(p);return true;
}

可加int length判断长度

五.双端队列

如果双端队列指从一端插入和删除，则双端队列转化为栈

六.特殊矩阵的压缩存储

6.1一维数组的存储结构

ElemType a[10];//ElemType 型一维数组 ，C语言定义一维数组

• 各数组元素大小相同，且物理上连续存放
• 数组元素a[i]存放地址=LOC+i*sizeof(ElemType)(0<=i<10)
• 注：除题目特别说明，否则数组下标默认从0开始
  

6.2二维数组的存储结构

6.3普通矩阵的存储

压缩存储策略：只存储主对角线与上（下）三角区
用行优先原则存储到一维数组中

6.4三角矩阵的压缩存储

6.5三对角矩阵的压缩存储

6.6稀疏矩阵的压缩存储