棧
棧是一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)咖摹，只從一端讀寫數(shù)據(jù)柠衍。基本特點就”后進先出“孝赫，例如順序入棧1,2,3,4,5，再順序出棧是5,4,3,2,1
棧的基本操作
棧的基本操作有如下幾種：
- 檢測棧是否為空
- 返回棧存儲數(shù)據(jù)的數(shù)量
- 返回棧頂數(shù)據(jù)/返回棧頂數(shù)據(jù)并將其彈出
- 將數(shù)據(jù)壓入棧
- 清空棧
棧的實現(xiàn)
軟件實現(xiàn)——GO語言
軟件的椇旆可以使用鏈表基本結(jié)構(gòu)實現(xiàn)或使用數(shù)組實現(xiàn)：使用鏈表棧的優(yōu)勢是棧的容量幾乎不限青柄，確定是入棧出棧都需要開銷較大的聲明結(jié)構(gòu)體；數(shù)組實現(xiàn)的優(yōu)勢是速度快（自增自減一般有指令實現(xiàn)）预侯，但是空間必須預(yù)先指定致开。
統(tǒng)一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()
}
鏈表棧
數(shù)據(jù)結(jié)構(gòu)
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
}
}
獲取棧中數(shù)據(jù)量方法
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++
}
對于入棧數(shù)據(jù)，建立鏈表節(jié)點并將其插入到頭結(jié)點后（讀取位置）萎馅，保證后進先出
彈棧方法
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
}
}
直接取出頭結(jié)點后的節(jié)點双戳，若本來就是空棧則返回一個空棧的errors異常，否則該異常為nil
獲取棧頂數(shù)據(jù)（僅獲取糜芳，不彈出）
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
}
}
與彈棧相同飒货，不同的是讀取后不將讀取的節(jié)點移出鏈表
清空棧
func (l *Link_stack) Clear() {
_, err := l.Pop()
for err == nil {
_, err = l.Pop()
}
}
不斷彈棧并查看異常（拋棄讀出數(shù)據(jù)），直到報出空棧異常（返回異常不為nil）
數(shù)組棧
數(shù)據(jù)結(jié)構(gòu)
const DEPTH = 10
type Array_stack struct {
data [DEPTH]Stack_data
length int
}
data為數(shù)組峭竣，用于存儲數(shù)據(jù)塘辅；length為存入數(shù)據(jù)的數(shù)量，同時也是“棧頂指針”皆撩，標(biāo)記入棧位置
判空方法
func (a *Array_stack) Is_empty() bool {
if a.length == 0 {
return true
} else {
return false
}
}
獲取棧中數(shù)據(jù)量方法
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++
}
}
對于入棧數(shù)據(jù)扣墩，若入棧位置已經(jīng)超出數(shù)組尺寸，則棧滿毅访，不入棧。否則將輸入數(shù)據(jù)插入length標(biāo)記的入棧位置盘榨，并將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自減喻粹，獲得上一個入棧元素的位置，再返回該值
獲取棧頂數(shù)據(jù)（僅獲取草巡，不彈出）
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
}
直接將“棧頂指針”清零即可實現(xiàn)清空棧
切片棧
切片是一種Go語言特有的數(shù)據(jù)結(jié)構(gòu)，類似于動態(tài)數(shù)組山憨，使用切片可以實現(xiàn)深度可變的棧查乒。
硬件實現(xiàn)——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實現(xiàn)棧的關(guān)鍵點有三個：
- 控制棧頂指針
- 棧滿信號生成
- 棧空信號生成
該硬件棧的棧頂指針指向下一個入棧的位置郁竟，且位數(shù)比ram地址位多一位玛迄，當(dāng)最高位為1時，可認(rèn)為棧溢出棚亩，停止寫入蓖议；同理虏杰，當(dāng)棧頂指針指向0，該棧為空棧勒虾。
