花了两天时间把栈和队列的基础知识过了一遍，使用Golang改写了栈和队列的基本操作。

7cc170ae859de1deedc3323dcdf75b8c.png

ab3a3d31d1cec85e8137c642296e9d20.png

栈

PART

01

栈的定义

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

    栈顶(top)：线性表允许进行插入和删除的那一端。

    栈底(Bottom)：固定的，不允许进行元素的插入和删除操作。

    空栈：不含任何元素的空表。

a23c913864c317612f95ae46179afd0d.png

abf929041fed17c1346fcec1cb6e2bd5.png

PART

02

栈的基本操作

c679598cac47377ff3cc419f1459d6c3.png

PART

03

栈的顺序存储结构

    1.顺序栈的实现

        栈的顺序存储称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针(top)指示当前栈顶的位置，一个指针(base)指示当前栈底位置。

093da6cbbae9f513c4c3ea675342c29f.png

        栈的顺序存储类型可描述为：

//C语言描述typedef struct{    Elemtype data[maxsize];   //存放栈中元素    int top;                  //栈顶指针    int base;                  //栈底指针} SqStack;//Golang描述//SqStack struct//定义顺序栈的类型,假设类型为inttype SqStack struct {  //顺序栈的元素  data []int  //栈顶指针  top int  //栈底指针  base int  //最大个数  maxSize int}

【一个重要的图示】

abef381c01bab481f86b0539933407d0.png

【栈的初始化】

    栈的初始化几个要点：

  •  栈顶指针和栈底指针相等，即都指向栈底

  • 设置栈的大小

//InitStack function is initnial stack//初始化顺序栈,传入InitSize定义当前数据个数,最大个数设置为40func 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 mainimport "fmt"//SqStack struct//定义顺序栈的类型type SqStack struct {  //顺序栈的元素  data []int  //栈顶指针  top int  //栈底指针  base int  //最大个数  maxSize int}//InitStack function is initnial stack//初始化顺序栈,传入InitSize定义当前数据个数,最大个数设置为40func 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

队列的基本操作

104e6e534f647a1a59546c54d6ce29ff.png

PART

03

队列的顺序存储

    队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置(不同教材对front和rear的定义可能不同，例如，可以让rear指向队尾元素、front指向队头元素。对于不同的定义，出队入队的操作是不同的)。

e52fd4ef64479267ad9fff278486cdd5.png

队列的顺序存储类型描述：

//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数组中依然存在可以存放元素的空位置，所以是一种“假溢出”。

    针对"假溢出"现象，引入循环队列，因此我们的操作基本上就是针对循环队列来实现的。

5b6cd14fb7e7c749017f88ced6b82935.png

循环队列

30e558dbf4ed78ee20f08b3affd2fe10.png

    将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针Q.front=MaxSize-1后，再前进一个位置就自动到0，这可以利用除法取余运算(%)来实现。

4c41b28cdf5362c8d500a294c32fe971.png

001ba212f456b91b482cbcb34484b49c.png

这部分内容较杂，我直接引用教材截图哈，见谅

f6366a9ea13395714c6ecd590651ed74.png

    关于循环队列的操作，只要理解了栈的相关操作，那么队列实现起来还是比较容易的，只是要注意下队满和队空的条件。所以我就直接将全部代码展示出来了，如下。大家注意的是，对队首和队尾指针的不同理解代码是有区别的

//golang实现队列基本操作package mainimport (  //"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  // }  }

bf32d897883f55de351ec0910901ffb3.png

END

    栈和队列的基本知识就总结到这里，有一个点就是关于栈和队列的链式存储结构这里我没有总结，我希望大家是必须要学习的，链式存储结构其实只要把链表的操作掌握了，针对链式存储结构以及两者的基本操作就不在话下了，毕竟栈和队列本质上就是一种受限的线性表。