Http/TCP 基础协议

请求头

1
2
3
4
方法+空格+URI+空格+协议版本\r\n
首部字段\r\n
\r\n
主体

如:

1
2
3
4
5
post /api/v1/register http/1.1
Host: firmeve.com
Connection: keep-alive
Content-Type: application/json
{"name":"simon","mobile":""}

响应头

1
2
3
4
协议版本+空格+状态码+状态描述\r\n
首部字段\r\n
\r\n
主体

阅读更多

Golang RabbitMQ demo

AMQP协议

AMQP(Advanced Message Queuing Protocol,高级消息队列协议)是一个进程间传递异步消息的网络协议。

RabbitMQ 就是 amqp 协议的Erlang的实现。

AMQP的模型架构的主要角色,生产者、消费者、交换器、队列。

生产者、消费者、服务节点

  • 生产者(Producter) 消息投递方
  • 消费者(Consumer) 消息接收方
  • 服务节点(Broker) 消息的服务节点,基本上可以简单的把一个broker看成一台消息服务器

    阅读更多

Mysql8下GTID复制

简述

之前介绍了通过binlog Pos来进行主从复制,基于复制点(pos)来进行复制,在迁移或因故障未能及时同步
等问题下必须重新定位复制点,非常麻烦,特别是对于多台mysql而言。而GTID就可以很好的解决这个问题。
GTID自动检测二进制日志的位置。

什么是GTID?

全局事务标识符(Global Transaction Identifier, GTID )是在程序中创建的唯一标识符,并与主库上提交的每个事务相关联。
此标识符是唯一的,不仅在其主库上,在给定的复制设置中的所有数据库上,它都是唯一的。
所有事务和所有GTID之间都是一对一的映射关系。
GTID用一对坐标表示,用冒号(:)分隔:

1
GTID = source_id:transaction_id

source_id是主库的标识。通常,服务器的server_uuid选项就代表此标识。transaction_id 是一个序列号,由在该服务器上提交事务的顺序决定。

主要步骤

  1. master 开启binlog
  2. 创建复制用户
  3. 设置 master 以及 slave 惟一的server_id,gtid_mode,enforce_gtid_consistency
  4. 在 slave 上执行change master to MASTER_AUTO_POSITION=1
  5. 执行start slave

完整示例

开启3台mysql,分别命令为master,slave,slave2,初始配置如下:
其中slave2我们使用延时同步,主要是为了更好的灾备。

master:

1
2
3
4
5
[mysqld]
skip-host-cache
skip-name-resolve

[mysql]

slave:

1
2
3
4
5
[mysqld]
skip-host-cache
skip-name-resolve

[mysql]

slave2:

1
2
3
4
5
[mysqld]
skip-host-cache
skip-name-resolve

[mysql]

运行Mysql

1
2
3
4
5
6
7
8
docker run -d -it -v /tmp/mysql/master/conf:/etc/mysql/conf.d -v /tmp/mysql/slave/data:/var/lib/mysql -e MYSQL_ROOT_PASSWORD=root --name master mysql
docker run -d -it -v /tmp/mysql/slave/conf:/etc/mysql/conf.d -v /tmp/mysql/master/data:/var/lib/mysql -e MYSQL_ROOT_PASSWORD=root --name slave mysql
docker run -d -it -v /tmp/mysql/slave2/conf:/etc/mysql/conf.d -v /tmp/mysql/slave2/data:/var/lib/mysql -e MYSQL_ROOT_PASSWORD=root --name slave2 mysql
# 创建桥接网络
docker network create mysql
docker network connect --alias master mysql master
docker network connect --alias slave mysql slave
docker network connect --alias slave2 mysql slave2

docker ps查看保证mysql都已经启动,然后增加binlog和gtid的配置

master:

1
2
3
4
log_bin=/var/lib/mysql/bin_logs/master
server_id=100
gtid_mode=on
enforce_gtid_consistency=on

slave:

