算法：golang实现双端队列

喜欢ヅ旅行 2022-09-08 03:57 242阅读 0赞

# 使用指针实现 #

*  需要一个尾指针和一个头指针分别指向队列的两端
 *  队列里面是由一个个节点组成的

package main
    
    import (
    	"fmt"
    )
    
    type Fifo_Interface interface {
        
    	acl_push_back(data interface{
        });
    	acl_push_front(data interface{
        });
    	acl_pop_back() (interface{
        }, error);
    	acl_pop_front() (interface{
        }, error);
    	acl_head() (interface{
        }, error)
    	acl_tail() (interface{
        }, error)
    	acl_index(index int)(interface{
        }, error)
    }
    
    type acl_fifo_info struct {
        
    	data interface{
        }
    	prev *acl_fifo_info
    	next *acl_fifo_info
    }
    
    func acl_fifo_info_new(data interface{
        }) *acl_fifo_info  {
        
    	return &acl_fifo_info{
        
    		data: data,
    prev: nil,
    	next: nil,
    }
    }
    
    type Acl_fifo struct {
        
    	head *acl_fifo_info
    	tail *acl_fifo_info
    	cnt int
    }
    
    func Acl_fifo_new() *Acl_fifo  {
        
    	return &Acl_fifo{
        
    		head: nil,
    		tail: nil,
    		cnt:  0,
    	}
    }
    
    
    func (fifo *Acl_fifo)acl_push_back(data interface{
        }){
        
    	info := acl_fifo_info_new(data);
    	if info == nil {
        
    		return
    	}
    
    	if fifo.tail == nil {
        
    		fifo.head = info
    	    fifo.tail = info
    	    info.prev = nil
    	    info.next = nil
    	}else{
        
    		fifo.tail.next = info
    		info.prev = fifo.tail
    		info.next = nil
    		fifo.tail = info
    	}
    
    	fifo.cnt++;
    
    }
    func (fifo *Acl_fifo)acl_push_front(data interface{
        }){
        
    	info := acl_fifo_info_new(data);
    	if info == nil {
        
    		return
    	}
    
    	if fifo.head == nil {
        
    		fifo.head = info
    		fifo.tail = info
    		info.prev = nil
    		info.next = nil
    	}else{
        
    		info.next = fifo.head
    		fifo.head.prev = info
    		info.prev = nil
    		fifo.head = info
    	}
    
    	fifo.cnt++
    }
    func (fifo *Acl_fifo)acl_pop_back() (interface{
        }, error){
        
    	if fifo.tail == nil {
        
    		return nil, fmt.Errorf("fifo is empty");
    	}
    
    	info := fifo.tail
    	if fifo.tail.prev == nil {
        
    		fifo.tail = nil
    		fifo.head = nil
    	}else{
        
    		fifo.tail.prev.next = nil
    		fifo.tail = fifo.tail.prev
    	}
    
    	fifo.cnt--
    
    	return info.data, nil
    }
    func (fifo *Acl_fifo)acl_pop_front() (interface{
        }, error){
        
    	if fifo.head == nil {
        
    		return nil, fmt.Errorf("fifo is empty");
    	}
    
    	info := fifo.head
    	if fifo.head.next == nil {
        
    		fifo.head = nil
    		fifo.tail = nil
    	}else{
        
    		fifo.head.next.prev = nil
    		fifo.head = fifo.head.next
    	}
    
    	fifo.cnt--;
    
    	return info.data, nil
    }
    func (fifo *Acl_fifo)acl_size() int{
        
    	return fifo.cnt;
    }
    func (fifo *Acl_fifo)acl_index(index int)(interface{
        }, error){
        
    	if index < 0 || index > fifo.cnt - 1 {
        
    		 return nil, fmt.Errorf("index out of range");
    	}
    
    	info := fifo.head
    	for i := 0; i < fifo.cnt; i++{
        
    		if i == index {
        
    			break
    		}
    		info = info.next
    	}
    
    	return info.data, nil
    }
    
    
    func (fifo *Acl_fifo)acl_head() (interface{
        }, error){
        
    	if fifo.head == nil {
        
    		return nil, fmt.Errorf("fifo is empty");
    	}else{
        
    		return fifo.head.data, nil
    	}
    }
    func (fifo *Acl_fifo)acl_tail() (interface{
        }, error){
        
    	if fifo.tail == nil {
        
    		return nil, fmt.Errorf("fifo is empty");
    	}else{
        
    		return fifo.tail.data, nil
    	}
    }
    
    func main() {
        
    	var size int
    	var fifo *Acl_fifo
    
    	fifo = Acl_fifo_new()
    
    	size = fifo.acl_size()
    	fmt.Print(size, " should be [0]\n")
    
    	fmt.Printf("\n----------push_back[pop_back]-------------------\n")
    	for i := 0; i < 10; i++{
        
    		fifo.acl_push_back(i)
    		fmt.Printf("%d\t",i)
    	}
    	fmt.Println()
    
    
    	head , _  := fifo.acl_head()
    	tail , _  := fifo.acl_tail()
    	fmt.Println(head.(int), tail.(int))
    
    	size = fifo.acl_size()
    	for i := 0; i < size; i++{
        
    		info, _ := fifo.acl_pop_back()
    		fmt.Printf("%d\t",info.(int))
    	}
    
    
    	fmt.Printf("\n----------push_back[pop_front]-------------------\n")
    
    
    	for i := 0; i < 10; i++{
        
    		fifo.acl_push_back(i)
    		fmt.Printf("%d\t",i)
    	}
    	fmt.Println()
    
    	head , _  = fifo.acl_head()
    	tail , _  = fifo.acl_tail()
    	fmt.Println(head.(int), tail.(int))
    
    	size = fifo.acl_size()
    	for i := 0; i < size; i++{
        
    		info, _ := fifo.acl_pop_front()
    		fmt.Printf("%d\t",info.(int))
    	}
    	fmt.Printf("\n-----------------------------\n")
    
    
    
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBAT2NlYW4mJlN0YXI_size_26_color_FFFFFF_t_70_g_se_x_16]

