栈和队列
#数据结构#栈和队列 2023-12-31

栈和队列

介绍栈和队列的定义以及 Golang 实现。

概念性的东西

栈的定义

栈（Stack）：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。

队的定义

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

队头（Front）：允许删除的一端，又称队首。
队尾（Rear）：允许插入的一端。
空队列：不包含任何元素的空表。

栈(Go)

数组栈的存储结构

1
2
3
type ArrayStack struct {
	stack []interface{} // 栈切片
}

出栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Pop 出栈
func (s *ArrayStack) Pop() interface{} {
	if s.IsStackNil() {
		return nil
	}
	elem := s.stack[0]

	var newStackArr []interface{}
	for i := 1; i < len(s.stack); i++ {
		newStackArr = append(newStackArr, s.stack[i])
	}

	s.stack = newStackArr

	return elem
}

入栈

1
2
3
4
// Push 压栈
func (s *ArrayStack) Push(data interface{}) {
	s.stack = append(s.stack, data)
}

判断栈为空

1
2
3
func (s *ArrayStack) IsStackNil() bool {
	return s.stack == nil
}

获取头元素

1
2
3
4
5
6
func (s *ArrayStack) GetTop() interface{} {
	if s.IsStackNil() {
		return nil
	}
	return s.stack[0]
}

懒狗

链表栈差不多

队列和栈也差不多。。。就是先进先出罢了