数据结构-栈和队列

栈

栈的顺序存储结构

特点：利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附加一个指针(top)指示当前栈顶的位置

0.顺序栈的类型描述

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

1.初始化操作

目标：初始化一个空的顺序栈

Void InitStack(SqStack &stack){
    stack.top=-1;//初始化栈顶指针
}

2.判空操作

目标：判断当前栈是否为空栈，若是返回TRUE,否则返回FALSE

int StackEmpty(SqStack stack){
    if(stack.top==-1)//栈空
        return TRUE;
    else
        return FALSE;
}

3.进栈操作

目标：向顺序栈中插入一个元素

int Push(SqStatck &stack,ElemType x){
    if(stack.top)==MaxSize-1)//栈满，报错
        retrun FALSE;
    stack.data[++stack.top]=x//指针先加1再入栈
        return TRUE;
}

WARNING

当初始化时stack.top=0;此时入栈代码变为stack.data[stack.top++]=x; 此时栈判空代码变为if(stack.top==0)

此时栈判满代码变为if(stack.top==MaxSize)

4.出栈操作

目标：从顺序栈中弹出一个元素

int Pop(SqStack &stack,ElemType &x){
    if(stack.top==-1)//栈空
        return FALSE;
    x=stack.data[stack.top--];//先出栈指针再减1
    return TRUE;
}

WARNING

当初始化时stack.top=0;此时出栈代码变为x=stack.data[--stack.top];

5.读栈顶元素

目标：当前顺序栈中栈顶的元素，并用引用变量x返回

int GetTop(SqStack stack,ElemType &x){
    if(stack.top=-1)//栈空
        return FALSE;
    x=stack.data[stack.top];//x记录栈顶元素
    return TRUE;
}

WARNING

当初始化时stack.top=0;此时读栈顶元素代码变为x=stack.data[stack.top-1];

共享栈

定义：利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置共享空间的两端，两个栈顶向共享空间的中间延伸

0号栈判空：top0==-1

1号栈判空：top1==MaxSize

栈满：top1-top0==1

0号栈进栈 top0先加一再赋值

1号栈进制top1先减一再赋值

0号栈出栈先取值再top0减一

1号栈出栈先取值再top1加一

优点：更有效的利用存储空间，两个栈空间相互调节只有整个存储空间被占满才发生上溢

栈的链式存储

特点：使用线性表的链式存储即单链表表示栈

0.链式栈的类型描述

typedef struct StackNode{
    ElemType data;
    struct StackNode *next;
}StackNode,*LinkStack;

队列

定义：只允许在一端进行插入操作，而在另一端进行删除操作的线性表

• 队头：线性表只允许删除的那一端
• 队尾：只允许进行插入的那一端
• 空队列：不含任何元素的空表

注意：

1. 队列本质是线性表，是操作受限的线性表
2. 线性表可以有空表，队列也有空队列
3. 插入：入队、出队
4. 删除：出队
5. 队列的操作特性：先进先出(FIFO)

队列的顺序存储

特点：分配一块连续的存储单元存放队列中的元素，并附设两个指针front与rear分别指示队头元素和队尾元素的位置

0.顺序队列的类型描述

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
}SqQueue;

• 初始状态：Q.front==Q.rear==0
• 进队操作：队不满时，先赋值再Q.rear++;
• 出队操作：队不空时，先取值再Q.front++;

循环队列

把顺序队列从逻辑上看成一个环，成为循环队列

• 初始时：Q.rear=Q.front=0；

• 入队时：Q.rear=(Q.rear+1)%MaxSize

• 出队时：Q.front=(Q.front+1)%MaxSize

• 队列长度：(Q.rear-Q.front+MaxSize)%MaxSize

• 判空：if(Q.rear==Q.front)

• 判满：if(Q.rear==Q.front)

  • 判空和判满重复！！改进：

    • 牺牲一个存储单元来区分队空还是队满

      队空：Q.front==Q.rear

      队满： (Q.rear+1)%MaxSize==Q.front

      队中元素个数： (Q.rear-Q.front+MaxSize)%MaxSize

    • 增设一个记录当前数据元素的变量Q.size

      队空：Q.size==0

      队满：Q.size==MaxSize

      队中元素个数：Q.size

    • 增设tag变量，记录最后一次操作是插入还是删除

      tag=0，表示最后一次操作是删除

      tag=1，表示最后一次操作是插入

      队空：if(Q.front==Q.rear&&tag==0)

      队满：if(Q.front==Q.rear&&tag==1)

      队中元素个数： (Q.rear-Q.front+MaxSize)%MaxSize

1.初始化

目标：初始化一个循环队列

void InitQueue(SqQueue &Q){
    Q.rear=Q.front=0;//初始化队首、队尾指针
}

2.判队空

目标：判断给定队列是否为空，若空返回TRUE,否则返回FALSE

int QueueEmpty(SqQueue Q){
    if(Q.rear==Q.front)//队空条件(使用方法一改进循环队列)
        return TRUE;
    else
        return FALSE;
}

3.入队

目标：向循环队列入队一个元素，若入队失败返回FALSE，若入队成功返回TRUE

#define TURE 1
#define FALSE 0
int EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front)//队满(使用方法一改进循环队列)
        return FALSE;
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;//后移循环队列队尾指针
    return TRUE;
}

4.出队

目标：从循环队列出队一个元素，若出队失败返回FALSE，若出队成功返回TRUE，并引用变量x返回出队元素

#define TURE 1
#define FALSE 0
int 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;
}

队列的链式存储

特点：使用链表来表示队列

0.链式队列的类型描述

typedef struct QNode{
    ElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

• 链队列本质是一个同时带队头指针和队尾指针的单链表
• 判空：if(Q.front==Q.rear)

1.初始化

目标：初始化一个带头结点的链式队列

void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(QNode *)malloc(sizeof(QNode));
    Q.front->next=NUll;
}

2.判队空

目标：判断队列是否为空，若空返回TRUE，否则返回FALSE

int QueueEmpty(LinkQueue Q){
    if(Q.front==Q.rear)
        return TRUE;
    else
        return FALSE;
}

3.入队

目标：向链式队列中入队一个元素x

void EnQueue(LinkQueue &Q,ElemType x){
    s=(QNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}

4.出队

目标：从链式队列中出队一个元素，若出队失败返回FALSE，成功返回TRUE，并用引用变量x保持出队元素

int DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==Q.rear)
        return FALSE;
    p=Q.front->next;
    x=p->data;//保存出队元素
    Q.front->next=p->next;//修改头结点指针
    if(Q.rear=P)//额外处理仅有一个元素时的Q.rear指针
        Q.rear=Q.front;
    free(p);//释放已出队结点
    return TRUE;
}

双端队列

特点：允许两端都进行入队和出队操作的队列，元素的逻辑结果仍是线性结构

• 输出受限的双端队列

  • 允许在一端进行插入删除，但在另一端只能插入的双端队列

• 输入受限的双端队列

  • 允许在一端进行插入删除，但在另一端只能删除的双端队列

END