一、栈栈是只能一头增删的线性表,分为
[顺序栈]静态开辟,想要动态开辟栈选择链栈,[共享栈]为公用一块区域的两个顺序栈
[链栈]动态结点开辟.
#define MaxSize 10
typedef struct
{
ElemType data[MaxSize]; //静态数组 存放元素类型为ElemType
int top; //栈顶指针 表示为数组下标(不是位序)
}SqStack;
2.初始化
bool InitStack(SqStack &S)
{
S.top = -1; //元素入栈需要先令栈顶指针上移再给元素值,因而指向-1
return true;
}
3.判空
bool Empty(SqStack S)
{
return(S.top == -1);
}
4.入栈
bool Push(SqStack &S, ElemType e)
{
if(S.top == MaxSize - 1) //栈满,即栈顶指针指向data[MaxSize-1]
return false;
S.data[++S.top] = e; //先令栈顶指针上移,再对指针位置赋值
return true;
}
5.出栈
bool Pop(SqStack &S, ElemType &e)
{
if(Empty(S)) //空栈
return false;
e = S.data[S.top--]; //将栈顶指针的元素赋值给外部变量e,再下移栈顶指针
return true;
}
6.获取栈顶元素
ElmeType GetTop(SqStack S)
{
assert(Empty(S));
return S.data[S.top];
}
共享栈ShStack
两个栈共享同一栈区,0号栈从下至上添加元素,1号栈从上至下添加元素
#define MaxSize 10
typedef struct
{
ElemType data[MaxSize]; //静态数组 存放元素类型为ElemType
int top0; //0号栈栈顶指针
int top1; //1号栈栈顶指针
}ShStack;
2.初始化
bool InitStack(SqStack &S)
{
S.top0 = -1;
S.top1 = MaxSize;
return true;
}
3.判空
//0号栈判空
bool Empty0(SqStack S)
{
return(S.top0 == -1);
}
//1号栈判空
bool Empty1(SqStack S)
{
return(S.top1 = MaxSize);
}
4.入栈
//0号栈入栈
bool Push0(SqStack &S, ElemType e)
{
if(S.top0 == S.top1 - 1) //栈满,即两栈栈顶指针相邻
return false;
S.data[++S.top0] = e; //先令0号栈顶指针上移,再对指针位置赋值
return true;
}
//1号栈入栈
bool Push1(SqStack &S, ElemType e)
{
if(S.top0 == S.top1 - 1)
return false;
S.data[--S.top1] = e; //先令1号栈顶指针下移,再对指针位置赋值
return true;
}
5.出栈
//0号栈出栈
bool Pop0(SqStack &S, ElemType &e)
{
if(Empty0(S))
return false;
e = S.data[S.top0--];
return true;
}
//1号栈出栈
bool Pop1(SqStack &S, ElemType &e)
{
if(Empty1(S))
return false;
e = S.data[S.top1++];
return true;
}
链栈linkStack
链栈的本质是只能在表头进行增删的链表,一般使用无头结点方式
1.类型定义typedef struct
{
Elemtype data;
struct LNode* next;
}LNode,*linkStack;
二、队列
队列是一头增一头删的线性表,分为
[顺序队列]静态开辟
为了避免假溢出,可以在出队时整体向队头位置[平移],或将存储逻辑视为环形,构造[循环队列]
由于整体平移的时间复杂度过高,通常选取构造循环队列的方式,因此只讨论循环队列
[链队列]动态结点开辟
队列存在变种[双端队列]，即两侧都可以入队和出队(人为定义),常考察判断给定序列是否满足条件
循环队列 1.类型定义#define MaxSize 10
typedef struct //牺牲存储单元类型
{
ElemType data[MaxSize]; //静态数组 存放元素类型为ElemType
int front; //队头(出队)指针 指向当前队列的第一个元素的位置
int rear; //队尾(入队)指针 指向当前队列的最后一个元素之后的位置
}SqQueue;
2.初始化
bool InitQueue(SqQueue &Q)
{
Q.rear = Q.front = 0; //不同于栈,队列先赋值再上移
}
3.判空
bool Empty(SqQueue &Q)
{
return (Q.rear == Q.front) //牺牲存储单元类型
}
4.求队列长度
int Length(SqQueue Q)
{
return ((Q.rear - Q.front + MaxSize) % MaxSize);
}
5.入队
bool EnQueue(SqQueue &Q, ElemType e)
{
if((Q.rear + 1) % MaxSize == Q.front)
//队满,为了防止与队空混淆(d1),牺牲一个储存单元(d2)以便判断
return false;
Q.data[Q.rear] = e;
Q.rear = (Q.rear + 1) % MaxSize;
return true;
}
注:避免牺牲储存单元,可以用以下两种办法
1_在队列定义时加入int size类型,入队自增,出队自减,当Q.rear == Q.front时,
若size == 0,则队空
若size > 0,则队满
2_在队列定义时加入int tag类型,入队赋值1,出队赋值0,当Q.rear == Q.front时,
若tag == 0,则队空
若tag == 1,则队满
bool DeQueue(SqQueue &Q, ElemType &e)
{
if(Empty(Queue))
return false;
e = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
return true;
}
7.获取队头元素
bool GetHead(SqQueue Q, ElemType &e)
{
if(Q.rear == Q.front)
return false;
e = Q.data[Q.front];
return true;
}
链队列
1.类型定义
typedef struct LNode
{
ElemType data;
struct
}LNode;
typedef struct
{
LNode* front; //指向头结点或者首元素结点
LNode* rear; //指向尾结点
}linkQueue //链队列里包含两个结点指针
2.初始化
//不带头结点
bool InitQueue(linkQueue &Q)
{
Q.front = Q.rear = NULL;
return true;
}
//带头结点
bool InitQueue(linkQueue &Q)
{
Q.front = Q.rear = (LNode*)malloc(sizeof(LNode));
if(Q.front == NULL)
return false;
Q.front->next = NULL;
return true;
}
3.判空
//不带头结点
bool Empty(linkQueue Q)
{
return(Q.front == NULL);
}
//带头结点
bool Empty(linkQueue Q)
{
return(Q.front == Q.rear);
}
4.入队
//不带头结点
bool EnQueue(linkQueue &Q, ElemType e)
{
LNode* s = (LNode*)malloc(sizeof(LNode));
if(s = NULL)
return false;
s->data = e;
s->next = NULL;
if(Empty(Q)){ //若无头结点队列为空
Q.rear = Q.front = s;
} else {
Q.rear->next = s; //当前尾结点指向新结点
Q.rear = s; //调整新尾结点指针
}
return true;
}
//带头结点
bool EnQueue(linkQueue &Q, ElemType e)
{
LNode* s = (LNode*)malloc(sizeof(LNode));
if(s = NULL)
return false;
s->data = e;
s->next = NULL;
Q.rear->next = s;
Q.rear = s;
return true;
}
5.出队
//不带头结点
bool DeQueue(linkQueue &Q, ElemType &e)
{
if(Empty(Q))
return false;
LNode* p = Q.front; //p标记首结点
e = p->data;
Q.front =p->next;
if(Q.rear == p) //如果是最后一个结点
Q.rear = Q.front = NULL;
free(p);
return true;
}
//带头结点
bool EnQueue(linkQueue &Q, ElemType &e)
{
if(Empty(Q))
return false;
LNode* p = Q.front->next; //p标记头结点之后的结点
e = p->data;
Q.front->next = p->next;
if(Q.rear == p)
Q.rear = Q.front;
free(p);
return true;
}
