目录
栈(stack),是具有一定操作约束的线性表。其只能在一端(栈顶,Top)做插入、删除操作。
栈的抽象数据类型描述
数据对象集:一个有0或多个元素的线性表。
操作集:
栈的顺序存储结构体,通常由一个数组和一个记录栈顶元素位置的变量组成。
- type Stack struct {
- MaxSize int
- Top int
- arr [10]int
- }
- func initStack() (stack *Stack) {
- stack = &Stack{
- MaxSize: 10,
- Top: -1,
- arr: [10]int{},
- }
- return stack
- }
- func (s *Stack) push(v int) error {
- //判断栈是否满
- if s.MaxSize-1 == s.Top {
- return errors.New("栈已满,无法插入数据")
- }
-
- s.Top++ //栈顶+1
- s.arr[s.Top] = v //入栈
-
- return nil
- }
- func (s *Stack) pop() (int, error) {
- //判断栈是否为空
- if s.Top == -1 {
- return 0, errors.New("error: 栈为空")
- }
-
- v := s.arr[s.Top] //出栈
- s.Top-- //栈顶-1
-
- return v, nil
- }
- package main
-
- import (
- "errors"
- "fmt"
- )
-
- type Stack struct {
- MaxSize int
- Top int
- arr [10]int
- }
-
- func main() {
- //初始化一个栈
- stack1 := initStack()
-
- //验证空栈pop报错
- fmt.Println("---空栈pop报错---")
- _, err := stack1.pop()
- if err != nil {
- fmt.Println(err)
- }
-
- //入栈
- fmt.Println("---栈满push报错---")
- for i := 1; 1 <= 20; i++ {
- err := stack1.push(i)
- if err != nil {
- fmt.Println(err)
- break
- }
- }
-
- //出栈
- v, _ := stack1.pop()
- fmt.Println("---pop出栈---:", v)
- }
-
- func initStack() (stack *Stack) {
- stack = &Stack{
- MaxSize: 10,
- Top: -1,
- arr: [10]int{},
- }
- return stack
- }
-
- func (s *Stack) push(v int) error {
- //判断栈是否满
- if s.MaxSize-1 == s.Top {
- return errors.New("栈已满,无法插入数据")
- }
-
- s.Top++ //栈顶+1
- s.arr[s.Top] = v //入栈
-
- return nil
- }
-
- func (s *Stack) pop() (int, error) {
- //判断栈是否为空
- if s.Top == -1 {
- return 0, errors.New("error: 栈为空")
- }
-
- v := s.arr[s.Top] //出栈
- s.Top-- //栈顶-1
-
- return v, nil
- }
使用一个数组实现两个堆栈,要求最大地利用数组空间。使数组只要有空间,入栈操作就可以成功。
- package main
-
- import (
- "errors"
- "fmt"
- )
-
- type Stack struct {
- Top1 int
- Top2 int
- arr [10]int
- }
-
- func main() {
- //初始化一个栈
- stack1 := initStack()
- fmt.Println(stack1.arr)
-
- //验证空栈pop报错
- fmt.Println("---空栈pop报错---")
- _, err := stack1.pop(1)
- if err != nil {
- fmt.Println(err)
- }
- _, err = stack1.pop(2)
- if err != nil {
- fmt.Println(err)
- }
-
- //入栈
- fmt.Println("---栈满push报错---")
- for i := 1; i <= 5; i++ {
- err := stack1.push(i, 1)
- if err != nil {
- fmt.Println(err)
- break
- }
- }
- for i := 1; i <= 6; i++ {
- err := stack1.push(i, 2)
- if err != nil {
- fmt.Println(err)
- break
- }
- }
- fmt.Println(stack1.arr)
-
- //出栈
- v, _ := stack1.pop(1)
- fmt.Println("---pop出栈---:", v)
- v, _ = stack1.pop(2)
- fmt.Println("---pop出栈---:", v)
- }
-
- func initStack() (stack *Stack) {
- stack = &Stack{
- Top1: -1,
- Top2: 10,
- arr: [10]int{},
- }
- return stack
- }
-
- //通过tag区分插入哪个队列
- func (s *Stack) push(v int, tag int) error {
- //判断栈是否满
- if s.Top2-s.Top1 == 1 {
- return errors.New("栈已满,无法插入数据")
- }
-
- if tag == 1 {
- s.Top1++ //栈A,栈顶+1
- s.arr[s.Top1] = v //入栈
- } else if tag == 2 {
- s.Top2-- //栈B,栈顶-1
- s.arr[s.Top2] = v //入栈
- } else {
- return errors.New("tag参数不合法, 需要传入1或2")
- }
-
- return nil
- }
-
- func (s *Stack) pop(tag int) (int, error) {
- var v int
- //判断栈是否为空
- if tag == 1 {
- if s.Top1 == -1 {
- return 0, errors.New("error: 栈A为空")
- }
- v = s.arr[s.Top1] //出栈
- s.Top1-- //栈A,栈顶-1
- } else if tag == 2 {
- if s.Top2 == 10 {
- return 0, errors.New("error: 栈B为空")
- }
- v = s.arr[s.Top2] //出栈
- s.Top2++ //栈B,栈顶+1
- }
-
- return v, nil
- }
链栈
- type LinkStack struct {
- data int
- next *LinkStack
- }
- func initLinkStack() (linkStack *LinkStack) {
- //初始化链栈,新建链栈头节点
- linkStack = &LinkStack{
- data: -1,
- next: nil,
- }
- return linkStack
- }
- func (s *LinkStack) push(v int) {
- //链栈可先不考虑栈满,因为目前没有对栈做限制
-
- pushNode := &LinkStack{
- data: v,
- next: nil,
- }
-
- pushNode.next = s.next //入栈节点的next指向头节点的next节点
- s.next = pushNode //头节点指向入栈节点
- }
- func (s *LinkStack) pop() (int, error) {
- var v int
- //判断栈是否为空
- if s.next == nil {
- return 0, errors.New("error: 栈为空")
- }
-
- tmpTop := s.next
- v = tmpTop.data //出栈,获取节点的元素值
-
- s.next = tmpTop.next //头节点指向原栈顶节点的下一个节点
- tmpTop.next = nil //原栈顶节点指向nil
-
- return v, nil
- }
- package main
-
- import (
- "errors"
- "fmt"
- )
-
- type LinkStack struct {
- data int
- next *LinkStack
- }
-
- func main() {
- //初始化一个链栈
- fmt.Println("---初始化链栈---")
- linkStack1 := initLinkStack()
-
- //入栈
- fmt.Println("---入栈---")
- for i := 1; i <= 5; i++ {
- linkStack1.push(i)
- fmt.Printf("第%v次出栈, 值为:%v\n", i, i)
- }
-
- //出栈
- fmt.Println("---出栈---")
- for i := 1; i <= 6; i++ {
- v, err := linkStack1.pop()
- if err != nil {
- fmt.Println(err)
- break
- }
- fmt.Printf("第%v次出栈, 值为:%v\n", i, v)
- }
- }
-
- func initLinkStack() (linkStack *LinkStack) {
- //初始化链栈,新建链栈头节点
- linkStack = &LinkStack{
- data: -1,
- next: nil,
- }
- return linkStack
- }
-
- func (s *LinkStack) push(v int) {
- //链栈可先不考虑栈满,因为目前没有对栈做限制
-
- pushNode := &LinkStack{
- data: v,
- next: nil,
- }
-
- pushNode.next = s.next //入栈节点的next指向头节点的next节点
- s.next = pushNode //头节点指向入栈节点
- }
-
- func (s *LinkStack) pop() (int, error) {
- var v int
- //判断栈是否为空
- if s.next == nil {
- return 0, errors.New("error: 栈为空")
- }
-
- tmpTop := s.next
- v = tmpTop.data //出栈,获取节点的元素值
-
- s.next = tmpTop.next //头节点指向原栈顶节点的下一个节点
- tmpTop.next = nil //原栈顶节点指向nil
-
- return v, nil
- }