当前位置: 首页 > >

Algorithm1---数组、链表===>栈、队列

发布时间:



文章目录
数组、链表 实现 栈、队列导论链表(Link)循环链表([约瑟夫问题](https://zhuanlan.zhihu.com/p/74436158))双向链表栈 (Stack)最小栈、最小队列、最大栈、最大队列



数组、链表 实现 栈、队列
导论

???????队列可以使用链表或者数组实现,使用链表的优点是扩容简单,缺点是无法通过索引定位元素,使用数组则相反,扩容不容易但是可以通过索引定位元素。


链表(Link)

链表一般有下面这几个基本操作,先定义一个接口,方便开发和测试:


创建空链表获取链表的长度判断链表是否为空在链表后追加元素在链表前追加元素指定位置插入元素获取指定位置的元素信息打印链表信息删除指定位置的链表元素清空链表

type Element interface {}
type Node struct {
Data Element
Next *Node
}
type Link struct {
Head *Node
Length int
}
/*
当链表中只包含头节点,则链表长度为0,称为空链表。 当插入元素是,也是忽略头节点进行的操作。
*/
// 1、创建空链表
//创建链表的时候,不需要传入参数,直接返回一个链表就ok
func New() *Link{
head := new(Node)
return &Link{head,0}
}
// 2、获取链表的长度。返回 0 则为空
func (l *Link)Len() int{
return l.Length
}
// 3、判断链表是否为空。为空则返回 true
func (l *Link)IsEmpty()bool{
return l.Length == 0
}
// 4、在链表后追加元素
func (l *Link)Append(value interface{}){
n := &Node{value,nil}
p := l.Head
if !l.IsEmpty() {
for p.Next != nil{
p = p.Next
}
}
p.Next = n
l.Length++
return
}
// 5、在链表前追加元素
func (l *Link)PreAppend(value interface{}){
n := &Node{value,nil}
n.Next = l.Head.Next
l.Head.Next = n
l.Length++
return
}
// 6、向链表的指定位置插入元素
func (l *Link)Insert(index int, value interface{}){
if index < 0 || l.IsEmpty(){
l.PreAppend(value)
}else if index > l.Len(){
l.Append(value)
}else{
n := &Node{value,nil}
p := l.Head
for i:=0; i
p = p.Next
}
n.Next = p.Next
p.Next = n
l.Length++
return
}
}
// 7、获取指定位置的元素信息
func (l *Link)Query(index int)Element{
if l.IsEmpty() || index < 0 || index > l.Len(){
return nil
}
p := l.Head.Next
for i:=1; i
p = p.Next
}
return p.Data
}
// 8、打印链表信息
func (l *Link)Print(){
if l.IsEmpty(){
return
}
p := l.Head
for p != nil{
fmt.Println(p.Data)
p = p.Next
}
}
// 9、删除指定位置的链表元素
func (l *Link)Delete(index int){
p := l.Head
for i:=0;i
p = p.Next
}
p.Next = p.Next.Next
l.Length--
}
// 10、清空链表
func (l *Link)Empty(){
l.Head.Next = nil
l.Length = 0
}

循环链表(约瑟夫问题)

package main

import "fmt"

type Element interface{}

var NoData Element = 0

type Node struct {
Data Element
Next *Node
}

