栈

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

栈的基本操作

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

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

栈的实现

软件实现——GO语言

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

统一adt接口

1
2
3
4
5
6
7
8
type Stack_adt interface {
	Is_empty() bool
	Get_depth() int
	Push(data Stack_data)
	Pop() (Stack_data, error)
	Get_head() (Stack_data, error)
	Clear()
}

链表栈

数据结构

1
2
3
4
5
6
7
8
9
type stack_node struct {
	data Stack_data
	next *stack_node
}

type Link_stack struct {
	length int
	head   *stack_node
}

判空方法

1
2
3
4
5
6
7
func (l *Link_stack) Is_empty() bool {
	if l.head.next == nil {
		return true
	} else {
		return false
	}
}

获取栈中数据量方法

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

压栈方法

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

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

弹栈方法

1
2
3
4
5
6
7
8
9
10
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

获取栈顶数据（仅获取，不弹出）

1
2
3
4
5
6
7
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
	}
}

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

清空栈

1
2
3
4
5
6
func (l *Link_stack) Clear() {
	_, err := l.Pop()
	for err == nil {
		_, err = l.Pop()
	}
}

不断弹栈并查看异常（抛弃读出数据），直到报出空栈异常（返回异常不为nil）

数组栈

数据结构

1
2
3
4
5
6
const DEPTH = 10

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

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

判空方法

1
2
3
4
5
6
7
func (a *Array_stack) Is_empty() bool {
	if a.length == 0 {
		return true
	} else {
		return false
	}
}

获取栈中数据量方法

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

压栈方法

1
2
3
4
5
6
7
8
func (a *Array_stack) Push(data Stack_data) {
	if a.length >= DEPTH {
		return
	} else {
		a.data[a.length] = data
		a.length++
	}
}

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

弹栈方法

1
2
3
4
5
6
7
8
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自减，获得上一个入栈元素的位置，再返回该值

获取栈顶数据（仅获取，不弹出）

1
2
3
4
5
6
7
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
	}
}

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

清空栈

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

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

切片栈

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

硬件实现——Verilog语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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，该栈为空栈。