栈
只允许在一端进行插入或删除操作的线性表。
一,栈的基本操作介绍
- InitStack(&S):初始化栈。构造一个空栈S,分配内存空间。
- DestroyStack(&L):销毁栈。销毁并释放栈S 所占用的内存空间。
- Push(&S,x):进栈,若栈S 未满,则将x 加入使之称为新栈顶。
- Pop(&S,&x):出栈,若栈非空,则弹出栈顶元素,并用x 返回。
- GetTop(S,&x):读栈顶元素,若栈S 非空,则用x 返回栈顶元素。
二,栈的顺序存储实现
1,顺序栈的定义
见如下代码片段,体会顺序栈的定义:
#define MaxSize 10
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
} SqStack;
void testStack(){
SqStack S; //声明一个顺序栈(分配空间)
//.....
}
2,初始化操作
//初始化栈
void InitStack(SqStack &S){
S.top=-1; //初始化栈顶指针
}
//我们也可以知道如何判断栈空
bool StackEmpty(SqStack S){
if(S.top==-1) //栈空
return true;
else
return false;
}
3,进栈操作
//新元素入栈
bool Push(SqStack &S,ElemType x){
if(S.top==MaxSize-1) //栈满,报错
return false;
S.data[++S.top]=x; //指针先加1,新元素入栈
return true;
}
4,出栈操作
在栈顶弹出一个元素,并用x 返回:
bool Pop(SqStack &S,ElemType &x){
if(S.top==-1) //栈空,报错
return false;
x=S.data[S.top]; //栈顶元素先出栈(注意一下和指针变化的先后顺序)
S.top=S.top-1; //指针再减1
return true;
}
三,栈的链式存储实现
采用链式存储的栈称为链栈,其优点是便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况。通常采用单链表实现,并规定所有的操作都是在单链表的表头进行的。
现在再想一想,是不是在单链表中,表头后插入一个结点就相当于元素入栈的操作,在表头后删除一个元素就相当于元素出栈。只不过入栈和出栈的操作都是在链表的表头进行的。
队列
一,队列的定义
前面我们知道了栈是只允许在一端进行插入或删除操作的线性表,那队列呢?
队列是只允许在一端进行插入,在另一端删除的线性表。这个结合日常生活中的排队来想,是不是非常简单~
以下是队列的几种基本操作:
- InitQueue(&Q):初始化队列,构造一个空队列Q。
- DestroyQueue(&Q):销毁队列。销毁并释放队列Q 所占用的内存空间
- EnQueue(&Q,x):入队,若队列Q 未满,将x 加入,使之成为新的队尾。
- DeQueue(&Q,&x):出队,若队列Q 非空,删除队头元素,并用x 返回。
二,队列的顺序实现
1,初始化操作
#define MaxSize 10 //定义队列中元素的最大个数
typedef struct {
ElemType data[MaxSize]; //用静态数组存放队列元素
int front,rear; //队头指针和队尾指针
}SqQueue;
//初始化队列
void InitQueue(SqQueue &Q){
//初始时,队头队尾指针指向0
Q.rear=Q.front=0;
}
//判断队列是否为空,就是头,尾指针指向同一个元素
bool QueueEmpty(SqQueue Q){
if(Q.rear==Q.front) //队空的条件
return true;
else
return false;
}
2,入队操作
//入队
bool EnQueue(SqQueue &Q,ElemType x){
if(队列已满)
return false; //队满则报错
Q.data[Q.rear]=x; //新元素插入队尾
Q.rear=(Q.rear+1)%MaxSzie //队尾指针加1取模
}
上述程序中的判断队列是否已满的操作我们后面再说,这里的模运算操作其实就是将无限的整数域映射到有限的整数集合{0,1,2,.....,MaxSize-1} 上,将存储空间在逻辑上变成了“环状”。
结合循环队列,我们可以知道,队列已满的条件:队尾指针的再下一个位置是对头,即 (Q.rear+1)%MaxSize==Q.front)
3,出队操作
只能让队头元素出队。删除一个队头元素,并用x 返回
bool DeQueue(SqQueue &Q,ElemType &x){
if(Q.rear==Q.front) //判断队空
return false;
x=Q.data[Q.front];
Q.front=(Q.front+1)%MaxSize; //队头指针后移
return true;
}
那如何知道队列元素的个数呢?这里有一个公式,希望我们记住:(rear+MaxSize-front)%MaxSize ,自己可以验证一下这个公式的合法性。
三,队列的链式实现
1,队列的链式实现
代码如下:
typedef struct LinkNode{ //链式队列结点
Elemtype data;
struct LinkNode *next;
}LinkNode;
typedef struct{ //链式队列
LinkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;
初始化队列(带头结点)的实现:
void InitQueue(LinkQueue &Q){
//初始时 front、rear都指向头结点
Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
Q.front->next=NULL;
}
void testLinkQueue(){
LinkQueue Q; //声明一个队列
InitQueue(Q); //初始化队列
//... 后续操作...
}
示意图如下:
由此可知,判断一个队列是否为空的代码实现如下:
bool IsEmpty(LinkQueue Q){
if(Q.front==Q.rear)
return true;
else
return false;
}
不带头结点的队列初始化:
void InitQueue(LinkQueue &Q){
//初始时,front、rear 都指向NULL
Q.front=NULL;
Q.rear=NULL;
}
//此时判断队列是否为空即队头指针为NULL
bool IsEmpty(LinkQueue Q){
if(Q.front==NULL)
return true;
else
return false;
}
2,入队
带头结点 的新元素入队操作只需要记得只能从队尾添加元素即可,逻辑也比较简单,直接见如下代码片段:
void EnQueue(LinkQueue &Q,ElemType x){
LinkNode *s=(LinkNode *)mallloc(sizeof(LinkNode));
s->data=x;
s->next=NULL;
Q.rear->next=s; //新结点插入到rear 之后
Q.rear=s; //修改表尾指针
}
不带头结点 新元素入队,由于开始front、rear 指针都是指向 NULL 的,所以需要对其进行修改操作:
void EnQueue(LinkQueue &Q,ElemType x){
LinkNode *s=(LinkNode *)mallloc(sizeof(LinkNode));
s->data=x;
s->next=NULL;
if(Q.front==NULL){ //在空队列中插入第一个元素,需要特殊处理
Q.front=s; //修改队头队尾指针
Q.rear=s;
}else{
Q.rear->next=s; //新结点插入到 rear 结点之后
Q.rear=s; //修改 rear 指针
}
}
3,出队
带头结点队头元素出队操作,逻辑比较简单,直接见代码:
bool DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front==Q.rear)
return false; //空队
LinkNode *p=Q.front->next;
x=p->data; //用变量x 返回队头元素
Q.front->next=p->next; //修改头结点的next 指针
if(Q.rear==p) //此次是最后一个结点出队
Q.rear=Q.front; //修改rear 指针
free(p); //释放结点空间
return true;
}
不带头结点 队头元素出队,代码如下:
bool DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front==NULL)
return false; //空队
LinkNode *p=Q.front; //p指向此次出队的结点
x=p->data; //用变量x 返回队头元素
Q.front=p->next; //修改front 指针
if(Q.rear==p){ //此次是最后一个结点出队
Q.front=NULL; //front指向NULL
Q.rear=NULL; //rear指向NULL
}
free(p);
return true;
}
最后,我们一定要多动手、勤思考,这样我们才有可能攻陷数据结构!