队列及其实现队列队列的实现
队列及其实现队列队列的实现
月见樽
发布于 2018-04-27 11:58:22
发布于 2018-04-27 11:58:22
队列
队列即FIFO，一言以蔽之就是先进先出。比如入队列的顺序是1,2,3,4，那么出队列的顺序也是1,2,3,4
队列的实现
软件——GO语言实现
除了使用链表和数组实现链表以外，GO语言内置一种新的数据结构叫切片，可以实现类似于动态语言中的list的一些功能（切片和append），用这个数据结构实现队列非常容易
结构体
type fifo struct {
data []int
length int
}出队列方法
f.data[1:]就是类似于python中的切片操作，表示切掉第一个值，剩下的保留
func (f *fifo) Pop() (int, error) {
if len(f.data) == 0 {
return 0, errors.New("empty fifo")
} else {
temp := f.data[0]
f.data = f.data[1:]
f.length--
return temp, nil
}
}入队列方法
append方法是go语言自带的切片处理方法，第一个参数是要操作的切片，随后的参数都是要插入到切片之后的变量，返回值是完成插入后新的切片
func (f *fifo) Push(din int) {
f.data = append(f.data, din)
f.length++
}构造函数
func New_fifo() *fifo {
return &fifo{[]int{}, 0}
}硬件——Verilog实现
fifo由于其不改变数据顺序常用于实现buffer，常用双口ram+控制逻辑的方法实现fifo
端口定义
module fifo_control #(
parameter WIDTH = 8,
parameter DEPTH_LOG = 8
)(
input clk, // Clock
input rst_n, // Asynchronous reset active low
input fifo_write_req,
input [WIDTH - 1:0]fifo_write_data,
output reg fifo_full,
input fifo_read_req,
output reg fifo_empty,
output reg ram_write_req,
output reg [DEPTH_LOG - 1:0]ram_write_addr,
output reg [WIDTH - 1:0]ram_write_data,
output reg [DEPTH_LOG - 1:0]ram_read_addr
);线网定义
reg [DEPTH_LOG - 1:0]write_point,read_point;
wire almost_full = (write_point == read_point - 1'b1)?1'b1:1'b0;
wire almost_empty = (write_point == read_point + 1'b1)?1'b1:1'b0;写指针控制
always @(posedge clk or negedge rst_n) begin
if(~rst_n) begin
write_point <= 'b0;
ram_write_req <= 'b0;
end else if((!fifo_full || fifo_read_req) && fifo_write_req) begin
write_point <= write_point + 1'b1;
ram_write_req <= 1'b1;
end else begin
ram_write_req <= 'b0;
end
end(!fifo_full || fifo_read_req) && fifo_write_req为写执行条件：
- fifo不满且写请求
- 读写同时又请求（不可能溢出）
fifo满信号生成
always @ (posedge clk or negedge rst_n) begin
if(~rst_n) begin
fifo_full <= 'b0;
end else if(fifo_read_req && fifo_write_req) begin
fifo_full <= fifo_full;
end else if(fifo_read_req) begin
fifo_full <= 'b0;
end else if(almost_full && fifo_write_req) begin
fifo_full <= 'b1;
end
end-
fifo_read_req && fifo_write_req当读写同时进行时，满信号状态不会改变 -
almost_full && fifo_write_req当写请求有效且只剩一个空位时，满信号置位 -
fifo_read_req只要读过一次，不可能满
写地址与数据生成
always @ (posedge clk or negedge rst_n) begin
if(~rst_n) begin
ram_write_data <= 'b0;
ram_write_addr <= 'b0;
end else begin
ram_write_data <= fifo_write_data;
ram_write_addr <= write_point;
end
end读指针/地址控制
always @ (posedge clk or negedge rst_n) begin
if(~rst_n) begin
read_point <= 'b0;
ram_read_addr <= 'b0;
end else if(!fifo_empty && fifo_read_req) begin
read_point <= read_point + 1'b1;
ram_read_addr <= read_point;
end
end-
!fifo_empty && fifo_read_req当fifo非空时，读fifo
fifo空信号生成
always @ (posedge clk or negedge rst_n) begin
if(~rst_n) begin
fifo_empty <= 1'b1;
end else if(fifo_read_req && fifo_write_req) begin
fifo_empty <= fifo_empty;
end else if(fifo_write_req) begin
fifo_empty <= 1'b0;
end else if(almost_empty && fifo_read_req) begin
fifo_empty <= 1'b1;
end
end本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.12.04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录