（5）Go实现链表栈
2019-04-17 本文已影响0人
哥斯拉啊啊啊哦
链表在对头节点进行操作时，时间复杂度是O(1)，因此用链表来实现栈是一种不错的方式
// 链表的实现定义和栈的实现定义
type node struct {
Item interface{}
Next *node
}
// 链表
type linkedList struct {
Length int
DummyHead *node //虚拟头节点
//end node
}
func NewNode() *node {
return &node{
Item: nil,
Next: nil,
}
}
func NewLinkedList() *linkedList {
return &linkedList{
Length: 0,
DummyHead: &node{},
}
}
func (l *linkedList) Add(index int, n *node) {
if index < 0 || index > l.Length {
log.Fatal("failed to add, index 超出范围.")
}
prev := l.DummyHead
for i := 0; i < index; i++ {
prev = prev.Next
}
n.Next = prev.Next
prev.Next = n
l.Length++
}
func (l *linkedList) AddFirst(n *node) {
l.Add(0, n)
}
func (l *linkedList) AddLast(n *node) {
l.Add(l.Length-1, n)
}
// 输入index，返回index位节点
func (l *linkedList) Get(index int) (cur *node, err error) {
if index < 0 || index > l.Length {
err = errors.New("failed to traverse, index out of range.")
return nil, err
}
if l.Length == 0 {
log.Fatal("failed to traverse,linkedList is empty.")
}
cur = l.DummyHead //虚拟头节点
for i := 0; i <= index; i++ {
cur = cur.Next //index位节点
}
return cur, nil
}
// 修改index节点
func (l *linkedList) Modify(index int, n *node) {
if index < 0 || index > l.Length {
log.Fatal("failed to modify, index out of range.")
}
if l.Length == 0 {
log.Fatal("failed to traverse,linkedList is empty.")
}
cur, _ := l.Get(index)
cur.Item = n.Item
cur.Next = n.Next
}
func (l *linkedList) ModifyContent(index int, item interface{}) {
if index < 0 || index > l.Length {
log.Fatal("failed to modifyContent, index out of range.")
}
if l.Length == 0 {
log.Fatal("failed to traverse,linkedList is empty.")
}
cur, _ := l.Get(index)
cur.Item = item
}
func (l *linkedList) Delete(index int) error {
if index < 0 || index > l.Length {
return errors.New("failed to delete, index out of range.")
}
prev := l.DummyHead
for i := 0; i < index; i++ {
prev = prev.Next
}
delNode := prev.Next
prev.Next = delNode.Next
delNode = nil
l.Length--
return nil
}
// 查找链表中是否有元素e
func (l *linkedList) Contains(n *node) bool {
if l.Length == 0 {
return false
}
cur := l.DummyHead //虚拟头节点
for i := 0; i <= l.Length-1; i++ {
cur = cur.Next //index位节点
if cur == n {
return true
}
}
return false
}
// 获取链表中所有内容
func (l *linkedList) Traverse() []interface{} {
resp := []interface{}{}
buf := l.DummyHead.Next
for buf != nil {
resp = append(resp, buf.Item, "->")
buf = buf.Next
}
resp = append(resp, nil)
return resp
}
type queue struct {
linkedList
}
func NewQueue() *queue {
return &queue{
linkedList{
Length: 0,
DummyHead: &node{},
},
}
}
func (q *queue) Push(item interface{}) {
buf := &node{
Item: item,
Next: nil,
}
q.AddFirst(buf)
}
func (q *queue) Pop() (item interface{}) {
if q.Length == 0 {
return errors.New(
"error:failed to pop,queue is empty.")
}
cur, _ := q.Get(0)
q.Delete(0)
return cur.Item
}
func (q *queue) Top() (item interface{}) {
if q.Length == 0 {
return errors.New(
"error:failed to top,queue is empty.")
}
cur, _ := q.Get(0)
return cur.Item
}
func (q *queue) Len() int {
return q.Length
}
func (q *queue) IsEmpty() bool {
return q.Length == 0
}
func main() {
q := linked_list2.NewQueue()
q.Push("3")
q.Push("4")
fmt.Println(q.Pop())
fmt.Println(q.Top())
fmt.Println(q.Pop())
fmt.Println(q.Pop())
}
// 测试结果
4
3
3
error:failed to pop,queue is empty.
有bug欢迎指出，转载请注明出处。
