算法学习与笔记（五）数据结构-爱代码爱编程
一.数据结构
1.数据结构概念：指数据及其为了对数据进行有效处理而对数据建立的各种结构关系
2.抽象数据类型概念：一个抽象数据类型由数据及对数据进行操作的函数组成
二.堆栈
堆栈是一种抽象的数据类型，它具有如下函数：
stack_init()堆栈清空
empty()若堆栈空，则回送真，若堆栈不空，则回送假
push(val)把项val加入堆栈
pop（）把最近加入堆栈的项删除
top（）回送最近加入堆栈的项，但不删除
堆栈最简单的实现办法是数组
1.堆栈初始化:将一个堆栈初始化为空，空堆栈的t=-1
Input Parameters:None
Output Parameters:None
stack_init(){
t=-1
}
2.测试堆栈是否为空。若堆栈为空，返回为真，堆栈不空，返回t=-1
Input Parameters:None
Output Parameters:None
empty(){
t=t+1
data[t]=val
}
3.从堆栈删除一个元素，删除最近加入的元素
Input Parameters:None
Output Parameters:None
pop(){
t=t-1
}
4.回送顶元素：但不删除
Input Parameters:None
Output Parameters:None
top(){
return data[t]
}
例题：判断栈中是否正好只有一个元素，函数返回真，否则返回假，不改变栈的数据结构
Input Parameters:s（堆栈）
Output Parameters:None
one(s){
if(s.empty())
return false
val=s.top
s.pop()
flag=s.empty()
s.push(val)
return flag
}这是一个函数，输入参数为一个堆栈s，输出参数为无。函数名为one，其功能是判断堆栈s是否为空。具体实现如下：
- 首先判断堆栈s是否为空，如果是，则返回false；
- 如果堆栈s不为空，则将堆栈顶部元素弹出，并将其赋值给变量val；
- 再次判断堆栈s是否为空，将判断结果赋值给变量flag；
- 将之前弹出的元素val重新压入堆栈s中；
- 最终返回变量flag。
简单来说，这个函数的作用就是判断堆栈s是否为空，并且不改变堆栈s的内容。
堆栈是后进先出，队列是按顺序，先进的先出
三。队列
队列有入队和出队，元素加入到队尾，从队首删除
队列有如下抽象数据类型：
queue_init() 队列清空
empty() 若队列为空，回送真；若队列不空，回送假
enqueue(val) 项val加入队列
dequeue() 删除最早加入队列的项
front() 回送最早加入队列的项，但不删除
队列可以用数组来实现，用r和f来跟踪队尾和队首的下标，一个空队列的r和f都为-1
1.队列初始化:将一个队列初始化为空，空队列有r=f=-1
Input Parameters:None
Output Parameters:None
queue_init(){
r=f=-1
}
2.测试空队列 若队列为空，返回为真，队列不空，返回假。空队列有r=f=-1
Input Parameters:None
Output Parameters:None
empty(){
return r= -1
}
3.向队列加入一个元素
本算法将val加入队列，队列用大小为SIZE的一个数组表示。假定队列未满，最近加入的项在下标r处（队尾）处，最早加入的项在下标f处（队首）。若队列空，则r=f=-1
Input Parameters:val
Output Parameters:None
enqueue(){
if(empty())
r=f=0
else{
r=r+1
if(r==SIZE)
r=0
}
data[r]=val
}这是一个简单的队列数据结构的enqueue操作的代码实现，其输入参数为要添加的值val，输出参数为None。enqueue操作的作用是将一个元素添加到队列的尾部。
具体实现逻辑如下：
(1)如果队列为空，即队列中没有元素，则将队列头尾指针f和r都设置为0。
(2)如果队列不为空，则将队列尾指针r加1，即将新的元素添加到队列的尾部。
(3)如果队列尾指针r已经达到了队列的最大容量SIZE，则将其设置为0，即循环回到队列的开头。
(4)将要添加的值val存储到队列中当前尾指针所指向的位置data[r]中。
需要注意的是，该代码没有考虑队列满的情况，即队列中元素个数已经达到了队列的最大容量，此时不能再继续添加元素。因此，如果想要完整的队列实现，还需要添加对队列满的判断和处理。
4.从队列中删除一个元素 本算法从队列中删除最先加入的那个项。队列用一个大小为SIZE的数组表示。算法假定队列不为空。最近加入的项在下标r处（队尾），最先加入的项在下标f处（队首）。若队列为空，则r=f=-1
Input Parameters:None
Output Parameters:None
dequeue(){
if(r==f)
r=f=-1
else{
f=f+1
if(f==SIZE)
f=0
}
}这是一个简单的队列（queue）的dequeue操作的伪代码实现。其中，r代表队尾指针，f代表队头指针，SIZE代表队列的最大容量。具体解释如下：
(1)如果队列为空，即队头指针f和队尾指针r都为-1，则无法进行出队操作，直接返回。
(2)如果队列不为空，则将队头指针f向后移动一位，表示出队一个元素。
(3)如果队头指针f移到了队列的末尾，即f==SIZE，那么将其重置为0，以实现循环队列的效果。
需要注意的是，这段代码仅为伪代码实现，具体实现方式可能会有所不同，例如需要考虑线程安全、队列满的情况等。