1
2
3
4
log_bin=/var/lib/mysql/bin_logs/slave
server_id=101
gtid_mode=on
enforce_gtid_consistency=on

slave2:

1
2
3
4
log_bin=/var/lib/mysql/bin_logs/slave
server_id=103
gtid_mode=on
enforce_gtid_consistency=on

在master上增加复制帐户

1
2
3
create user 'binlog_user'@'%' identified with mysql_native_password by 'binlog_password';
grant replication slave on *.* to 'binlog_user'@'%';
flush privileges;

重启master和slave

1
2
3
docker restart master
docker restart slave
docker restart slave2

在slave中增加change master tostart slave

1
2
change master to master_host='master',master_user='binlog_user',master_password='binlog_password',master_port=3306,master_auto_position=1;
start slave;

在slave中增加change master tostart slave并开启延时

1
2
change master to master_host='master',master_user='binlog_user',master_password='binlog_password',master_port=3306,master_auto_position=1,master_delay=10;
start slave;

这里注意,master_delay=10表示开启了10秒延时

查看slave和master状态

1
show master status\G;

binlog

1
show slave status\G;

可以看到slave的Slave_IO_State: Waiting for master to send event
binlog

测试

在主库中创建数据库并写入数据

1
2
3
4
5
6
7
8
create database tv default charset utf8mb4 collate utf8mb4_unicode_ci;
create table t1 (
id int(10) unsigned primary key auto_increment,
content text default null
);
#写入数据
use tv;
insert into t1(content) values('1'),('2'),('3'),('4');

结果

登录slave和slave2分别查看可以看到,数据已经同步,其中slave2是延时同步,也已经生效。
binlog
binlog

最后

master正常写入数据
重启slave和slave2随后也是可以正常同步的

如果希望从库重启后不进行自动同步,需要在配置中增加skip_slave_start
还要注意的是,这里的示例是全部新库,如果原来是使用pos位置同步这里并不完全适用
需要先设置master为read only,等待所有从库全部同步完成才可以进行切换

Mysql8下主从复制、主主复制、多源复制

简述

复制的原理如下:在主库上执行的所有DDLDML语句都会被记录到二进制日志中,也就是binlog
这些日志由连接到它的从库提取。它们只是被复制到从库,并被保存为中继日志。这个过程由IO线程的线程负责。还有一个SQL线程,它按顺序执行中继日志中的语句。

主要步骤

不管是主主,还是多源,其基础配置都和主从差不多,所以就列出主从的基本步骤:

  1. master 开启binlog
  2. 创建复制用户
  3. 设置 master 以及 slave 惟一的server_id
  4. 在 slave 上执行change master to
  5. 执行start slave

主从复制

增加binlog配置

如果不想要自定义配置,先看下系统是否开启了binlog即可

1
show variables like '%log_bin%'

binlog

增加或修改binlog配置,一同增加server_id

1
2
3
4
5
6
[mysqld]
log-bin=/var/lib/mysql/bin_logs/master
expire_logs_days=7
max_binlog_size=1GB

server_id=1

其它更多binlog配置请参考官方文档

查看binlog其它配置

1
SHOW VARIABLES LIKE '%binlog%';

binlog

查看所有binlog及大小

1
show master logs(或者 show binary logs)

binlog

查看当前最新binlog位置

1
show master status;

binlog

查看binlog所有位置及其它信息

1
show binlog events;

binlog

移至下一个日志(开启新日志)

1
flush logs;

binlog

创建复制用户

1
2
3
create user 'binlog_user'@'%' identified with mysql_native_password by 'binlog_password';
grant replication slave on *.* to 'binlog_user'@'%';
flush privileges;

需要的权限以及连接的服务器请自行修改

修改slave配置,增加server_id

1
2
[mysqld]
server_id=100

在slave中执行change master to

1
change master to master_host='172.22.0.2',master_user='binlog_user',master_password='binlog_password',master_log_file='master.000013',master_log_pos=155

如果配置增加未修改的话,请重启master和slave

开启复制

1
start slave

主主复制

