栈.md

[TOC]

---

栈

---

一，栈的定义

栈是限定仅在表尾进行插入和删除操作的线性表。

我们把允许插入和删除的一端称为栈顶（top）。另一端称为栈底（bottom）。不含任何元素的栈称为空栈。

栈又称为后进先出的线性表。（Last In Fist Out）LIFO 结构

最先进栈的就一定最后出栈吗？当然不是，应该说是不一定，因为第一个进栈如果，第二个进栈前就出栈了，对吧。

线性表有顺序结构和链式结构，同样栈也是这样。

顺序结构的有扩容问题，链式结构的不存在扩容问题。

二，golang实现栈结构

公共参数

//长度
const MaxSize = 5

1.顺序结构

type Stack struct {
	Data [MaxSize]int
	Top  int
}
//打印栈
func (s *Stack) Print() {
	fmt.Println(s.Data)
}
//push
func (s *Stack) Push(val int) (bool, error) {
	if s.Top == MaxSize-1 {
		return false, fmt.Errorf("空间已满")
	}
	s.Data[s.Top] = val
	s.Top++
	return true, nil
}
//pop
func (s *Stack) Pop() (int, error) {
	if s.Top == 0 {
		return 0, fmt.Errorf("没有元素了")
	}
	s.Top--
	return s.Data[s.Top], nil //这样容易产生内存泄漏。因为这个元素在顺序结构中还存在呢。并没有清理掉。
}

虽然指针进行了偏移，但是由于此对象依然存在于内存中。

3 <nil>
2 <nil>
1 <nil>
[1 2 3 0 0] 
PASS

优化pop接口之后

//将已经取出的元素进行置空操作
func (s *Stack) Pop_New() (int, error) {
	if s.Top == 0 {
		return 0, fmt.Errorf("没有元素了")
	}
	s.Top--
	v := s.Data[s.Top]
	s.Data[s.Top] = 0
	return v, nil //清理掉,Pop的元素。
}

6 <nil>
5 <nil>
4 <nil>
[0 0 0 0 0]
PASS

2.链式结构

//链式栈
type ChainStack struct {
	head  *Chain
	count int
}
//链
type Chain struct {
	Data int
	Next *Chain
}

//打印链的数据
func (s *ChainStack) Print() {
	content := ""
	cur := s.head
	for {
		if cur == nil {
			break
		}
		content += strconv.Itoa(cur.Data) + " "
		cur = cur.Next
	}
	fmt.Println(content)
}

//添加数据
func (s *ChainStack) Push(data int) bool {
	head := &Chain{
		Data: data,
		Next: s.head,
	}
	s.head = head
	s.count++
	return true
}
//抛出数据
func (s *ChainStack) Pop() int {
	content := 0
	if s.head != nil {
		content = s.head.Data
		s.head = s.head.Next
		s.count--
	}
	return content
}

三，双栈共享空间结构

//双栈共享空间结构
type DoubleStack struct {
	Data []int
	Top1 int
	Top2 int
}

//创建双栈共享空间结构对象
func NewDoubleStack() *DoubleStack {
	return &DoubleStack{
		Data: make([]int, MaxSize),
		Top1: 0,
		Top2: MaxSize - 1,
	}
}
//打印数组
func (d *DoubleStack) Print() {
	fmt.Println(d.Data)
}

栈操作

//push
func (d *DoubleStack) Push(val int, stackNum int) (bool, error) {
	if d.Top1+1 == d.Top2 {
		return false, fmt.Errorf("空间已经满了")
	}
	if stackNum == 1 {
		d.Data[d.Top1] = val
		d.Top1++
	}
	if stackNum == 2 {
		d.Data[d.Top2] = val
		d.Top2--
	}
	return true, nil
}
//pop
func (d *DoubleStack) Pop(stackNum int) (int, error) {
	if stackNum == 1 {
		if d.Top1 == -1 {
			return 0, fmt.Errorf("栈1已经空了")
		}
		v := d.Data[d.Top1]
		d.Data[d.Top1] = 0
		d.Top1--
		return v, nil
	}
	if stackNum == 2 {
		if d.Top2 == MaxSize-1 {
			return 0, fmt.Errorf("栈2已经空了")
		}
		d.Top2++
		v := d.Data[d.Top2]
		d.Data[d.Top2] = 0
		return v, nil
	}
	return 0, fmt.Errorf("stackNum wrong")
}

测试代码和打印内容

func Test_DoubleStack(t *testing.T) {
	dou := NewDoubleStack()
	dou.Push(1, 1)
	dou.Push(2, 1)
	dou.Push(3, 2)
	dou.Print()
	dou.Pop(1)
	dou.Pop(1)
	dou.Pop(1)
	dou.Pop(2)
	dou.Print()
}
//打印内容
[1 2 0 0 3]
[0 0 0 0 0]
PASS

这种双栈共享空间的结构，一般根据实际情况，不会出现栈满的情况，原因是两个栈是互补的关系。

四，总结

栈这种数据结构就是用来处理需要预存对象的业务场景，有代表性的处理场景就是逆波兰表示