花了两天时间把栈和队列的基础知识过了一遍，使用Golang改写了栈和队列的基本操作。
栈
PART
01
栈的定义
栈(stack)：只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。
栈顶(top)：线性表允许进行插入和删除的那一端。
栈底(Bottom)：固定的，不允许进行元素的插入和删除操作。
空栈：不含任何元素的空表。
PART
02
栈的基本操作
PART
03
栈的顺序存储结构
1.顺序栈的实现
栈的顺序存储称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针(top)指示当前栈顶的位置，一个指针(base)指示当前栈底位置。
栈的顺序存储类型可描述为：
//C语言描述
typedef struct{
Elemtype data[maxsize]; //存放栈中元素
int top; //栈顶指针
int base; //栈底指针
} SqStack;
//Golang描述
//SqStack struct
//定义顺序栈的类型,假设类型为int
type SqStack struct {
//顺序栈的元素
data []int
//栈顶指针
top int
//栈底指针
base int
//最大个数
maxSize int
}【一个重要的图示】
【栈的初始化】
栈的初始化几个要点：
- 栈顶指针和栈底指针相等，即都指向栈底
- 设置栈的大小
//InitStack function is initnial stack
//初始化顺序栈,传入InitSize定义当前数据个数,最大个数设置为40
func InitStack(InitSize int) *SqStack {
return &SqStack{data: make([]int, InitSize), maxSize: 40}
}【栈是否为空】
判断条件：s.base == s.top
//StackEmpty method to know is stackempty
//判断是否空
func (s *SqStack) StackEmpty() bool {
if s.base == s.top { //栈顶指针和栈底指针相等
return true
}
return false
}【栈的长度】
求栈的长度可使用栈顶指针减去栈底指针
//StackLength method is getting length
//求顺序栈长度,直接使用栈顶指针减去栈底指针,得到指针相隔多少就是元素个数
func (s *SqStack) StackLength() int {
if s.base == s.top { //判断是否为空
return 0
}
return s.top - s.base
}【清空栈】
//Clear method is clearing elements
//清空栈,直接把栈顶指针移到栈底即可,注意只是清空,栈在内存中还是存在的，忽略里面到底存了什么。
//清空栈的意思就是栈顶指针和栈底指针都指向栈底,代表里面没有元素了
func (s *SqStack) Clear() bool {
if s.base == s.top { //判空
return true
}
s.top = s.base
return true
}【压栈操作】
压栈操作就是将一个元素从栈顶入栈，即将当前栈顶位置元素赋值为e，然后将栈顶指针向上移动一个位置
//Push method is pushing an element into stack
//压栈操作,将一个元素入栈,向上移动指针
func (s *SqStack) Push(e int) bool {
if s.top-s.base == s.maxSize {
return false
}
s.data[s.top] = e
s.top++
return true
}【出栈操作】
出栈操作很简单就是把栈顶指针向下移动即可，可以用一个变量来接收被弹出栈的元素
//Pop function is pop top element
//弹栈操作,将栈顶元素弹出
func (s *SqStack) Pop() bool {
if s.base == s.top {
return false
}
// x = s.data[s.top] //接收栈顶被弹出的元素
s.top-- //可以使用for循环(参考遍历的循环),将所有元素都弹出
return true
}【读取栈顶元素】
读栈顶元素就是返回栈顶指针的元素
//GetElem is get top element
//读取栈顶元素
func (s *SqStack) GetElem() int {
if s.base == s.top {
return -1
}
x := s.data[s.top]
return x
}【遍历栈元素】
//Traverse function is get all elements
//遍历栈元素
func (s *SqStack) Traverse() {
for s.top != s.base {
fmt.Println(s.data[s.top]) //不为空时，循环得到栈顶元素
s.top-- //栈顶指针下移获得下个元素
}
}PART
04
代码改写
//golang实现栈的基本操作
package main
import "fmt"
//SqStack struct
//定义顺序栈的类型
type SqStack struct {
//顺序栈的元素
data []int
//栈顶指针
top int
//栈底指针
base int
//最大个数
maxSize int
}
//InitStack function is initnial stack
//初始化顺序栈,传入InitSize定义当前数据个数,最大个数设置为40
func InitStack(InitSize int) *SqStack {
return &SqStack{data: make([]int, InitSize), maxSize: 40, top: 0, base: 0}
}
//StackEmpty method to know is stackempty
//判断是否空
func (s *SqStack) StackEmpty() bool {
if s.base == s.top { //栈顶指针和栈底指针相等
return true
}
return false
}
//StackLength method is getting length
//求顺序栈长度,直接使用栈顶指针减去栈底指针,得到指针相隔多少就是元素个数
func (s *SqStack) StackLength() int {
if s.base == s.top {
return 0
}
return s.top - s.base
}
//Clear method is clearing elements
//清空栈,直接把栈顶指针移到栈底即可,注意只是清空,栈在内存中还是存在的，并且忽略里面到底存了什么。
//清空栈的意思就是栈顶指针和栈底指针都指向栈底,代表里面没有元素了
func (s *SqStack) Clear() bool {
if s.base == s.top {
return true
}
s.top = s.base
return true
}
//Push method is pushing an element into stack
//压栈操作,将一个元素入栈,向上移动指针
func (s *SqStack) Push(e int) bool {
if s.top-s.base == s.maxSize {
return false
}
s.data[s.top] = e
s.top++
return true
}
//Pop function is pop top element
//弹栈操作,将栈顶元素弹出
func (s *SqStack) Pop() bool {
if s.base == s.top {
return false
}
// x = s.data[s.top]
s.top-- //可以使用for循环(参考遍历的循环),将所有元素都弹出
return true
}
//GetElem is get top element
//读取栈顶元素
func (s *SqStack) GetElem() int {
if s.base == s.top {
return -1
}
x := s.data[s.top]
return x
}
//Traverse function is get all elements
//遍历栈元素
func (s *SqStack) Traverse() {
for s.top != s.base {
fmt.Println(s.data[s.top])
s.top--
}
}
func main() {
S := InitStack(10)
S.Push(12)
S.Push(1212)
S.Push(1242)
S.Push(212)
S.Push(12345)
fmt.Println("栈底位置", S.base)
fmt.Println("栈顶位置", S.top)
fmt.Println("当前栈元素个数", S.StackLength())
S.Pop()
fmt.Println("栈顶元素", S.GetElem())
fmt.Println(S.StackLength())
fmt.Printf("S.top的类型%T", S.top)
fmt.Println()
S.Traverse()
}队列
PART
01
队列的定义
队列(Queue)：队列简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。最重要的操作即入队和出队，其操作特性是先进先出，故又称为先进先出的线性表。
队头(Front)：允许删除的一端，又称队首。
队尾(Rear)：允许插入的一端。
空队列：不含任何元素的空表。
PART
02
队列的基本操作
PART
03
队列的顺序存储
队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置（不同教材对front和rear的定义可能不同，例如，可以让rear指向队尾元素、front指向队头元素。对于不同的定义，出队入队的操作是不同的）。
队列的顺序存储类型描述：
//C语言描述
#define MaxSize 50
typedef struct{
ElemType data[MaxSize]; //存放的元素
int front, rear; //队首队尾指针
}
//golang实现
//SqQueue struct
//顺序队列的结构,但实际上是循环队列
type SqQueue struct{
data [10]int //定义有20个元素的整型数组作为队列元素
front int //队首指针
rear int //队尾指针
maxSize int
}图3 .6(a）所示为队列的初始状态，有Q.front==Q.rear==0成立，该条件可以作为队列判空的条件。但能否用Q.rear==MaxSize作为队列满的条件呢？显然不能，图3.6(d）中，队列中仅有一个元素，但仍满足该条件。这时入队出现“上溢出”，但这种溢出并不是真正的监出，在data数组中依然存在可以存放元素的空位置，所以是一种“假溢出”。
针对"假溢出"现象，引入循环队列，因此我们的操作基本上就是针对循环队列来实现的。
循环队列
将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针Q.front=MaxSize-1后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。
这部分内容较杂，我直接引用教材截图哈，见谅
关于循环队列的操作，只要理解了栈的相关操作，那么队列实现起来还是比较容易的，只是要注意下队满和队空的条件。所以我就直接将全部代码展示出来了，如下。大家注意的是，对队首和队尾指针的不同理解代码是有区别的
//golang实现队列基本操作
package main
import (
//"container/list"
"fmt"
)
//SqQueue struct
//顺序队列的结构,但实际上是循环队列
type SqQueue struct{
data [10]int //定义有20个元素的整型数组作为队列元素
front int //队首指针
rear int //队尾指针
maxSize int
}
//InitQueue method to initqueue
//初始化队列,将队首指针和队尾指针指向都指向队尾
func (Q *SqQueue) InitQueue(maxSize int){
Q.front=Q.rear
Q.maxSize=maxSize
}
//isEmpty method to know whether empty
//判断是否为空
func (Q *SqQueue) isEmpty()bool{
if Q.front==Q.rear {
return true
}
return false
}
//EnQueue method is to push element
//将元素从队尾插入队列
func (Q *SqQueue) EnQueue(e int) bool{
if (Q.rear+1)%Q.maxSize==Q.front{
return false
}
Q.data[Q.rear] = e
Q.rear = (Q.rear+1) % Q.maxSize
return true
}
//DeQueue method is
//将元素弹出队列
func (Q *SqQueue) DeQueue()bool{
if Q.front==Q.rear{
return false
}
//x := Q.data[Q.front] //可以使用for循环将弹出元素打印出来
Q.front=(Q.front+1)%Q.maxSize
return true
}
//Traverse method is get all elements
//遍历所有元素
func (Q *SqQueue) Traverse() {
for Q.front!=Q.rear{
x:=Q.data[Q.front]
Q.front++
fmt.Println(x)
}
}
//GetLength method
//求队列元素个数(队列长度)
func (Q *SqQueue) GetLength() int{
return (Q.rear-Q.front+Q.maxSize)%Q.maxSize
}
//GetHead method to GetHead element
//获取队头元素
func (Q *SqQueue) GetHead() int{
if Q.front!=Q.rear{
return Q.data[Q.front]
}
return -1
}
func main(){
var queue SqQueue
queue.InitQueue(20)
queue.EnQueue(12)
queue.EnQueue(22)
queue.EnQueue(32)
//queue.Traverse()
// fmt.Println(queue.EnQueue(32))
// fmt.Println(queue.maxSize)
//fmt.Println(queue.isEmpty())
//fmt.Println(queue.DeQueue())
fmt.Println(queue.rear)
fmt.Println(queue.front)
// for queue.front!=queue.rear{ //for循环打印弹出的元素,先进先出
// fmt.Println(queue.data[queue.front])
// queue.front=(queue.front+1)%queue.maxSize
// }
}
END
栈和队列的基本知识就总结到这里，有一个点就是关于栈和队列的链式存储结构这里我没有总结，我希望大家是必须要学习的，链式存储结构其实只要把链表的操作掌握了，针对链式存储结构以及两者的基本操作就不在话下了，毕竟栈和队列本质上就是一种受限的线性表。