type CirculationLink struct {
Head *Node
Length int
}
// 1、创建循环链表
func New() *CirculationLink {
head := new(Node)
return &CirculationLink{Head: head, Length: 0}
}
// 2、获取链表长度
func (l *CirculationLink ) Len() int {
return l.Length
}
// 3、判断是否为空链表
func (l *CirculationLink ) IsEmpty() bool {
if l.Head.Next == nil {
return true
}
return false
}
// 4、向链表末尾追加数据
func (l *CirculationLink ) Append(e Element) {
node := &Node{Data: e, Next: nil}

p := l.Head
if l.IsEmpty() {
p.Next = node

l.Length++
return
}

for p.Next != l.Head {
p = p.Next
}

p.Next = node
l.Length++

return
}
// 5、在头部追加数据
func (l *CirculationLink ) PreAppend(e Element) {
p := l.Head
node := &Node{Data: e, Next: nil}

if l.IsEmpty() {
p.Next = node

l.Length++

return
}

// 插入节点的 NEXT 指向头节点的 Next
node.Next = p.Next

// 头节点的 Next 指向 新插入的节点
p.Next = node

l.Length++

return
}
// 6、在指定位置插入数据
func (l *CirculationLink ) Insert(index int, e Element) {
if l.IsEmpty() || index < 0 {
l.PreAppend(e)

return
}

if index > l.Len() {
l.Append(e)

return
}

p := l.Head
node := &Node{Data: e, Next: nil}

for i := 0; i < index-1; i++ {
p = p.Next
}

// 新插入节点的 Next 节点指向 p[index-1]的Next 节点
node.Next = p.Next

// p[index -1] 的Next 节点 指向 新插入的节点
p.Next = node

l.Length++

return
}
// 7、删除指定位置的数据, 并返回该数据
func (l *CirculationLink ) Delete(index int) Element {
if l.IsEmpty() {
fmt.Println("list is empty. delete error")
return NoData
}

if index < 0 || index > l.Len() {
fmt.Println("index out of range. delete error")
}

p := l.Head
for i := 0; i < index; i++ {
p = p.Next
}

e := p.Next.Data

// 先将 p [index -1] 的 Next 指向 p [index] 的 Next
p.Next = p.Next.Next

l.Length--

return e

}

