栈与栈的实现栈栈的基本操作栈的实现

栈是一种基础的数据结构,只从一端读写数据。基本特点就”后进先出“,例如顺序入栈1,2,3,4,5,再顺序出栈是5,4,3,2,1

栈的基本操作

栈的基本操作有如下几种:

  • 检测栈是否为空
  • 返回栈存储数据的数量
  • 返回栈顶数据/返回栈顶数据并将其弹出
  • 将数据压入栈
  • 清空栈

栈的实现

软件实现——GO语言

软件的栈可以使用链表基本结构实现或使用数组实现:使用链表栈的优势是栈的容量几乎不限,确定是入栈出栈都需要开销较大的声明结构体;数组实现的优势是速度快(自增自减一般有指令实现),但是空间必须预先指定。

统一adt接口

type Stack_adt interface {
    Is_empty() bool
    Get_depth() int
    Push(data Stack_data)
    Pop() (Stack_data, error)
    Get_head() (Stack_data, error)
    Clear()
}

链表栈

数据结构

type stack_node struct {
    data Stack_data
    next *stack_node
}

type Link_stack struct {
    length int
    head   *stack_node
}

判空方法

func (l *Link_stack) Is_empty() bool {
    if l.head.next == nil {
        return true
    } else {
        return false
    }
}

获取栈中数据量方法

func (l *Link_stack) Get_depth() int {
    return l.length
}

压栈方法

func (l *Link_stack) Push(data Stack_data) {
    new_node := stack_node{data, l.head.next}
    l.head.next = &new_node
    l.length++
}

对于入栈数据,建立链表节点并将其插入到头结点后(读取位置),保证后进先出

弹栈方法

func (l *Link_stack) Pop() (Stack_data, error) {
    if l.Is_empty() {
        return Stack_data{}, errors.New("empty stack")
    } else {
        data := l.head.next.data
        l.head.next = l.head.next.next
        l.length--
        return data, nil
    }
}

直接取出头结点后的节点,若本来就是空栈则返回一个空栈的errors异常,否则该异常为nil

获取栈顶数据(仅获取,不弹出)

func (l *Link_stack) Get_head() (Stack_data, error) {
    if l.Is_empty() {
        return Stack_data{}, errors.New("empty stack")
    } else {
        return l.head.next.data, nil
    }
}

与弹栈相同,不同的是读取后不将读取的节点移出链表

清空栈

func (l *Link_stack) Clear() {
    _, err := l.Pop()
    for err == nil {
        _, err = l.Pop()
    }
}

不断弹栈并查看异常(抛弃读出数据),直到报出空栈异常(返回异常不为nil

数组栈

数据结构

const DEPTH = 10

type Array_stack struct {
    data   [DEPTH]Stack_data
    length int
}

data为数组,用于存储数据;length为存入数据的数量,同时也是“栈顶指针”,标记入栈位置

判空方法

func (a *Array_stack) Is_empty() bool {
    if a.length == 0 {
        return true
    } else {
        return false
    }
}

获取栈中数据量方法

func (a *Array_stack) Get_depth() int {
    return a.length
}

压栈方法

func (a *Array_stack) Push(data Stack_data) {
    if a.length >= DEPTH {
        return
    } else {
        a.data[a.length] = data
        a.length++
    }
}

对于入栈数据,若入栈位置已经超出数组尺寸,则栈满,不入栈。否则将输入数据插入length标记的入栈位置,并将length自加

弹栈方法

func (a *Array_stack) Pop() (Stack_data, error) {
    if a.length == 0 {
        return Stack_data{}, errors.New("empty stack")
    } else {
        a.length--
        return a.data[a.length], nil
    }
}

先将length自减,获得上一个入栈元素的位置,再返回该值

获取栈顶数据(仅获取,不弹出)

func (a *Array_stack) Get_head() (Stack_data, error) {
    if a.length == 0 {
        return Stack_data{}, errors.New("empty stack")
    } else {
        return a.data[a.length-1], nil
    }
}

与弹栈相同,不同的是读取后不改变“栈顶指针”的位置

清空栈

func (a *Array_stack) Clear() {
    a.length = 0
}

直接将“栈顶指针”清零即可实现清空栈

切片栈

切片是一种Go语言特有的数据结构,类似于动态数组,使用切片可以实现深度可变的栈。

硬件实现——Verilog语言

module stack_controller #(
    parameter DEPTH_LOG = 4,
    parameter WIDTH = 8
)(
    input clk,    // Clock
    input rst_n,  // Asynchronous reset active low

    input stack_write_req,
    input [WIDTH - 1:0]stack_write_data,
    input stack_read_req,

    output reg stack_empty,
    output stack_full,

    output reg ram_write_req,
    output reg [DEPTH_LOG - 1:0]ram_addr,
    output reg [WIDTH - 1:0]ram_write_data
);

reg [DEPTH_LOG:0]stack_point;
wire is_full = (stack_point == 2 ** DEPTH_LOG)?1'b1:1'b0;
wire is_empty = (stack_point == 'b0)?1'b1:1'b0;
always @ (posedge clk or negedge rst_n) begin //control point of stack
    if(~rst_n) begin
        stack_point <= 'b0;
    end else if(stack_write_req && stack_read_req) begin //lock
        stack_point <= stack_point;
    end else if(stack_write_req && !is_full) begin //write when stack is not full
        stack_point <= stack_point + 1'b1;
    end else if(stack_read_req && !is_empty) begin // read when stack is not empty
        stack_point <= stack_point - 1'b1;
    end
end
assign stack_full = stack_point[DEPTH_LOG];

always @ (posedge clk or negedge rst_n) begin //generate empty signal
    if(~rst_n) begin
        stack_empty <= 'b0;
    end else if(ram_addr == 'b0 && is_empty) begin // delay signal
        stack_empty <= 1'b1;
    end else begin
        stack_empty <= 'b0;
    end
end

always @ (posedge clk or negedge rst_n) begin //generate ram_write_req
    if(~rst_n) begin
        ram_write_req <= 'b0;
    end else if(!is_full) begin
        ram_write_req <= stack_write_req;
    end else begin
        ram_write_req <= 'b0;
    end
end

always @ (posedge clk or negedge rst_n) begin //prepare the addr and data for push
    if(~rst_n) begin
        ram_addr <= 'b0;
        ram_write_data <= stack_write_data;
    end else begin
        ram_addr <= stack_point[DEPTH_LOG - 1:0];
        ram_write_data <= stack_write_data;
    end
end

endmodule

Verilog实现栈的关键点有三个:

  • 控制栈顶指针
  • 栈满信号生成
  • 栈空信号生成

该硬件栈的栈顶指针指向下一个入栈的位置,且位数比ram地址位多一位,当最高位为1时,可认为栈溢出,停止写入;同理,当栈顶指针指向0,该栈为空栈。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我的博客

GO获取表单元素

1.如果使用Form[“username”]获取表单元素需调用ParseForm(),获取到的是数组 2.如果使用FormValue会自动调用ParseFor...

428150
来自专栏我的博客

Go命令介绍

1.go build 用于编译代码 2.go clean 用来移除当前源码包和关联源码包里面编译生成的文件 _obj/ 旧的object目...

38380
来自专栏友弟技术工作室

Go 程序的基本结构和要素

示例 package main import "fmt" func main() { fmt.Println("hello, world") } 包...

349110
来自专栏禅林阆苑

macos下golang配置 【原创】

macos下golang配置 Write By CS逍遥剑仙 我的主页: www.csxiaoyao.com GitHub: github.c...

28350
来自专栏禅林阆苑

golang之fmt格式占位符总结 【原创】

golang之fmt格式占位符总结 Write By CS逍遥剑仙 我的主页: www.csxiaoyao.com GitHub: githu...

88380
来自专栏文武兼修ing——机器学习与IC设计

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

队列 队列即FIFO,一言以蔽之就是先进先出。比如入队列的顺序是1,2,3,4,那么出队列的顺序也是1,2,3,4 队列的实现 软件——GO语言实现 除了使用链...

46470
来自专栏从零开始的linux

初识docker

docker使用go语言开发,基于apache2.0协议 容器虚拟化 ? 传统虚拟化 ? Docker的优势 启动非常快,秒级实现 资源利用率很高,一台机器可以...

40150
来自专栏我的博客

Go函数知识

1.函数格式 func funcName(input1 type1, input2 type2) (output1 type1, output2 type2) ...

36580
来自专栏友弟技术工作室

golang之Struct什么是结构体struct?

最近在复习golang,学习的东西,如果不使用,很快就会忘记。所以,准备复习完golang,做一个练手的小项目,加深对golang的学习。今天开始公司,进入封闭...

65460

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励