3.1 栈

栈

注：每定义一种新的数据结构，都应该从逻辑结构，存储结构和运算三个方面入手。

栈是只允许在一端进行插入或删除操作的-线性表。

栈顶TOP：允许进出的一端

栈底Bottom。空栈：不含任何元素的空表。

栈的操作：后进先出（LIFO）

栈的一个数学性质：n个不同元素入栈时，出站元素不同排列的个数为$$
\frac{1}{n+1} C_{2n}^{n}
$$​

栈的操作

初始化一个空栈S InitStack(&S)

判断一个栈是否为空 StackEmpty(S)

入栈 Push(&S,x) 若栈S未满，则将x加入使之成为新栈顶。

出栈 Pop(&S,&x) 若栈S非空，则弹出栈顶元素，并用x返回。

读栈顶元素 GetTop（S,&x) 读栈顶元素，但不出栈，若栈S非空，则用x返回栈顶元素。

销毁栈 DestroyStack(&S) 销毁栈，并释放栈S占用的存储空间

栈的顺序存储结构

1.顺序栈的实现

1
2
3
4
5
6
//栈的顺序存储类型可描述为：
#define MaxSize 50;	//定义栈中元素的最大个数
typedef struct{
    Elemtype data{MaxSize};	//存放栈中元素
    int top;	//栈顶指针
}SqStack;

栈顶指针：S.top，初始设置为S.top=-1 栈顶元素：S.data[S.top]

入栈操作：栈不满时，栈顶指针先+1，再送值到栈顶。

出栈操作：栈非空时，先取栈顶元素，再将栈顶指针-1。

栈空条件：S.top == -1 栈满条件S.top == MaxSize-1

image-20260812162236903

另一种表达方式：初始栈顶指针S.top=0；入栈先送值到栈顶，栈顶指针再+1；出栈栈顶指针-1，再弹出栈顶元素；栈空条件是S.top==0；栈满条件是S.top = MaxSize

2.顺序栈的基本操作

初始化

1
2
3
void InitStack(SqStack &S){
    S.top = -1;
}

判栈空

1
2
3
4
5
6
bool StackEmpty(SqStack S){
    if(S.top = -1)
        return true;
    else
        return false;
}

入栈

1
2
3
4
5
6
bool Push(SqStack &S,ElemType x){
    if(S.top = MaxSize-1)
        return false;
    S.data[++S.top] = x;
    return true;
}

出栈

1
2
3
4
5
6
bool Pop(SqStack &S,ElemType &x){
    if(S.top = -1)
        return false;
    x  = S.data[S.top--];
    return true;
}

读栈顶元素

1
2
3
4
5
6
bool GetTop(SqStack S,ElemType &x){
    if(S.top = -1)
        return false;
    x=S.data[S.top];
    return true;
}

如果top指的是栈顶元素的下一位置（而非上面的栈顶元素），则入栈操作改为S.data[S.top++]=x；出栈操作改为x=data[–S.top]

3.共享栈

（因为栈底位置相对不变），可以让两个栈共享一个一维数组空间，两个栈顶向共享空间的中间延伸。

top0=-1时0号栈为空，top1=MaxSize时1号栈为空；

仅当两个栈顶指针相邻（top1-top0=1）时，判断为栈满。

当0号栈入栈时top0先加1再赋值，1号栈入栈时top1先减1再赋值；出栈时相反。

存取时间O(1)

c224caf33a501e5fc3a2886c1cb7ed4f

栈的链式存储结构

优点：便于多个栈共享存储空间并提高效率。且不存在栈满上溢的情况。

通常用单链表实现。规定：链栈没有头节点，Lhead指向栈顶元素。

image-20260812193959640

1
2
3
4
5
//栈的链式存储类型可描述为：
typedef struct Linknode{
    ElemType data;	//数据域
    struct Linknode *next;	//指针域
}LiStack	//栈类型定义

3.2 队列

队列

Queue，是一种操作受限的线性表，只允许在表的一段进行插入，而在另一端进行删除。

操作特点是先进先出（FIFO）

队头(Front)，也称队首。 队尾(Rear) 空队列：不含任何元素的空表。

队列基本操作

初始化队列 InitQueue(&Q) 构造一个空队列Q

判队列为空 QueueEmpty(Q)

入队 EnQueue(&Q,x) 若队列未满，将x加入，使之成为新的队尾。

出队 DeQueue(&Q,&x) 若队列非空，删除队首元素，并用x返回。

读队首元素 GetHead(Q,&x) 读队首元素，若队列非空，则将队首元素赋值给x。

队列的顺序存储结构

1.队列的顺序存储

两个指针，队首指针front指向队首元素，队尾指针rear指向队尾元素的下一个位置。（不同教材有所不同）

1
2
3
4
5
6
//队列的顺序存储类型可描述为：
#define MaxSize 50;
typedef struct{
    ElemType data[MaxSize];	//用数组存放队列元素。
    int front,rear;	//队首指针和队尾指针。
}SqQueue;

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

入队操作：队不满时，先送值到队尾元素，再将队尾指针加1。

出队操作：队不空时，先取队首元素值，再将队首指针加1。

判空条件：Q.front == Q.rear == 0 成立

队满：（此时是假溢出）

image-20260812195331789

2.循环队列

9e9fda3498d4848bbf5aed16fc752b70

当队首指针Q.front = MaxSize-1后，再前进 一个位置就自动到0（可以用除法取模运算%实现）

初始时：Q.front = 0，Q.rear = 0

队首指针进1：Q.front = (Q.front+1) % MaxSize

队尾指针进1：Q.rear = (Q.rear+1) % MaxSize

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

出入队时：指针都按顺时针方向进1。

判断队空还是队满：三种方式

①入队时少用一个队列单元(0处)，以队首指针在队尾指针的下一个位置作为队满的标志。

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

②类型中增设size数据成员，表示元素个数。

  • 队满：Q.size == MaxSize
  • 队空：Q.size == 0

③类型中增设tag数据成员，来区分队满还是队空。

  • 队满：插入成功置tag=1，若导致Q.front = Q.rear，则队满
  • 队空：删除成功置tag=0，若导致Q.front = Q.rear，则队空

3.循环队列的操作

初始化

1
2
3
void InitQueue(SqQueue,&Q){
    Q.rear = Q.front = 0;
}

判队空

1
2
3
4
5
6
bool isEmpty(SqQueue Q){
    if(Q.rear==Q.front)
        return true;
    else
        return false;
}

入队

1
2
3
4
5
6
7
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;	//队尾指针加1取模
    return true;
}

出队

1
bool DeQueue(SqQueue)