数据结构-线性表之栈和队列(Golang)

mb5fe190725e8a3 · · 595 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

花了两天时间把栈和队列的基础知识过了一遍,使用Golang改写了栈和队列的基本操作。
数据结构-线性表之栈和队列(Golang)

数据结构-线性表之栈和队列(Golang)

PART
01
栈的定义

栈(stack):只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作。
栈顶(top):线性表允许进行插入和删除的那一端。
栈底(Bottom):固定的,不允许进行元素的插入和删除操作。
空栈:不含任何元素的空表。
数据结构-线性表之栈和队列(Golang)
数据结构-线性表之栈和队列(Golang)

PART
02
栈的基本操作

数据结构-线性表之栈和队列(Golang)

PART
03
栈的顺序存储结构

1.顺序栈的实现
栈的顺序存储称为顺序栈,它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附设一个指针(top)指示当前栈顶的位置,一个指针(base)指示当前栈底位置。
数据结构-线性表之栈和队列(Golang)
栈的顺序存储类型可描述为:

//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
}

【一个重要的图示】
数据结构-线性表之栈和队列(Golang)

【栈的初始化】
栈的初始化几个要点:

  • 栈顶指针和栈底指针相等,即都指向栈底
  • 设置栈的大小
//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
队列的基本操作

数据结构-线性表之栈和队列(Golang)

PART
03
队列的顺序存储

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素,并附设两个指针:队头指针front指向队头元素,队尾指针rear指向队尾元素的下一个位置(不同教材对front和rear的定义可能不同,例如,可以让rear指向队尾元素、front指向队头元素。对于不同的定义,出队入队的操作是不同的)。
数据结构-线性表之栈和队列(Golang)
队列的顺序存储类型描述:

//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数组中依然存在可以存放元素的空位置,所以是一种“假溢出”。
针对"假溢出"现象,引入循环队列,因此我们的操作基本上就是针对循环队列来实现的。

数据结构-线性表之栈和队列(Golang)循环队列数据结构-线性表之栈和队列(Golang)

将顺序队列臆造为一个环状的空间,即把存储队列元素的表从逻辑上视为一个环,称为循环队列。当队首指针Q.front=MaxSize-1后,再前进一个位置就自动到0,这可以利用除法取余运算(%)来实现。
数据结构-线性表之栈和队列(Golang)
数据结构-线性表之栈和队列(Golang)
这部分内容较杂,我直接引用教材截图哈,见谅
数据结构-线性表之栈和队列(Golang)

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

//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
  // }

}

数据结构-线性表之栈和队列(Golang)

END

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


有疑问加站长微信联系(非本文作者)

本文来自:51CTO博客

感谢作者:mb5fe190725e8a3

查看原文:数据结构-线性表之栈和队列(Golang)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

595 次点击  
加入收藏 微博
3 回复  |  直到 2021-01-23 13:43:48
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传