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