数据结构与算法复习（3）栈、数组和队列

发表于 2022-08-03 分类于 Algorithm ， 408

前言

本章介绍三种逻辑结构，栈和队列都是操作受限的线性表，而数组则是线性表的推广。栈和队列的操作以及特征是重点，而且要掌握特殊形式和常见应用方式。

栈

首先栈是一种线性表，但只允许在一端进行插入和删除，即栈是插入删除等操作受限的线性表（逻辑结构）。

概念

栈顶，线性表允许进行插入删除的一端；
栈底，不允许进行插入和删除的一端；
空栈，不含任何元素的空表；
特点：后进先出（LIFO）；

顺序存储

顺序栈

采用顺序存储的栈称为顺序栈，用一组地址连续的存储单元存放元素，同时用一个指针保存当前栈顶元素的位置。

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

栈空：top==-1；
栈满：top==MaxSize-1；
栈长：top+1；
栈顶元素：S.data[S.top];

基本操作

//栈初始化
void InitStack(SqStack &S)
{
    S.top = -1;
}

//判栈空
bool StackEmpty(SqStack &S)
{
    if(S.top == -1)
        return true;
    else
        return false;
}
//判栈满操作相似

//进栈
bool Push(SqStack &S, ElemType x)
{
    if(S.top == MaxSize - 1)
    {
        return false;
    }
    S.top++;
    S.data[S.top] = x;
    return true;
}

//出栈
bool Pop(SqStack &S, ElemType &x)
{
    if(S.top == -1)
        return false;
    X = S.data[S.top];
    S.top--;
    return true;
}

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

共享栈

将两个栈共享在同一个数组空间，栈底设置在两端，两个栈向中间延伸。

链式存储

采用链式存储的栈叫链栈，优点是便于多个栈共享存储空间和提高效率，不存在栈满上溢的情况。

一般用单链表实现，头结点同样会有影响。

trpedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}*LinkStack;

队列

也是一种操作受限的线性表，只允许在表的一端插入，另一端删除，特点是先进先出（FIFO）。

概念

队头，允许删除的一端；
队尾，允许插入的一端；
空队列，不含任何元素的空表。

顺序存储

普通顺序存储

分配一块连续的存储单元存放队列元素，同时用队头指针指向队头元素，队尾指针指向队尾元素。

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

//初始化
bool InitQueue(SqQueue &Q)
{
    Q.front = 0;
    Q.rear = 0;
}

但是由于顺序队列有一个缺点，在计算过程中会发生假上溢：

此时判空可以通过队首队尾指针是否相同判断，但是要判满就不能实现了，所以要用循环队列的方式克服。

循环队列

将队列想象成环状的空间，当队首计算到MaxSize-1时，再出队则队首变为0，用取余运算实现。
初始：Q.front=0;Q.rear=0;
队首指针进一：Q.front=(Q.front+1)%MaxSize;
队尾指针进一：Q.rear=(Q.rear+1)%MaxSiae;
队列长度：(Q.rear + MaxSize - Q.front) % MaxSize;

判空判满：需要单独处理。

1）牺牲一个单元来区分，约定当队头在队尾的下一位置时队满，此时
队满：(Q.rear + 1)%MaxSize == Q.front;
队空：Q.front == Q.rear;
2)增加一个表示元素个数的数据成员，用来保存个数判断；
3）增加tag数据成员，tag=0，若因为删除导致Q.front == Q.rear，则是队空；tag=1，如果因为插入导致Q.front == Q.rear，则为队满。

//判空
bool isEmpty(SqQueue Q)
{
    if(Q.rear == Q.front)
        return true;
    return false;
}

//入队
bool 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;
}

//出队
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;
}

链式存储

队列的链式存储叫做链队列，实际上就是同时有头指针和尾指针的单链表。

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front, *rear;
}LinkQueue;

//初始化
void InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}

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

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

//出队
bool DeQueue(LinkQueue &Q, ElemType &x)
{
    if(Q.front == Q.rear)
        return false;
    LinkNode *p = Q.front->next;
    x = p->next;
    Q.front->next = p->next;
    if(Q.rear == p)
    {
        Q.rear=Q.front;
    }
    free(p);
    return true;
}