# 使用容器list实现 #

> **注意迭代器的写法**

package main
    
    
    import (
    	"container/list"
    	"sync"
    )
    
    type Deque struct {
        
    	sync.RWMutex
    	container *list.List // 双向链表
    	capacity int
    }
    /*
    Deque使用双向链表实现，每个操作的时间复杂度为O（1）。
    并且是同步&&并发安全的
    */
    func NewDeque() *Deque  {
        
    	return NewCappedDeque(-1)
    }
    
    
    /*
    newCappedRequest创建具有指定容量限制的Deque。
     -1 表示不限制容量
    */
    func NewCappedDeque(capacity int) *Deque {
        
    	return  &Deque{
        
    		RWMutex:   sync.RWMutex{
        },
    		container: list.New(),
    		capacity:  capacity,
    	}
    }
    
    /*
    PushBack： 在Deque尾部以O（1）时间复杂度插入元素，
    如果成功，则返回true；如果Deque已满容量，则返回false。
    */
    func (s *Deque)PushBack(item interface{
        }) bool  {
        
    	s.Lock()
    	defer s.Unlock()
    
    	// 如果不限制容量 || 当前容量 < 限制容量 ， 则尾插
    	if(s.capacity < 0 || s.container.Len() < s.capacity){
        
    		s.container.PushBack(item)
    		return true
    	}
    
    	return false
    }
    
    /*
    PushFront： 在Deque头部以O（1）时间复杂度插入元素，
    如果成功，则返回true；如果Deque已满容量，则返回false。
    */
    func (s *Deque)PushFront(item interface{
        }) bool  {
        
    	s.Lock()
    	defer s.Unlock()
    
    	// 如果不限制容量 || 当前容量 < 限制容量 ， 则头插
    	if(s.capacity < 0 || s.container.Len() < s.capacity){
        
    		s.container.PushFront(item)
    		return true
    	}
    
    	return false
    }
    
    // popBack： 时间复杂度O（1）, 移除末尾元素
    // 返回移除的元素。 如果当前队列为空，则返回nil
    func (s *Deque) popBack() interface{
        }  {
        
    	s.Lock()
    	defer s.Unlock()
    
    	var item interface{
        } = nil
    	var lastContainerItem *list.Element = nil
    
    	lastContainerItem = s.container.Back() // 获取最末尾的元素
    	if(lastContainerItem != nil){
        
    		item = s.container.Remove(lastContainerItem)
    	}
    
    	return item
    }
    
    // PopFront： 时间复杂度O（1）, 移除队首元素
    // 返回移除的元素。 如果当前队列为空，则返回nil
    func (s *Deque) PopFront() interface{
        } {
        
    	s.Lock()
    	defer s.Unlock()
    
    	var item interface{
        } = nil
    	var lastContainerItem *list.Element = nil
    
    	lastContainerItem = s.container.Front() // 获取队首元素
    	if(lastContainerItem != nil){
        
    		item = s.container.Remove(lastContainerItem)
    	}
    
    	return item
    }
    
    // Front()： 时间复杂度O（1）, 获取队首元素
    func (s *Deque) Front() interface{
        } {
        
    	s.Lock()
    	defer s.Unlock()
    
    	item := s.container.Front() // 获取队首元素
    	if(item != nil){
        
    		return item.Value
    	}
    
    	return nil
    }
    
    // Back()： 时间复杂度O（1）, 获取队尾元素
    func (s *Deque) Back() interface{
        } {
        
    	s.Lock()
    	defer s.Unlock()
    
    	item := s.container.Back() // 获取队尾元素
    	if(item != nil){
        
    		return item.Value
    	}
    
    	return nil
    }
    
    
    // Size()： 时间复杂度O（1）, 获取队列长度
    func (s *Deque) Size() int {
        
    	s.Lock()
    	defer s.Unlock()
    
    	return s.container.Len()
    }
    
    // Capacity()： 时间复杂度O（1）, 获取队列容量， -1表示不限制容量
    func (s *Deque) Capacity() int {
        
    	s.Lock()
    	defer s.Unlock()
    
    	return s.capacity
    }
    
    // Empty()： 时间复杂度O（1）,检查队列是否为空
    func (s *Deque) Empty() bool {
        
    	s.Lock()
    	defer s.Unlock()
    
    	return s.container.Len() == 0
    }
    
    // Empty()： 时间复杂度O（1）,检查队列是否满了
    func (s *Deque) Full() bool {
        
    	s.Lock()
    	defer s.Unlock()
    
    	return s.capacity > 0 && s.container.Len() >= s.capacity
    }
    
    func (q *Deque) Dump()  {
        
    	for iter := q.container.Front();  iter != nil; iter = iter.Next()  {
        
    		fmt.Println("item:", iter.Value)
    	}
    }

# 使用切片实现 #

# 使用数组实现 #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBAT2NlYW4mJlN0YXI_size_26_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/47ff724d5f274bd3a12bb0ce0bd48b84.png