队列及其实现队列队列的实现

队列

队列即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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏帘卷西风的专栏

关于lua扩展库lpack的使用指南

lpack的具体用法 1、打包接口pack的使用,全局名字容易混淆lua本身函数unpack,使用string.pack好些,也可以修改源码修改函数名。

1493
来自专栏冰霜之地

如何设计并实现一个线程安全的 Map ?(下篇)

在上篇中,我们已经讨论过如何去实现一个 Map 了,并且也讨论了诸多优化点。在下篇中,我们将继续讨论如何实现一个线程安全的 Map。说到线程安全,需要从概念开始...

4877
来自专栏微信公众号:Java团长

从并发编程到分布式系统——如何处理海量数据(上)

在这里想写写自己在学习并发处理的学习思路,也会聊聊自己遇到的那些坑,以此为记,希望鞭策自己不断学习、永不放弃!

771
来自专栏跟着阿笨一起玩NET

C# 解析js方法,并调用js方法

本文转载:http://www.cnblogs.com/StudyLife/archive/2013/03/11/2953516.html

3193
来自专栏林冠宏的技术文章

C++ 连接数据库的入口和获取列数、数据

这里不具体放出完整的程序,分享两个核心函数: 由于这里用到的函数是编译器自己的库所没有的,需要自己下载mysql.h库或者本地有数据库,可以去bin找到,放进去...

2538
来自专栏Java编程技术

常用开源框架中设计模式使用分析(全)

说起来设计模式,大家应该都耳熟能详,设计模式代表了软件设计的最佳实践,是经过不断总结提炼出来的代码设计经验的分类总结,这些模式或者可以简化代码,或者可以是代码逻...

1422
来自专栏FD的专栏

一步步理解python的异步IO

看到越来越多的大佬都在使用python的异步IO,协程等概念来实现高效的IO处理过程,可是我对这些概念还不太懂,就学习了一下。 因为是初学者,在理解上有很多不到...

1562
来自专栏崔庆才的专栏

腾讯云上 Winpcap 网络编程四之主机通信

由于腾讯云上提供了Windows系统,所以我们这次Winpcap编程选用腾讯云主机实验,让大家简要了解两台云主机的通信方法以及实践过程。

5620
来自专栏Elasticsearch实验室

Elasitcsearch 底层系列 Lucene 内核解析之 Stored Fields

Lucene 的 stored fields 主要用于行存文档需要保存的字段内容,每个文档的所有 stored fields 保存在一起,在查询请求需要返回字段...

6135
来自专栏我的小碗汤

自动评论csdn博客文章实现

今天我们来用java代码爬取csdn博客网站,然后自动评论,这一波操作可以说是相当风骚了,话不多说,咱上代码。

1842

扫码关注云+社区

领取腾讯云代金券