1、栈的定义
-
栈(stack)是限定仅在表尾进行插入或删除操作的线性表。
- 栈顶(top)，指表尾端。
- 栈底(bottom)，指表头端。
- 空栈，即不含元素的空表。
- LIFO(Last In First Out)，即栈的修改是按后进先出的原则进行的。
- 顺序栈， 指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。
栈中元素和指针之间的关系图
- 由于顺序栈的插入和删除只在栈顶进行，其他操作和顺序表类似，本文只给出了以下基本操作。
- 初始化
- 入栈
- 出栈
- 取栈顶元素
2、顺序栈的初始化
type Stack struct {
top int
base int
stackSize int
stackList []interface{}
}
//栈的初始化
func initStack(size int, arr []interface{}) *Stack{
if size <= 0 {return new(Stack)}
list := &Stack{
top: 0,
base: 0,
stackSize: size,
stackList: make([]interface{}, 0, size),
}
for i := range arr {
list.stackList = append(list.stackList, arr[i])
list.top ++
}
return list
}
3、入栈
//入栈
func (stack *Stack) push(val interface{}) {
if stack.top - stack.base == stack.stackSize{
fmt.Println("栈满")
return
}
stack.stackList = append(stack.stackList, val)
stack.top ++
}
4、出栈
//出栈
func (stack *Stack) pop() interface{}{
if stack.top == stack.base {
fmt.Println("栈空")
return nil
}
val := stack.stackList[stack.top - 1]
stack.top --
stack.stackList = append(stack.stackList[:stack.top])
return val
}
5、取栈顶元素
//取栈顶元素
func (stack *Stack) getTop() interface{} {
if stack.top == stack.base {
fmt.Println("栈空")
return nil
}
val := stack.stackList[stack.top - 1]
return val
}
6、完整代码即结果展示
package main
import "fmt"
type Stack struct {
top int
base int
stackSize int
stackList []interface{}
}
//栈的初始化
func initStack(size int, arr []interface{}) *Stack{
if size <= 0 {return new(Stack)}
list := &Stack{
top: 0,
base: 0,
stackSize: size,
stackList: make([]interface{}, 0, size),
}
for i := range arr {
list.stackList = append(list.stackList, arr[i])
list.top ++
}
return list
}
//入栈
func (stack *Stack) push(val interface{}) {
if stack.top - stack.base == stack.stackSize{
fmt.Println("栈满")
return
}
stack.stackList = append(stack.stackList, val)
stack.top ++
}
//出栈
func (stack *Stack) pop() interface{}{
if stack.top == stack.base {
fmt.Println("栈空")
return nil
}
val := stack.stackList[stack.top - 1]
stack.top --
stack.stackList = append(stack.stackList[:stack.top])
return val
}
//取栈顶元素
func (stack *Stack) getTop() interface{} {
if stack.top == stack.base {
fmt.Println("栈空")
return nil
}
val := stack.stackList[stack.top - 1]
return val
}
func main() {
data := []interface{}{
"bala",
"aa",
12,
45,
}
//var data2 []interface{}
L := initStack(6, data)
fmt.Println(L)
L.push("99")
fmt.Println(L)
fmt.Printf("栈顶元素为:%s\n", L.getTop())
fmt.Println(L.pop())
fmt.Println(L)
}
&{4 0 6 [bala aa 12 45]}
&{5 0 6 [bala aa 12 45 99]}
栈顶元素为:99
99
&{4 0 6 [bala aa 12 45]}
7、总结
- 和链栈一起总结了
