数据结构（第三章）

栈

• 定义：只允许在一端进行插入或删除操作的线性表
• 特点：后进先出

顺序栈的表示与实现

• 顺序栈：利用顺序存储结构实现栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设top指示栈顶元素在顺序栈中的位置。

栈的顺序存储类型

#define Maxsize 50
typedef struct{
    ElemType data[MaxSize];
    int top;
}SqStack

栈的操作：使用不带头结点的单链表，只在头部进行插入和删除操作。

1. 栈顶指针：S.top
2. 栈空：S.top==-1
3. 栈满：S.top==MaxSize-1
4. 栈长：S.top+1

这里使用的初始值为S.top=-1若初始值为0的话，上面的结果将发生改变。

图片注解：

顺序栈的基本操作

1. 初始化

//初始化
bool  InitStack(SqStack &S){
    S.top=-1; // 初始化栈顶指针，初始化设置为-1
    return true;
}

2. 栈判空

//栈判空
bool SqStackEmpty(SqStack S){
    if (S.top==-1)
        return true; //栈空
    else
        return false;
}

3. 进栈操作

//进栈操作
bool Push(SqStack &S ,ElemType e){
    if (S.top==MaxSize-1)
        return false ; //栈满
    else
       S.data[++S.top]=e; //先让指针+1 ,然后将元素压入栈底
        return true;
}

4. 出栈操作

//出栈操作
bool Pop(SqStack &S , ElemType &e){
    if (S.top==-1)
        return false ; //栈空
    else
        e=S.data[S.top--]; //先让元素出栈，再让指针减1
    return true;
}

5. 获取栈顶元素

//获取栈顶元素
bool GetTop(SqStack S , ElemType &e){
    if (S.top==-1)
        return false;
    else
        e=S.data[S.top];
    return true;
}

共享栈

通过两个顺序栈，共享一个一维空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

图片注解：

判空条件：

• 0号栈判空：top0=-1
• 1号栈判空：top1=MaxSize

栈满条件判断：

• top1-top0=1

进栈操作：top0先加1，再将元素插入；top1则先减1，再将元素插入，出栈操作则相反。

栈的链式存储类型

栈的链式存储类型

typedef struct LinkNode {
    ElemType  data; //数据域
     struct LinkNode *next; //指针域
} *LiStack;

图解：

链栈的基本操作

以下操作皆是使用带有头结点的链栈进行操作的

1. 初始化

//初始化
bool InitLiStack(LiStack &L ){
    L=new LinkNode;
    L->next=NULL; //开辟一个头结点
    return true;
}

2. 判空操作

//判空操作
bool IsEmpty(LiStack L ){
    if (L->next==NULL)
        return true;
    else
        return false;
}

3. 进栈操作

//进栈操作
bool Push(LiStack &L ,ElemType e){
    LinkNode *p; //创建结点进行操作
    p=new LinkNode;
    p->next=NULL;
    p->data=e;
    p->next=L->next; //头插法进行操作
    L->next=p;
    return true;
}

4. 出栈操作

//出栈操作
bool Pop(LiStack &L ,ElemType &e){
    LinkNode *p;
    if (L->next==NULL)
        return false;
    else
    p=L->next;
    e=p->data;
    L->next=p->next; //将p的下一个地址，直接赋值给L的next
    free(p);//将该结点释放掉
    return true;
}

队列

• 定义：其本质也是一种受限制的线性表，只允许在表的一端进行插入另一端进行删除。在队列中插入元素称为入队，删除元素称为出队。
• 特点：先进先出

队列的表示和实现

队列的顺序存储

#define MaxSize 50
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize]; //数据域
    int front , rear;  //队头和队尾
}SqQueue;

• 初始状态：队头和队尾指向同一位置

Q.front==Q.rear==0;

• 队满状态：队头指向定义的空间的最大位置

Q.rear-Q.front==MaxSize; //普通队列

• 入队操作：先将值送到队尾，再将队尾指针加1，队头指针不动

Q.rear++;

• 出队操作：先将队头元素取出，再将队头指针加1，队尾指针不变

Q.fornt++;

上述的普通队列对于，空间的利用率存在着很大的弊端，因此引入了循环队列。

循环队列

定义：制造一个队头和队尾相连的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。

初始时：

Q.front==Q.rear;

队满：

(Q.rear+1)%MaxSize=Q.front;

队列长度：

(Q.rear-Q.front+MaxSize)%MaxSize;

循环队列的基本操作

1. 初始化操作

//队列初始化操作
bool InitQueue(SqQueue &Q){
    Q.front==Q.rear;
    return true;
}

2. 判空操作

//队列判空操作
bool IsEmpty(SqQueue Q){
    if (Q.front==Q.rear)
  return true;
    else
        return false;
}

3. 入队操作

//入队操作
bool EnQueue(SqQueue &Q, ElemType e){
    //判断队列是否已满
    if ((Q.rear+1)%MaxSize==Q.front)
        return false;
    else
        Q.data[Q.rear]=e;
    Q.rear=(Q.rear+1)%MaxSize;//队尾指针加1取模，保证可以循环进行
    return true;
}

4. 出队操作

//出队操作
bool DeQueue(SqQueue &Q ,ElemType &e){
    //队空判断
    if (Q.rear==Q.front)
        return false;
    else
        e=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

队列的链式存储

链式存储类型：

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

链式队列的基本操作

1. 初始化

//初始化
bool InitQueue(LinkQueue &Q){
    Q.front=new LinkNode;
    Q.rear=new LinkNode;
    Q.rear==Q.front;
    Q.front->next=NULL;
    return true;
}

2. 判空

//判空操作
bool IsEmpty(LinkQueue Q){
    if (Q.front==Q.rear)
        return true;
    else
        return false;
}

3. 入队

//入队操作
bool EnQueue(LinkQueue &Q , ElemType e){
    LinkNode  *p = new LinkNode ;
    p->data=e;
    p->next=NULL;
    Q.rear->next=p->next;
    Q.rear=p; //指针后移
  return true;
}

4. 出队

//出队操作
bool DeQueue(LinkQueue &Q , ElemType &e){
    if (Q.front==Q.rear)
        return false;
    LinkNode *p=Q.front->next;  //带有头结点
    e=p->data;
    Q.front->next=p->next;
    if (Q.rear==p)
        Q.front==Q.rear;
    free(p);
    return true;
}

上述使用的是带有头结点的链式存储结构，即队头指针为头结点。

双端队列

定义：双端队列是允许两端都可以进行入队和出队操作的队列，队列的两端称为前端和后端。

特点：两端都可以进行出队和入队