binlog
所谓主主复制,其实就是一台mysql既是主又是从,两台互为复制
需要新建一台mysql和从库开启方式一致,原主服务器再加上

1
2
CHANGE MASTER TO MASTER HOST, MASTER USER,MASTER PASSWORD,MASTER LOG FILE,MASTER LOG POS
start slave

多源复制

binlog
多游、复制可用于将多台服务器备份到单台服务器,合并表分片,以及将多台服务器中的数据整合到单台服务器。多源复制在应用事务时不会执行任何冲突检测或解析,并且如果需要的话,这些任务将留给应用程序来处理。在多源复制拓扑中,从库为每个主库创建一个复制通道,以便从中接收事务。

在slave上修改配置文件:

1
2
master_info_repository=TABLE
relay_log_info_repository=TABLE

如果此时从库还在同步,也需要修改

1
2
3
stop slave; 
SET GLOBAL master_info_repository='TABLE';
SET GLOBAL relay_log_info_repository='TABLE';

重启slave即可

注意:多源复制下,多主对一从,需要注意复制数据冲突问题

Golang Ioc容器

简介

用惯了LaravelIoc,对象获取变得那么自然,初用Go,各struct,func都要自己解析
一堆NewFunc,索性自己搞了个ioc
参见Github(https://github.com/firmeve/firmeve)

对象绑定

1
f := NewFirmeve()

标量绑定

1
f.Bind(`bool`, false)
1
f.Bind(`string`, "string")

Struct 绑定

假设我们有如下struct

1
2
3
4
5
6
7
type Foo struct {
Bar string
}

func NewFoo(bar string) Foo{
return Foo{Bar:bar}
}

我们将foo绑定进我们的容器中

1
f.Bind(`foo`,NewFoo("abc"))

Prt 绑定

绑定prtstruct类型是我们最常用的一种方式,请看下面的示例

1
2
3
4
5
6
7
8
9
type Baz struct {
Baz string
}

func NewBaz() *Baz {
return &Baz{}
}

f.Bind(`baz`, NewBaz())

函数绑定

1
2
3
4
5
func NewFoo() Foo{
return Foo{Bar:"default string"}
}

f.Bind(`foo`, NewFoo)

使用Firmeve在绑定的时候暂时不支持参数注入
注意:如果是非函数类型绑定,则会默认为单实例类型

已绑定值覆盖

我们通过WithBindCover(true)方法可以轻松设定覆盖参数

1
2
3
4
f.Bind(`bool`, false)
fmt.Printf("%t",f.Get(`bool`))
f.Bind(`bool`, true, WithBindCover(true))
fmt.Printf("%t",f.Get(`bool`))

对象获取

验证对象是否存在

在不确定容器中是否包含此对象时,请使用Has方法进行判断

1
f.Has(`foo`)

对象获取

直接获取容器中的值

1
f.Get(`foo`)

注意:如果指的定的key不存在,则会抛出panic错误

新对象获取

1
2
3
4
5
6
7
8
func NewFoo() Foo{
return Foo{Bar:"default string"}
}

f.Bind(`foo`, NewFoo)
fmt.Printf("%p\n",f.Get("foo"))
fmt.Printf("%p\n",f.Get("foo"))
fmt.Printf("%p\n",f.Get("foo"))

Firmeve中,如果需要每次重新得到一个新的结构体对象
必须绑定一个函数值,否则得到的将是一个单实例

单例获取

1
2
3
4
5
6
7
8
func NewFoo() Foo{
return Foo{Bar:"default string"}
}

f.Bind(`foo`, NewFoo())
fmt.Printf("%p\n",f.Get("foo"))
fmt.Printf("%p\n",f.Get("foo"))
fmt.Printf("%p\n",f.Get("foo"))

参数解析

函数自动解析

让我们来看一个简单的示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
type PersonName struct {
Name string
}

func NewPersonName() PersonName {
return PersonName{Name: "Firmeve"}
}

type PersonAge struct {
Age int
}

func PersonAge() *PersonAge {
return &PersonAge{Age: 1}
}

type Person struct {
name PersonName
age *PersonAge
}

func NewPerson(name PersonName,age *PersonAge) *NewPerson {
return NewPerson{
name: name
age: age
}
}

f.Bind("PersonName", NewPersonName)
f.Bind("PersonAge", PersonAge)
fmt.Printf("%#v", f.Resolve(NewPerson))

结构体tag自动解析

现在,让我们修改下上面的Person

1
2
3
4
5
type Person struct {
Name PersonName `inject:"PersonName"`
Age *PersonAge `inject:"PersonAge"`
age1 *PersonAge `inject:"PersonAge"`
}

然后我们使用new函数直接创建一个新的结构体指针

1
fmt.Printf("%#v", new(NewPerson))

注意:此时 Person中的Name字段并不是指针类型,而age1不符合structtag规范,所以Firmeve都会自动忽略。

Redis基础数据类型和常用操作命令

简述

经常用的都是通过代码包装好的redis调用程式,时间有些常用命令又模糊了,故拿出来记录下。

基础数据类型

String

Add|Set

  • SET key value [EX seconds|PX milliseconds] [NX|XX] NX:相当于SETNX值不存在时增加,XX值存在覆盖
  • MSET key value key value ... 一次设置多个值
  • SETNX key value 原子性操作,当key不存在设置成功返回1,否则返回0
  • STRLEN key 返回key的长度,不存在返回0,非string类型返回错误
  • APPEND key value 在key的末尾追加字符串,返回字符串长度,原来的key不存在,则会增加(相当于SET)
  • SETRANGE key offset value 替换字符串,从offset下标开始,替换strlen(value)位字符串

Get

  • EXISTS key ... 判断key是否存在,返回存在key的个数,单个key不存在返回0
  • GET key 获取key值
  • MGET key ... 获取多个key的值

Delete

  • DEL key ... 删除指定key,成功返回删除个数

string类型在redis中有三种存储方式

  • int 64位有符号位整数
  • embstr 长度小于44个字节的字符串
  • raw 长度大于44个字节的字符串
    其中raw效率相对最差,可以通过 OBJECT ENCODING key的命令来查看string的存储类型

List

Add|Set

  • LPUSH key value ... 左侧写入返回总列表个数
  • RPUSH key value ... 右侧写入返回总列表个数
  • LINSERT key [BEFORE|AFTER] item value 从左侧开始,指定元素(item)前或后插入新元素,返回总列表个数
  • LSET key index 覆盖或增加指定索引的值,返回OK,超过最大list范围则会报错

Get

  • LRANGE key start stop 获取指定范围的list, lrange key 0 -1 标识获取整个list
  • LINDEX key index 获取指定索引处的元素,不存在返回nil
  • LLEN key 获取列表长度

Delete

  • LPOP key 左侧弹出,返回总列表个数,当list不存在时返回nil
  • RPOP key 右侧弹出,返回总列表个数,当list不存在时返回nil
  • LTRIM key start stop 删除指定区间外的元素,返回OK
  • BLPOP key LPOP阻塞式方法
  • BRPOP key RPOP阻塞式方法

Hash

类似于Go中的mapPHP中的键值数组,用于存储字段的映射关系

Add|Set

  • HMSET key field value ... 成功返回 OK
  • HSET key field value ... 增加field时返回新增field值的个数,覆盖时返回0(覆盖成功也是0)
  • HSETNX key field value 当field不存在时增加成功返回1,如果field存则返回0,不可同时进行多个field操作

Get

  • HKEYS key 返回当前hash中所有的field
  • HEXISTS key field 判断当前key中是否存在field,存在返回1,否则返回0
  • HGETALL key 返回当前Key的所有值,当HASH巨大的时候不适合使用此函数
  • HMGET key field ... 返回当前key指定的field值
  • HSCAN key cursor [MATCH field] [COUNT number] 通过指针移动来获取MATCH匹配的值,COUNT代表的是返回的元素个数,但即使设置了count也并不一定代表就返回count个元素,因此不可作为分页式数据
  • HLEN key 获取Hash长度

Delete

  • HDEL key field ... 删除一个或多个field,当key全部删除后,key会被自动清除

Set

Add|Set

  • SADD key member ... 添加集合元素,返回添加的的元素数量

Get

  • SISMEMBER key member 判断是否存在于集合,0表示不存在1存在
  • SMEMBERS key 返回集合所有元素
  • SSCAN key cursor [MATCH member] [COUNT number] 通过指针移动来获取MATCH匹配的值,COUNT代表的是返回的元素个数,但即使设置了count也并不一定代表就返回count个元素,因此不可作为分页式数据
  • SRANDMEMBER key count 随机返回指定count元素
  • SUNION key key ... 集合并集,返回合并后的值
  • SUNIONSTORE storeKey key key ... 并集,并存储至storeKey中,索引相同则覆盖,返回合并个数
  • SINTER 集合交集,返回合交集值
  • SINTERSTORE storeKey key key ... 交集,并存储至storeKey中
  • SDIFF 集合差集,返回合差集值
  • SDIFFSTORE diffKey key key ... 差集,并存储至diffKey中
  • SCARD key 获取集合元素数量

Delete

  • DEL key 删除集合

Golang 锁的简单使用

简述

Golang中的锁机制主要包含互斥锁和读写锁

互斥锁

互斥锁是传统并发程序对共享资源进行控制访问的主要手段。在Go中主要使用
sync.Mutex的结构体表示。

一个简单的示例:

1
2
3
4
5
6
func mutex()  {
var mu sync.Mutex
mu.Lock()
fmt.Println("locked")
mu.Unlock()
}

或者也可以使用defer来实现,这在整个函数流程中全部要加锁时特别有用,还有一个好处就是可以防止忘记Unlock

1
2
3
4
5
6
func mutex()  {
var mu sync.Mutex
mu.Lock()
defer mu.Unlock()
fmt.Println("locked")
}

互斥锁是开箱即用的,只需要申明sync.Mutex即可直接使用

1
var mu sync.Mutex

互斥锁应该是成对出现,在同步语句不可以再对锁加锁,看下面的示例:

1
2
3
4
5
6
7
8
9
func mutex()  {
var mu sync.Mutex
mu.Lock()
fmt.Println("parent locked")
mu.Lock()
fmt.Println("sub locked")
mu.Unlock()
mu.Unlock()
}

此时则会出现fatal error: all goroutines are asleep - deadlock!错误

同样,如果多次对一个锁解锁,则会出现fatal error: sync: unlock of unlocked mutex错误

1
2
3
4
5
6
7
func mutex()  {
var mu sync.Mutex
mu.Lock()
fmt.Println("locked")
mu.Unlock()
mu.Unlock()
}

那么在goroutine中是否对外部锁加锁呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func mutex()  {
var mu sync.Mutex
fmt.Println("parent lock start")
mu.Lock()
fmt.Println("parent locked")
for i := 0; i <= 2; i++ {
go func(i int) {
fmt.Printf("sub(%d) lock start\n", i)
mu.Lock()
fmt.Printf("sub(%d) locked\n", i)
time.Sleep(time.Microsecond * 30)
mu.Unlock()
fmt.Printf("sub(%d) unlock\n", i)
}(i)
}
time.Sleep(time.Second * 2)
mu.Unlock()
fmt.Println("parent unlock")
time.Sleep(time.Second * 2)
}

先看上面的函数执行结果

1
2
3
4
5
6
7
8
9
10
11
12
parent lock start
parent locked
sub(0) lock start
sub(2) lock start
sub(1) lock start
parent unlock // 必须等到父级先解锁,后面则会阻塞
sub(0) locked // 解锁后子goroutine才能执行锁定
sub(0) unlock
sub(2) locked
sub(2) unlock
sub(1) locked
sub(1) unlock

为了方便调试,使用了time.Sleep()来延迟保证goroutine的执行
从结果中可以看出,当所有的goroutine遇到Lock时都会阻塞,而当main函数中的Unlock执行后,会有一个优先(无序)的goroutine来占得锁,其它的则再次进入阻塞状态。

总结:

  • 互斥锁必须成对出现
  • 同级别互斥锁不能嵌套使用
  • 父级中如果存在锁,当在goroutine中执行重复锁定操作时goroutine将被阻塞,直到原互斥锁解锁,多个goroutine将会争抢当前锁资源,其它继续阻塞。

读写锁

读写锁和互斥锁不同之处在于,可以分别针对读操作和写操作进行分别锁定,这样对于性能有一定的提升。
读写锁,对于多个写操作,以及写操作和读操作之前都是互斥的这一点基本等同于互斥锁。
但是对于同时多个读操作之前却非互斥关系,这也是相读写锁性能高于互斥锁的主要原因。

读写锁也是开箱即用型的

1
var rwm = sync.RWMutex

读写锁分为写锁和读锁:

  • 写锁定和写解锁

    1
    2
    rwm.Lock()
    rwm.Unlock()
  • 读锁定和读解锁

    1
    2
    rwm.RLock()
    rwm.RUnlock()

读写锁的读锁和写锁不能交叉相互解锁,否则会发生panic,如:

1
2
3
4
5
6
7
func rwMutex()  {
var rwm sync.RWMutex

rwm.Lock()
fmt.Println("locked")
rwm.RUnlock()
}

fatal error: sync: RUnlock of unlocked RWMutex

对于读写锁,同一资源可以同时有多个读锁定,如:

1
2
3
4
5
6
7
8
9
10
11
func rwMutex()  {
var rwm sync.RWMutex

rwm.RLock()
rwm.RLock()
rwm.RLock()
fmt.Println("locked")
rwm.RUnlock()
rwm.RUnlock()
rwm.RUnlock()
}

但对于写锁定只能有一个(和互斥锁相同),同时使用多个会产生deadlockpanic,如:

1
2
3
4
5
6
7
8
9
10
11
func rwMutex()  {
var rwm sync.RWMutex

rwm.Lock()
rwm.Lock()
rwm.Lock()
fmt.Println("locked")
rwm.Unlock()
rwm.Unlock()
rwm.Unlock()
}

goroutine中,写解锁会试图唤醒所有想要进行读锁定而被阻塞的goroutine

而读解锁会在已无任何读锁定的情况下,试图唤醒一个想进行写锁定而被阻塞的goroutine

下面看一个完整示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func rwMutex() {
var rwm sync.RWMutex

for i := 0; i <= 2; i++ {
go func(i int) {
fmt.Printf("go(%d) start lock\n", i)
rwm.RLock()
fmt.Printf("go(%d) locked\n", i)
time.Sleep(time.Second * 2)
rwm.RUnlock()
fmt.Printf("go(%d) unlock\n", i)
}(i)
}
// 先sleep一小会,保证for的goroutine都会执行
time.Sleep(time.Microsecond * 100)
fmt.Println("main start lock")
// 当子进程都执行时,且子进程所有的资源都已经Unlock了
// 父进程才会执行
rwm.Lock()
fmt.Println("main locked")
time.Sleep(time.Second)
rwm.Unlock()
}
1
2
3
4
5
6
7
8
9
10
11
go(0) start lock
go(0) locked
go(1) start lock
go(1) locked
go(2) start lock
go(2) locked
main start lock
go(2) unlock
go(0) unlock
go(1) unlock
main locked

反复执行上述示例中,可以看到,写锁定会阻塞goroutine
最开始先在mainsleep 100ms ,保证子的goroutine会全部执行,而每个子goroutinesleep 2s
此时会阻塞整个main进程,当所有子goroutine执行结束,读解锁后,main的写锁定才会执行。

再看一个读锁定示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func rwMutex5() {
var rwm sync.RWMutex

for i := 0; i <= 2; i++ {
go func(i int) {
fmt.Printf("go(%d) start lock\n", i)
rwm.RLock()
fmt.Printf("go(%d) locked\n", i)
time.Sleep(time.Second * 2)
rwm.RUnlock()
fmt.Printf("go(%d) unlock\n", i)
}(i)
}

fmt.Println("main start lock")
rwm.RLock()
fmt.Println("main locked")
time.Sleep(time.Second * 10)
}
1
2
3
4
5
6
7
8
9
10
11
main start lock
main locked
go(1) start lock
go(1) locked
go(2) start lock
go(2) locked
go(0) start lock
go(0) locked
go(0) unlock
go(1) unlock
go(2) unlock

可以看到读锁定却并不会阻塞goroutine

总结:

  • 读锁定和写锁定对于写操作都是互斥的
  • 读锁定支持多级嵌套,但写锁定无法嵌套执行
  • 如果有写锁定,当多个读解锁全部执行完成后,则会唤起执行写锁定
  • 写锁定会阻塞goroutine(在Lock()时和互斥锁一样,RLock()时先也是等到RUnlock()先执行,才有锁定机会)

单向链表优化

说明

Golang 单向链表 中是通过不断修改next来实现链表
本章通过一个虚拟head方法来优化链表,其原理就是,创建时直接创建headnext,head第一个值始终是nil
通过headnext来作为初始值,并且对原有链表进行相关优化

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
type node struct {
value interface{}
next *node
}

type LinkedList struct {
dummyHead *node
length int
}

func newNode(value interface{}, next *node) *node {
return &node{
value: value,
next: next,
}
}

func NewLinkedList() *LinkedList {
return &LinkedList{
// 一个虚拟的head value,只使用next
dummyHead: newNode(nil, newNode(nil, nil)),
length: 0,
}
}

// 添加元素
func (l *LinkedList) Add(index int, value interface{}) {
l.checkIndexRange(index)

//移动指针到指定下标
prev := l.dummyHead
for i := 0; i < index; i++ {
// 不断的移动链表指针
// dummyHead 有个虚拟value,其实是从dummyHead的next作为第一个值
prev = prev.next
}

// 每当数据更改时,自动修改其head,移动head头指针(往前增加),而不是直接修改next(不是往后增加)
prev.next = newNode(value, prev.next)
l.length ++
}

// 删除元素
func (l *LinkedList) Delete(index int) interface{} {
l.checkIndexRange(index)

prev := l.dummyHead
var current *node
for i := 0; i <= index; i++ {
// 保存当前值
// dummyHead 有个虚拟value,其实是从dummyHead的next作为第一个值
current = prev.next

// 需要删除的值
if i == index {
if current.next != nil {
// 移除指定索引,移动指针
// 当前值的next就等于当前的next,这样就移除了current
prev.next = current.next
} else {
prev.next = nil
}
} else {
prev = current
}
}

l.length --

return current.value
}

// 通过指定索引获取值
func (l *LinkedList) Index(index int) interface{} {
l.checkIndexRange(index)

prev := l.dummyHead
for i := 0; i <= index; i++ {
prev = prev.next
}

return prev.value
}

// 在链表开头插入值
func (l *LinkedList) Unshift(value interface{}) {
l.Add(0, value)
}

// 在链表结尾插入值
func (l *LinkedList) Push(value interface{}) {
l.Add(l.length, value)
}

// 弹出链表最后一个值
func (l *LinkedList) Pop() interface{} {
return l.Delete(l.length - 1)
}

// 弹出链表第一个值
func (l *LinkedList) Shift() interface{} {
return l.Delete(0)
}

//
func (l *LinkedList) Length() int {
return l.length
}

func (l *LinkedList) checkIndexRange(index int) {
if index < 0 || index > l.length {
panic(`下标越界`)
}
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func TestNewLinkedList(t *testing.T) {
list := NewLinkedList()
list.Add(0,"a")
list.Push("b")
list.Add(2,"c")
list.Add(3,"d")

assert.Equal(t,"a",list.Index(0).(string))
assert.Equal(t,"b",list.Index(1).(string))
assert.Equal(t,"c",list.Index(2).(string))
assert.Equal(t,"d",list.Index(3).(string))

// 中间追加
list.Add(2,"e")

assert.Equal(t,"e",list.Index(2).(string))
assert.Equal(t,"c",list.Index(3).(string))
assert.Equal(t,"d",list.Index(4).(string))
assert.Equal(t,5,list.Length())

assert.Equal(t,"a",list.Index(0).(string))
assert.Equal(t,"b",list.Index(1).(string))
assert.Equal(t,"e",list.Index(2).(string))
assert.Equal(t,"c",list.Index(3).(string))
assert.Equal(t,"d",list.Index(4).(string))


assert.Equal(t,"e",list.Delete(2))
assert.Equal(t,4,list.Length())

assert.Equal(t,"a",list.Index(0).(string))
assert.Equal(t,"b",list.Index(1).(string))
assert.Equal(t,"c",list.Index(2).(string))
assert.Equal(t,"d",list.Index(3).(string))

assert.Equal(t,"d",list.Pop())
assert.Equal(t,3,list.Length())
assert.Equal(t,"a",list.Index(0).(string))
assert.Equal(t,"b",list.Index(1).(string))
assert.Equal(t,"c",list.Index(2).(string))

assert.Equal(t,"a",list.Shift())
assert.Equal(t,2,list.Length())
assert.Equal(t,"b",list.Index(0).(string))
assert.Equal(t,"c",list.Index(1).(string))
}

Golang container/list 实现 简单stack

基础实现方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import "container/list"

type Stack struct {
list *list.List
}

func NewStack() *Stack {
return &Stack{
list: list.New(),
}
}

func (s *Stack) Push(value interface{}) {
s.list.PushBack(value)
}

func (s *Stack) Pop() interface{} {
e := s.list.Back()
if e != nil {
s.list.Remove(e)
return e.Value
}

return nil
}

func (s *Stack) Length() int {
return s.list.Len()
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func TestNewStack(t *testing.T) {
stack := NewStack()
stack.Push("a")
stack.Push("b")
stack.Push("c")
stack.Push("d")
assert.Equal(t,4,stack.Length())
v := stack.Pop()
assert.Equal(t,"d",v.(string))
assert.Equal(t,3,stack.Length())
v = stack.Pop()
assert.Equal(t,"c",v.(string))
assert.Equal(t,2,stack.Length())
v = stack.Pop()
assert.Equal(t,"b",v.(string))
assert.Equal(t,1,stack.Length())
v = stack.Pop()
assert.Equal(t,"a",v.(string))
assert.Equal(t,0,stack.Length())
}

Leetcode刷题之有效的括号#20

题目描述

给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

解题思路

由’(‘,’)’,’{‘,’}’,’[‘,’]’等一一对应,想到的应该是数据栈。

左侧结构的符号入栈,遇到右侧的出栈对比,这样即可一一对应。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func IsValid(s string) bool {
stack := make([]string, 0)
for _,v := range strings.Split(s,``) {
if v == `{` || v == `[` || v == `(` {
stack = append(stack, v)
} else {
var sv string
if len(stack) == 0 {
return false
} else if len(stack) == 1 {
sv = stack[0]
stack = stack[0:0]
} else {
sv = stack[len(stack)-1]
stack = stack[:len(stack)-1]
}

if sv == `{` && v != `}`{
return false
} else if sv == `[` && v != `]` {
return false
} else if sv == `(` && v != `)`{
return false
}
}
}

return len(stack) == 0
}

测试

1
2
3
4
5
6
func TestIsValid(t *testing.T) {
assert.Equal(t,false,IsValid("{}{{{{]}}"))
assert.Equal(t,true,IsValid("{}()[]"))
assert.Equal(t,true,IsValid("[{{{}}}]"))
assert.Equal(t,true,IsValid("{([])}"))
}