栈

栈是一种基础的数据结构，只从一端读写数据。基本特点就”后进先出“，例如顺序入栈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，该栈为空栈。