公告版位

簡介

佇列(Queue)中文也翻作隊列,顧名思義是一種像排隊一樣的概念,以生活中的情況為例如下圖

queue_line_2   

人們一個接一個的從隊伍後面加入排隊,而窗口的服務人員則從最前面的民眾一個接一個處理事務;當然現實生活是會有中途離開的人,而在程式世界裡面一般情況是不會有。

在這個模式下我們可以知道他是一種先進先出(First-In-First-Out, FIFO)的排程,而在此資料結構中至少會實作兩個操作:

  1. enqueue:將資料放入佇列尾端。(註:C++中用push、Java用offer、也有add等不同的用字)
  2. dequeue:取出佇列前端之資料。(註:C++中用pop、Java用poll、也有remove等不同的用字)

有時候也會多實作一些額外的操作以方便使用,例如:

  1. peek:看佇列前端的資料而不取出。(註:也有front等不同的用字)
  2. size:取得佇列的數目。

在實作上一般使用連結串列(LinkedList)來實作,使用陣列同樣可以達成,但較為複雜:

連結串列

用指標將資料串起來,將新的東西不斷接在最後面,而取出時則移除最前面的東西即可。由於加入和移除的端點不同,如果只記住第一個節點的話,在加入資料時,必須每次都向後找到最後一個節點會耗費許多時間,為了讓加入和移除都在O(1)的時間完成,可以同時記錄最前面和最後面的節點。

陣列

佇列建立時即建立一個陣列,但由於加入和刪除的端點不同,所以我們需要一個索引來記錄開始位址和一個索引來記錄結束位址,如下圖所示:

 arrayQueue  

然而我們會發現,不斷的enqueue和dequeue之後,佇列的範圍會慢慢往後移,直到陣列的盡頭,為了永續經營,我們必須重新使用前面的部分,所以我們還必須多進行一個轉換的動作。

實作上我只有額外多紀錄開始索引,而利用序列數目、陣列長度和簡單的取餘數方式來算出結束索引,公式如下:

下一個佇列索引位址 = (開始索引位址 + 序列數目) % 陣列長度

以上圖情況為例:

(0 + 3) % 6 = 3
(3 + 3) % 6 = 0
(4 + 3) % 6 = 1

另外,在實作佇列擴充,進行陣列的複製動作時,需將陣列元素重新整理,將開始位址的元素複製到新陣列的起始位置,否則資料會亂掉,如下圖所示:

q  

語法

C#

抽象類別

using System;
using System.Collections.Generic;
using System.Text;

namespace Queue
{
    abstract class Queue<T>
    {
        public int Count { get; protected set; }
        abstract public void Enqueue(T value);
        abstract public T Dequeue();
        abstract public T Peek();
    }
}

連結串列

using System;
using System.Collections.Generic;
using System.Text;

namespace Queue
{
    class Node<T>
    {
        public Node<T> Next { get; internal set; }
        public T Value { get; internal set; }

        public Node(T value)
        {
            Value = value;
        }
    }

    class LinkedListQueue<T> : Queue<T>
    {
        private Node<T> first;
        private Node<T> last;

        public override void Enqueue(T value)
        {
            Node<T> node = new Node<T>(value);
            if (Count == 0)
                first = node;
            else
                last.Next = node;
            last = node;
            ++Count;
        }

        public override T Dequeue()
        {
            Node<T> node = first;
            first = first.Next;
            node.Next = null;
            --Count;
            return node.Value;
        }

        public override T Peek()
        {
            return first.Value;
        }
    }
}

陣列

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Queue
{
    class ArrayQueue<T> : Queue<T>
    {
        private int capacity;
        private int first;
        private T[] array;

        public ArrayQueue()
            : this(10240)
        {
        }

        public ArrayQueue(int capacity)
        {
            this.capacity = capacity;
            array = new T[capacity];
        }

        public override void Enqueue(T value)
        {
            if (Count == array.Length)
            {
                T[] newArray = new T[array.Length + capacity];
                Array.Copy(array, first, newArray, 0, array.Length - first);
                Array.Copy(array, 0, newArray, array.Length - first, first);
                array = newArray;
                first = 0;
            }
            array[(first + Count) % array.Length] = value;
            ++Count;
        }

        public override T Dequeue()
        {
            T value = array[first];
            array[first] = default(T);
            first = (first + 1) % array.Length;
            --Count;
            return value;
        }

        public override T Peek()
        {
            return array[first];
        }
    }
}

Java

抽象類別

public abstract class Queue<T> {
	protected int count;
	
    abstract public void offer(T value);
    abstract public T poll();
    abstract public T peek();
    
    public int size()
    {
    	return count;
    }
}

連結串列

public class Node<T>
{
	private Node<T> next;
	private T value;
	
    public Node<T> getNext() 
    { 
    	return next; 
    }
    
    void setNext(Node<T> next) 
    { 
    	this.next = next;
    }
    
    public T getValue()
    { 
    	return value;
    }
    
    void setValue(T value) 
    { 
    	this.value = value;
    }

    public Node(T value)
    {
        this.value = value;
    }
}
public class LinkedListQueue<T> extends Queue<T> {

	private Node<T> first;
	private Node<T> last;
	
	@Override
	public void offer(T value) {
		// TODO Auto-generated method stub
        Node<T> node = new Node<T>(value);
        if (count == 0)
            first = node;
        else
            last.setNext(node);
        last = node;
        ++count;
	}