// 8、查找指定位置的数据
func (l *CirculationLink) Query(index int) Element {
if l.IsEmpty() {
fmt.Println("list is empty. ")

return NoData
}

if index < 0 || index > l.Len() {
return NoData
}

p := l.Head

for i := 0; i < index; i++ {
p = p.Next
}

return p.Data
}
// 9、打印链表
func (l *CirculationLink) Print() {
if l.IsEmpty() {
fmt.Println("list is empty")
}

p := l.Head.Next
i := 1
for p != l.Head {
fmt.Printf("iNode %d, Data %#v
", i, p.Data)
i++
p = p.Next
}
}



双向链表

package main

import "fmt"

type Element interface{}

var NoData Element = 0

type Node struct {
Data Element
Next *Node
Pre *Node
}

type DoubleLink struct {
Head *Node
Length int
}
// 1、创建双向链表
func New() *DoubleLink {
head := new(Node)
return &DoubleLink {Head: head, Length: 0}
}
// 2、获取链表长度
func (l *DoubleLink ) Len() int {
return l.Length
}
// 3、判断是否为空链表
func (l *DoubleLink ) IsEmpty() bool {
if l.Head.Next == nil && l.Head.Pre == nil {
return true
}
return false
}
// 4、向链表末尾追加数据
func (l *DoubleLink ) Append(e Element) {
node := &Node{Data: e, Next: nil, Pre: nil}

p := l.Head
if l.IsEmpty() {
p.Next = node
node.Pre = p

l.Length++
return
}

for p.Next != nil {
p = p.Next
}

p.Next = node
node.Pre = p
l.Length++

return
}
// 5、在头部追加数据
func (l *DoubleLink ) PreAppend(e Element) {
p := l.Head
node := &Node{Data: e, Next: nil, Pre: nil}

if l.IsEmpty() {
p.Next = node
node.Pre = p

l.Length++

return
}

// 插入节点的 NEXT 指向头节点的 Next
node.Next = p.Next
// 头节点的 Next 的 Pre 指向 新插入的节点
p.Next.Pre = node

// 头节点的 Next 指向 新插入的节点
p.Next = node
// 新插入节点的 Pre 指向头节点
node.Pre = p

l.Length++

return
}
// 6、在指定位置插入数据
func (l *DoubleLink ) Insert(index int, e Element) {
if l.IsEmpty() || index < 0 {
l.PreAppend(e)

return
}

if index > l.Len() {
l.Append(e)

return
}

p := l.Head
node := &Node{Data: e, Next: nil, Pre: nil}

for i := 0; i < index-1; i++ {
p = p.Next
}

// 新插入节点的 Next 节点指向 p[index-1]的Next 节点
node.Next = p.Next
// p[index - 1]的 Next.Pre 节点 指向 node 节点
p.Next.Pre = node

// p[index -1] 的Next 节点 指向 新插入的节点
p.Next = node
// ?新插入的节点的Pre 指向 p[index-1]
node.Pre = p

l.Length++

return
}
// 7、删除指定位置的数据, 并返回该数据
func (l *DoubleLink ) Delete(index int) Element {
if l.IsEmpty() {
fmt.Println("list is empty. delete error")
return NoData
}

if index < 0 || index > l.Len() {
fmt.Println("index out of range. delete error")
}

p := l.Head
for i := 0; i < index; i++ {
p = p.Next
}

e := p.Data

// 先将 p [index -1] 的 Next 指向 p [index] 的 Next
p.Pre.Next = p.Next

// 再将 p [index + 1] 的 Pre 指向 p [index -1]
p.Next.Pre = p.Pre

l.Length--

return e

}

// 8、查找指定位置的数据
func (l *DoubleLink) Query(index int) Element {
if l.IsEmpty() {
fmt.Println("list is empty. ")

return NoData
}

if index < 0 || index > l.Len() {
return NoData
}

p := l.Head

for i := 0; i < index; i++ {
p = p.Next
}

return p.Data
}
// 9、打印链表
func (l *DoubleLink) Print() {
if l.IsEmpty() {
fmt.Println("list is empty")
}

p := l.Head.Next
i := 1
for p != nil {
fmt.Printf("iNode %d, Data %#v
", i, p.Data)
i++
p = p.Next
}
}


栈 (Stack)

栈是一种线性结构,与数组相比,栈对应的操作是数组的子集

它只能从一端添加元素,也只能从一端取出元素(这一端称之为栈顶)。

Stack这种数据结构用途很广泛,在计算机的使用中,大量的运用了栈,比如编译器中的词法分析器、Java虚拟机、软件中的撤销操作(Undo)、浏览器中的回退操作,编译器中的函数调用实现等等。


接口说明复杂度
push()向栈中加入元素O(1)
pop()弹出栈顶元素O(1)
peek()查看栈顶元素O(1)
getSize()获取栈中元素个数O(1)
isEmpty()判断栈是否为空O(1)

数组实现stack


package stack

const NoData int = 0

const MaxSize int = 5

type Item interface {
}
// ItemStack the stack of Items
type ItemStack struct {
Items [MaxSize ]Item
Top int
}
// 1、New Create a new ItemStack
func (s *ItemStack) New() *ItemStack {
Items := [MaxSize]Item{}
return &ItemStack{Items,0}
}
// 2、Push adds an Item to the top of the stack
func (s *ItemStack) Push(t Item) {
if s.IsFull() {
fmt.Println(" Stack is full")
return
}
s.Items = append(s.Items, t)
s.Top++
}
// 3、Pop removes an Item from the top of the stack
func (s *ItemStack) Pop() *Item {
if s.IsEmpty() {
fmt.Println("stack is empty")
return NoData
}
s.Top--
item := s.Items[s.Top] // 后进先出
s.Items[s.Top] = 0
return &item
}
// 4、判断栈是否为空
func (s *ItemStack) IsEmpty() bool {
if s.Top == 0 {
return true
}
return false
}
// 5、判断栈是否满了
func (s *ItemStack) IsFull() bool {
if s.Top == MaxSize {
return true
}
return false
}
// 6、清空stack
func (s *ItemStack) Clear() {
var item [MaxSize]Item
s.Items = item
s.Top = 0
}


顺序存储双stack共享空间,解决数组存储问题


单链表实现stack


package main
// 栈顶放在单链表的尾部,当然放在头部也很好
type Stack struct {
top *node
length int
}
type node struct {
value interface{}
prev *node
}
// 创建一个栈
func New() *Stack{
return &Stack{nil,0}
}
// 入栈
func (s *Stack)Push(value interface){
n := &node{value, s.top}
s.top = n
s.length++
}
// 出栈
func (s *Stack)Pop()interface{}{
if s.length == 0 {
return nil
}
res := s.top
s.top = s.top.prev
s.length--
return res.value
}
// 查看栈顶元素
func (s *Stack) Query() interface{} {
if s.length == 0 {
return nil
}
return s.top.value
}
// 取栈长度
func (s *Stack)Len()int{
return s.length
}

package main

import "fmt"
/*
双向链表实现栈
*/
type Element interface{}

type Node struct {
Data Element
Next *Node
Pre *Node
}

type Stack struct {
size int
Top *Node
}

// 1、新建一个栈
func New() *Stack {
return &Stack{size: 0, Top: new(Node)}
}

// 3、获取当前栈的大小
func (s *Stack) Len() int {
return s.size
}

// 3、判断是否为空栈,true 为空, false 为非空
func (s *Stack) IsEmpty() bool {
if s.Len() != 0 {
return false
}

return true
}

// 4、入栈
func (s *Stack) Push(e Element) {
node := &Node{Data: e, Next: nil, Pre: nil}
p := s.Top

// 如果链表为空
if s.IsEmpty() {
p.Pre = node
node.Next = p

s.size++
return
}

// top节点的前一个节点的Next 指向新加入的节点。
p.Pre.Next = node

// 新加入节点指向 top 节点的前一个节点。
node.Pre = p.Pre

// 新加入节点的 Next 指向 Top 节点。
node.Next = p

// top 节点的 Pre 指向新加入的节点
p.Pre = node

// 更新top
s.Top = node
s.size++

return
}

// 5、将栈顶元素弹出栈,并返回被弹出的元素
func (s *Stack) Pop() (e Element) {
if s.IsEmpty() {
fmt.Println("stack is empty")
}

// 获取栈顶指针
p := s.Top

// 被弹出的元素,一定是 倒数第一个元素
e = p.Pre.Data

// 如果只有一个节点, 将 Top 节点的 Pre 指向 nil, 前一个节点的 Next 指向 nil
if p.Pre.Pre == nil {

p.Pre.Next = nil
p.Pre = nil

s.size--
return
}

// 将 top 节点的 前一个节点 的前一个节点。也就是倒入第二个节点的 Next 指向 top 节点。
// 将 top 节点的 Pre 指向 倒数第二个节点。

p.Pre.Pre.Next = p
p.Pre = p.Pre.Pre

s.size--
return
}

// 6、本着 先入后出的原则,我们从栈顶开始遍历 栈
func (s *Stack) Print() {
if s.IsEmpty() {
fmt.Println("stack is empty")
return
}

p := s.Top.Pre
iNode := s.Len()
for p != nil {
fmt.Printf("iNode == %d, data == %#v
", iNode, p.Data)
iNode--
p = p.Pre
}

return
}
// 7、清空栈
func (s *Stack) Clear() {
if s.IsEmpty() {
fmt.Println("stack is empty")
}

s.Top.Pre = nil
s.size = 0

return
}


##队列 Queue


队列也是一种线性数据结构,与数组相比,队列对应的操作是数组的子集

只能从一端 (队尾) 添加元素,只能从另一端 (队首) 取出元素。

队列的应用可以在播放器上的播放列表,数据流对象,异步的数据传输结构(文件IO,管道通讯,套接字等)上体现,当然最直观的的就是排队了。


队列的实现


接口说明复杂度
enqueue()入队O(1) 均摊
dequeue()出队O(n)
getFront()获取队首元素O(1)
getSize()获取队列元素个数O(1)
isEmpty()判断队列是否为空O(1)

数组实现queue


package queue

type Item interface {
}

// Item the type of the queue
type ItemQueue struct {
items []Item
}

type ItemQueuer interface {
New() ItemQueue
Enqueue(t Item)
Dequeue() *Item
IsEmpty() bool
Size() int
}
// New creates a new ItemQueue
func (s *ItemQueue) New() *ItemQueue {
s.items = []Item{}
return s
}
// Enqueue adds an Item to the end of the queue
func (s *ItemQueue) Enqueue(t Item) {
s.items = append(s.items, t)
}
// dequeue
func (s *ItemQueue) Dequeue() Item {
item := s.items[0] // 先进先出
s.items = s.items[1:len(s.items)]

return &item
}
func (s *ItemQueue) IsEmpty() bool {
return len(s.items) == 0
}
// Size returns the number of Items in the queue
func (s *ItemQueue) Size() int {
return len(s.items)
}

数组实现循环队列


package queue

import "errors"

type CyclicQueue struct {
front int
rear int
length int
capacity int
nodes []*Node
}

func NewCyclicQueue(capacity int) (*CyclicQueue, error) {
if capacity <= 0 {
return nil, errors.New("capacity is less than 0")
}

nodes := make([]*Node, capacity, capacity)

return &CyclicQueue{
front: -1,
rear: -1,
capacity: capacity,
nodes: nodes,
}, nil
}

func (q *CyclicQueue) Length() int {
return q.length
}

func (q *CyclicQueue) Capacity() int {
return q.capacity
}

func (q *CyclicQueue) Front() *Node {
if q.length == 0 {
return nil
}

return q.nodes[q.front]
}

func (q *CyclicQueue) Rear() *Node {
if q.length == 0 {
return nil
}

return q.nodes[q.rear]
}

func (q *CyclicQueue) Enqueue(value interface{}) bool {
if q.length == q.capacity || value == nil {
return false
}

node := &Node{
value: value,
}

index := (q.rear + 1) % cap(q.nodes)
q.nodes[index] = node
q.rear = index
q.length++

if q.length == 1 {
q.front = index
}

return true
}

func (q *CyclicQueue) Dequeue() interface{} {
if q.length == 0 {
return nil
}

result := q.nodes[q.front].value
q.nodes[q.front] = nil
index := (q.front + 1) % cap(q.nodes)
q.front = index
q.length--

return result
}

单链表实现queue


package main

import "fmt"
/*
我们用单链表来实现队列的功能。
头指针指向 队列的第一个元素。
尾指针指向 队列的最后一个元素。
*/
type Element interface{}

type Node struct {
Data Element
Next *Node
}

type Queue struct {
Head *Node
Tail *Node
Length int
}

// 1、创建一个队列
func Create() *Queue {
head := &Node{Data: nil, Next: nil}
tail := &Node{Data: nil, Next: nil}

return &Queue{Head: head, Tail: tail, Length: 0}
}

// 2、返回队列的长度
func (q *Queue) Len() int {
return q.Length
}

// 3、判断队列是否为空
func (q *Queue) IsEmpty() bool {
if q.Len() == 0 {
return true
}
return false
}

// 4、打印队列元素
func (q *Queue) Print() {
if q.IsEmpty() {
fmt.Println("queue is empty")
}

p := q.Head.Next
iNode := 1
for p != nil {
fmt.Printf("iNode == %#v,Data == %#v
", iNode, p.Data)
iNode++
p = p.Next
}

return
}

// 5、向队列内添加元素
func (q *Queue) Append(e Element) {
node := &Node{Data: e, Next: nil}
// 如果为空
if q.IsEmpty() {
q.Head.Next = node
q.Tail.Next = node
q.Length++

return
}

// 让最后一个节点的 Next 指向 新的节点
q.Tail.Next = node
// 尾节点指向 新的节点
q.Tail = node
q.Length++

return
}

// 6、删除元素,出队列
func (q *Queue) Delete() {
if q.IsEmpty() {
fmt.Println("queue is empty")

return
}

if q.Len() == 1 {
q.Head.Next = nil
q.Tail.Next = nil
q.Length--

return
}

q.Head.Next = q.Head.Next.Next
q.Length--

return
}

// 7、清空队列
func (q *Queue) Clear() {
if q.IsEmpty() {
fmt.Println("queue is empty")

return
}

q.Head.Next = nil
q.Tail.Next = nil
q.Length = 0

return
}

双链表实现queue


package queue

import "errors"

type Queue interface {
Length() int
Capacity() int
Front() *Node
Rear() *Node
Enqueue(value interface{}) bool
Dequeue() interface{}
}

type Node struct {
value interface{}
previous *Node
next *Node
}

type NormalQueue struct {
front *Node
rear *Node
length int
capacity int
}

func NewNormalQueue(capacity int) (*NormalQueue, error) {
if capacity <= 0 {
return nil, errors.New("capacity is less than 0")
}

front := &Node{
value: nil,
previous: nil,
}

rear := &Node{
value: nil,
previous: front,
}

front.next = rear
return &NormalQueue{
front: front,
rear: rear,
capacity: capacity,
}, nil
}

func (q *NormalQueue) Length() int {
return q.length
}

func (q *NormalQueue) Capacity() int {
return q.capacity
}

func (q *NormalQueue) Front() *Node {
if q.length == 0 {
return nil
}

return q.front.next
}

func (q *NormalQueue) Rear() *Node {
if q.length == 0 {
return nil
}

return q.rear.previous
}

func (q *NormalQueue) Enqueue(value interface{}) bool {
if q.length == q.capacity || value == nil {
return false
}

node := &Node{
value: value,
}

if q.length == 0 {
q.front.next = node
}

node.previous = q.rear.previous
node.next = q.rear
q.rear.previous.next = node
q.rear.previous = node
q.length++

return true
}

func (q *NormalQueue) Dequeue() interface{} {
if q.length == 0 {
return nil
}

result := q.front.next
q.front.next = result.next
result.next = nil
result.previous = nil
q.length--

return result.value
}

小结:
可以看到,具体实现和单链表基本一致,这种方法好处在于不需要考虑数组溢出的问题。但是有时候,我们可能会向 queue 插入相同的元素,我们当前的实现是无法判断数据是否已经存在的,这时我们就需要实现一个无重复元素的 queue。


双链表实现无重复元素的队列
我们只需要在原来的基础上加一个 Map 存放我们的具体值就可以了。直接上代码:


package queue

import (
"errors"
"reflect"
)

type UniqueQueue struct {
front *Node
rear *Node
length int
capacity int
nodeMap map[interface{}]bool
}

func NewUniqueQueue(capacity int) (*UniqueQueue, error) {
if capacity <= 0 {
return nil, errors.New("capacity is less than 0")
}

front := &Node{
value: nil,
}

rear := &Node{
value: nil,
previous: front,
}

front.next = rear
nodeMap := make(map[interface{}]bool)

return &UniqueQueue{
front: front,
rear: rear,
capacity: capacity,
nodeMap: nodeMap,
}, nil
}
func (q *UniqueQueue) Enqueue(value interface{}) bool {
if q.length == q.capacity || value == nil {
return false
}

node := &Node{
value: value,
}

// Ignore uncomparable type.
if kind := reflect.TypeOf(value).Kind(); kind == reflect.Map || kind == reflect.Slice || kind == reflect.Func {
return false
}

if v, ok := q.nodeMap[value]; ok || v {
return false
}

if q.length == 0 {
q.front.next = node
}

node.previous = q.rear.previous
node.next = q.rear
q.rear.previous.next = node
q.rear.previous = node

q.nodeMap[value] = true

q.length++

return true
}

最小栈、最小队列、最大栈、最大队列
实现一个栈,带有出栈(pop),入栈(push),取最小元素(getMin)三个方法。这三个方法的时间复杂度都是O(1)实现一个栈,带有出栈(pop),入栈(push),取最大元素(getMax)三个方法。这三个方法的时间复杂度都是O(1)实现一个队列,带有出队(deQueue),入队(enQueue),取最小元素(getMin)三个方法。时间复杂度都尽可能小。实现一个队列,带有出队(deQueue),入队(enQueue),取最大元素(getMax)三个方法。时间复杂度都尽可能小。



友情链接: