数据结构-线性表-限性表-栈-队列

栈

3.1栈

3.1.1栈的基本概念

栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构。

栈的存储方式

• 线性存储(顺序)
• 链接存储（链表）

栈的相关概念

• 栈顶和栈底：允许元素插入与删除的一段称为栈顶，另一端栈底
• 压栈：栈的插入操作，叫做进栈，也称压栈、入栈
• 弹栈：栈的删除操作，也叫作出栈

3.3.2栈的基本运算

3.1.2栈的顺序存储结构

3.3.3栈的运算算法

1.初始化栈

2.销毁栈

3.push进栈算法

4.pop出栈算法

int pop(sQsTACK & ST,ElemType x)
{
if(st.top==maxSizx-1)
{
return 0;
}else
{
x=st.data[st.topp];
st.top--;
return 1;
}


}

5.取栈顶元素

int Getpop(sQsTACK & ST,ElemType x)
{
if(st.top==maxSizx-1)
{
return 0;
}else
{
x=st.data[st.topp];
return 1;
}


}

6.判断栈空运算算法

3.1.3栈的链式存储结构

3.1.4栈链的运算算法

1.初始化栈算法

void InitStack(LinkStack * &ls)

{

ls=null;

}

2.销毁栈运算算法

void DestroyStack(LinkStack * &ls)

{
LinkStack *pre=ls,*P;
if(pre==null) return;//空栈
p=pre->next;//指向栈顶
while(p!=null)
{
free(pre)
pre=p;p=p->next;
}
free(pre);


}
pre-代表的是栈-》p下一个栈

3.进栈运算算法（头插)

4.出栈运算算法

5.取栈顶元素运算算法

6.判断栈空

队列

3.2.1队列的基本概念

队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构。其基本概念是：

1. 先进先出（FIFO）：在队列中，第一个被添加的元素最先被移除。这类似于排队买票，最先进入队列的人最先得到服务。
2. 队列的操作：
   • 入队（Enqueue）：将一个元素添加到队列的末尾。
   • 出队（Dequeue）：移除并返回队列的第一个元素。
   • 查看队头元素（Front/Peek）：查看队列的第一个元素，但不移除它。
3. 队列的类型：
   • 普通队列：遵循标准的先进先出规则。
   • 双端队列（Deque）：允许在队列的两端进行入队和出队操作。
   • 循环队列：队列中的元素循环使用，队尾连接到队头。
4. 用途：队列常用于广度优先搜索（BFS）、任务调度、缓冲区管理等场景。例如，操作系统中的任务排队、打印队列，或消息处理系统中的任务管理等。

队列的实现方式

在计算机科学中，队列通常使用数组或链表来实现。下面分别介绍这两种实现方式：

1. 数组实现

使用数组实现的队列被称为顺序队列。

2. 链表实现

使用链表实现的队列被称为链式队列。

3.2.2队列的基本运算

**初始化队列 InitQueue(Qu)**：建立一个空队列 Qu。

**销毁队列 DestroyQueue(Qu)**：释放队列 Qu 占用的内存空间。

**进队列 EnQueue(Qu, z)**：将元素 z 插入到队列 Qu 的队尾。

**出队列 DeQueue(Qu, z)**：将队列 Qu 的队头元素出队并赋给 z。

**取队头元素 GetHead(Qu, z)**：取出队列 Qu 的队头元素并赋给 z，但该元素不出队。

**判断队空 QueueEmpty(Qu)**：判断队列 Qu 是否为空。

3.2.3队列的顺序存储结构

先出的是front 队头指针

3.2.3.4循环队列

偷个懒 看视频学习

1.循环队列要素

2.循环队列基本算法

1.初始化队列运算算法

2.销毁队列算法

3.进队运算算法

3.2.4队列的链式存储

链式存储算法运算

1.初始化队列算法

2.销毁队列算法

void DestroyQueue(LinkQueue *&lq)
{
Qtype *pre=lq->front,*P;///指向头数据
if(pre!=null)//不为空
{
if(pre==lq->rear)//只有一个节点情况
{ free(pre);}else
{
p=pre->next;//下一个节点
while(p!=null)//不为空

{
free(pre)//节点数据
pre=p;//下节点赋值
p=p->next;//指向下一个节点

}
free(pre);//最好节点释放


}

}
free(lq);
}

3.进队运算算法

4.出队运算算法

5.取队头元素运算算法

6.判断队空运算算法