	@Override
	public T poll() {
		// TODO Auto-generated method stub
        Node<T> node = first;
        first = first.getNext();
        node.setNext(null);
        --count;
        return node.getValue();
	}

	@Override
	public T peek() {
		// TODO Auto-generated method stub
		return first.getValue();
	}

}

陣列

public class ArrayQueue<T> extends Queue<T> {

    private int capacity;
    private int first;
    private T[] array;

    public ArrayQueue()
    {
    	this(10240);
    }

    @SuppressWarnings("unchecked")
	public ArrayQueue(int capacity)
    {
        this.capacity = capacity;
        array = (T[]) new Object[capacity];
    }
    
    @SuppressWarnings("unchecked")
	@Override
	public void offer(T value) {
		// TODO Auto-generated method stub

        if (count == array.length)
        {
            T[] newArray = (T[]) new Object[array.length + capacity];
            System.arraycopy(array, first, newArray, 0, array.length - first);
            System.arraycopy(array, 0, newArray, array.length - first, first);
            array = newArray;
            first = 0;
        }
        array[(first + count) % array.length] = value;
        ++count;
	}

	@Override
	public T poll() {
		// TODO Auto-generated method stub
        T value = array[first];
        array[first] = null;
        first = (first + 1) % array.length;
        --count;
        return value;
	}

	@Override
	public T peek() {
		// TODO Auto-generated method stub
		return array[first];
	}

}

C++

抽象類別

#ifndef QUEUE_H
#define QUEUE_H

template<typename T>
class Queue
{
    public:
        Queue()
        {
            count = 0;
        }
        int size()
        {
            return count;
        }
        virtual void push(T value) = 0;
        virtual T pop() = 0;
        virtual T front() = 0;
    protected:
        int count;
    private:
};

#endif // QUEUE_H

連結串列

#ifndef LINKEDLISTQUEUE_H
#define LINKEDLISTQUEUE_H

#include "Queue.h"

template<typename T>
class Node
{
    public:
        Node(T v)
        {
            value = v;
            next = 0;
        }
        ~Node()
        {
            delete next;
        }
        Node<T>* next;
        T value;
    protected:
    private:
};

template<typename T>
class LinkedListQueue : public Queue<T>
{
    public:
        ~LinkedListQueue()
        {
            if(first != last)
                delete first;
            delete last;
        }
        void push(T value)
        {
            Node<T>* node = new Node<T>(value);
            if (Queue<T>::count == 0)
                first = node;
            else
                last->next = node;
            last = node;
            ++Queue<T>::count;
        }
        T pop()
        {
            Node<T>* node = first;
            first = first->next;
            node->next = 0;
            T value = node->value;
            delete node;
            --Queue<T>::count;
            return value;
        }

        T front()
        {
            return first->value;
        }
    protected:
    private:
        Node<T>* first;
        Node<T>* last;
};

#endif // LINKEDLISTQUEUE_H

陣列

#ifndef ARRAYQUEUE_H
#define ARRAYQUEUE_H

#include <memory.h>
#include "Queue.h"

template<typename T>
class ArrayQueue : public Queue<T>
{
    public:
        ArrayQueue(int capacity = 10240)
        {
            cap = capacity;
            arrayLength = capacity;
            array = new T[capacity];
        }
        ~ArrayQueue()
        {
            delete [] array;
        }
        void push(T value)
        {
            if (Queue<T>::count == arrayLength)
            {
                T* newArray = new T[arrayLength + cap];
                memcpy(newArray, array + first, (arrayLength - first) * sizeof(T));
                memcpy(newArray + arrayLength - first, array, first * sizeof(T));
                arrayLength += cap;
                delete [] array;
                array = newArray;
                first = 0;
            }
            array[(first + Queue<T>::count) % arrayLength] = value;
            ++Queue<T>::count;
        }

        T pop()
        {
            T value = array[first];
            array[first] = 0;
            first = (first + 1) % arrayLength;
            --Queue<T>::count;
            return value;
        }

        T front()
        {
            return array[first];
        }
    protected:
    private:
        int arrayLength;
        int cap;
        int first;
        T* array;
};

#endif // ARRAYQUEUE_H

enqueue和dequeue 500000次實測,同時候內建的類別比較

C#
Built-in Queue Enqueue Time: 30ms
Built-in Queue Dequeue Time: 10ms
LinkedListQueue Enqueue Time: 80ms
LinkedListQueue Pop Time: 20ms
ArrayQueue Enqueue Time: 60ms
ArrayQueue Dequeue Time: 10ms

Java
Built-in Queue Offer Time:  130ms
Built-in Queue Poll Time:  20ms
LinkedListQueue Offer Time:  178ms
LinkedListQueue Poll Time:  12ms
ArrayQueue Offer Time:  112ms
ArrayQueue Poll Time:  10ms

C++
Built-in Push Time: 10ms
Built-in Pop Time: 30ms
LinkedListQueue Push Time: 50ms
LinkedListQueue Pop Time: 40ms
ArrayQueue Push Time: 30ms
ArrayQueue Pop Time: 10ms

下載

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(2) 人氣()


留言列表 (2)

發表留言
  • Ablert.H
  • 您好,我最近在撰寫畢業論文
    想引用一些您的部落格上的內容
    不知是否可以?
    於文獻部分會標註此網站
  • 好的,沒有問題

    emn178 於 2014/05/06 09:31 回覆

  • 悄悄話
找更多相關文章與討論