Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
129 lines (101 sloc) 2.58 KB

Go 语言实现栈

现在是时候看看如何使用 Go 语言实现栈了。相关的细节在 stack.go 源文件中。同样,栈的实现也会用到链表。如你所知,你需要两个函数:一个 Push() 函数将元素放入栈中,一个 Pop() 函数从栈中删除元素。单独使用一个变量保存栈中元素的数量是个很实用的方法,这样即使不访问链表也能判断栈是否为空,不过这不是必须的。

stack.go 中的源代码将分四个部分介绍。第一部分如下:

package main

import (
	"fmt"
)

type Node struct {
	Value int
	Next  *Node
}

var size = 0
var stack = new(Node)

stack.go 的第二部分包含了 Push() 函数的实现:

func Push(v int) bool {
	if stack == nil {
		stack = &Node{v, nil}
		size = 1
		return true
	}

	temp := &Node{v, nil}
	temp.Next = stack
	stack = temp
	size++
	return true
}

如果栈为空就创建一个新节点(temp)并将它放在当前栈的最前面,然后新节点会成为栈的头节点。这个版本的 Push() 函数永远返回 true。对于存储空间有限的栈,你可以修改一下,在栈将要溢出时返回 false

第三部分包含 Pop() 函数的实现:

func Pop(t *Node) (int, bool) {
	if size == 0 {
		return 0, false
	}

	if size == 1 {
		size = 0
		stack = nil
		return t.Value, true
	}

	stack = stack.Next
	size--
	return t.Value, true
}

stack.go 的第四个代码段如下:

func traverse(t *Node) {
	if size == 0 {
		fmt.Println("Empty Stack!")
		return
	}

	for t != nil {
		fmt.Printf("%d -> ", t.Value)
		t = t.Next
	}
	fmt.Println()
}

由于这里的栈是使用链表实现的,所以也用链表的方式进行遍历。

stack.go 的最后一部分如下:

func main() {

	stack = nil
	v, b := Pop(stack)
	if b {
		fmt.Print(v, " ")
	} else {
		fmt.Println("Pop() failed!")
	}

	Push(100)
	traverse(stack)
	Push(200)
	traverse(stack)

	for i := 0; i < 10; i++ {
		Push(i)
	}

	for i := 0; i < 15; i++ {
		v, b := Pop(stack)
		if b {
			fmt.Print(v, " ")
		} else {
			break
		}
	}
	fmt.Println()
	traverse(stack)
}

如你所见,stack.go 的源代码比 queue.go 的稍微短一点,这主要是因为栈背后的思想比队列更简单。

执行 stack.go 将生成如下输出:

Pop() failed!
100 -> 
200 -> 100 -> 
9 8 7 6 5 4 3 2 1 0 200 100 
Empty Stack!

现在为止,你已经知道了如何使用链表实现哈希表、队列和栈。这些例子会让你意识到,在一般情况下链表对于编程和计算机科学来说是多么的有效和重要!

You can’t perform that action at this time.