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