C#實現(xiàn)雙端隊列的示例代碼
更新時間：2023年11月28日 09:41:39 作者：神仙別鬧
雙端隊列是一種可以在兩端擴展或收縮的序列化容器,本文主要介紹了C#實現(xiàn)雙端隊列的示例代碼,具有一定的參考價值,感興趣的可以了解一下
話說有很多數(shù)據(jù)結構都在玩組合拳，比如說：塊狀鏈表，塊狀數(shù)組，當然還有本篇的雙端隊列，是的，它就是棧和隊列的組合體。
一、概念
我們知道普通隊列是限制級的一端進，另一端出的 FIFO 形式，棧是一端進出的 LIFO 形式，而雙端隊列就沒有這樣的限制，也就是我們可以在隊列兩端進行插入或者刪除操作。
二、編碼
2.1、定義結構體
通常情況下，隊列的內部都是采用數(shù)組來實現(xiàn)，而且?guī)в袃蓚€指針 head 和 tail 來指向數(shù)組的區(qū)間段，為了充分利用數(shù)組空間，我們也會用 % 來實現(xiàn)邏輯上的循環(huán)數(shù)組，如下圖。
public class MyQueue
{
public int head;
public int tail;
public int maxSize;
public int size;
public T[] list;
public MyQueue()
{
head = tail = size = 0;
maxSize = 3;
list = new T[maxSize];
}
}
這里有一個注意的細節(jié)就是“size 字段“，它是為了方便統(tǒng)計隊列是否為滿或者隊列是否為空。
2.2、隊尾入隊
剛才也說了，雙端隊列是可以在隊列的兩端進行插入和刪除的，要注意的是我們用 head 和 tail 指針的時候，tail 指針是指向元素的下一個位置，
而 head 指針是指向當前元素，所以我們可以從 tail 端 push 數(shù)據(jù)的時候只要”順時針“下移一個位置即可。
/// <summary>
/// 隊尾入隊
/// </summary>
/// <param name="t"></param>
/// <returns></returns>
public bool Push_Tail(T t)
{
//判斷隊列是否已滿
if (myQueue.size == myQueue.list.Length)
return false;
myQueue.list[myQueue.tail] = t;
//順時針旋轉
myQueue.tail = (myQueue.tail + 1) % myQueue.maxSize;
myQueue.size++;
return true;
}
2.3、隊尾出隊
和隊尾入隊一樣，我們只要將 tail 指針”逆時針“下移一個位置，當然有一個細節(jié)需要注意，就是 tail 指針有存在負值的情況，畢竟我們是做”–操作“的，所以需要 tail+maxSize，即：
myQueue.tail = (--myQueue.tail + myQueue.maxSize) % myQueue.maxSize;
/// <summary>
/// 隊尾出隊
/// </summary>
/// <param name="edges"></param>
/// <param name="t"></param>
public T Pop_Tail()
{
//判斷隊列是否已空
if (myQueue.size == 0)
return default(T);
//逆時針旋轉(防止負數(shù))
myQueue.tail = (--myQueue.tail + myQueue.maxSize) % myQueue.maxSize;
var temp = myQueue.list[myQueue.tail];
//賦予空值
myQueue.list[myQueue.tail] = default(T);
myQueue.size--;
return temp;
}
2.4、隊首入隊
從 head 端來說，我們 push 數(shù)據(jù)的時候是 head 指針“逆時針”旋轉，要注意的是同樣要防止負數(shù)的產生，并且 head 指針是指向當前元素。
/// <summary>
/// 隊首入隊
/// </summary>
/// <param name="t"></param>
/// <returns></returns>
public bool Push_Head(T t)
{
//判斷隊列是否已滿
if (myQueue.size == myQueue.list.Length)
return false;
//逆時針旋轉(防止負數(shù)產生)
myQueue.head = (--myQueue.head + myQueue.maxSize) % myQueue.maxSize;
//賦予元素
myQueue.list[myQueue.head] = t;
myQueue.size++;
return true;
}
2.5、隊首出隊
說到這個方法，我想大家應該都懂了雙端隊列的大概流程了，這個方法我也不用贅敘了。
/// <summary>
/// 隊首出隊
/// </summary>
/// <param name="edges"></param>
/// <param name="t"></param>
public T Pop_Head()
{
//判斷隊列是否已空
if (myQueue.size == 0)
return default(T);
//獲取隊首元素
var temp = myQueue.list[myQueue.head];
//原來單位的值賦默認值
myQueue.list[myQueue.head] = default(T);
//順時針旋轉
myQueue.head = (myQueue.head + 1) % myQueue.maxSize;
myQueue.size--;
return temp;
}
從上面的四個方法可以看出：
當我們只使用 Push_Tail 和 Pop_Tail 的話，那它就是棧。
當我們只使用 Push_Tail 和 Pop_Head 的話，那它就是隊列。
最后是全部代碼：
using System.Net;
using System;
using System.IO;
using System.Collections.Generic;
using System.Text;
using System.Drawing;
using System.Drawing.Imaging;
class Program
{
static void Main(string[] args)
{
DoubleQueue<int> queue = new DoubleQueue<int>();
queue.Push_Tail(10);
queue.Push_Tail(20);
queue.Push_Tail(30);
queue.Pop_Tail();
queue.Pop_Tail();
queue.Pop_Tail();
queue.Push_Tail(10);
queue.Push_Head(20);
queue.Push_Head(30);
queue.Push_Head(30);
queue.Pop_Tail();
queue.Pop_Tail();
queue.Pop_Head();
queue.Push_Head(40);
queue.Push_Tail(50);
queue.Push_Tail(60);
}
}
/// <summary>
/// 雙端隊列
/// </summary>
public class DoubleQueue<T>
{
public class MyQueue
{
public int head;
public int tail;
public int maxSize;
public int size;
public T[] list;
public MyQueue()
{
head = tail = size = 0;
maxSize = 3;
list = new T[maxSize];
}
}
MyQueue myQueue = new MyQueue();
/// <summary>
/// 隊尾入隊
/// </summary>
/// <param name="t"></param>
/// <returns></returns>
public bool Push_Tail(T t)
{
//判斷隊列是否已滿
if (myQueue.size == myQueue.list.Length)
return false;
myQueue.list[myQueue.tail] = t;
//順時針旋轉
myQueue.tail = (myQueue.tail + 1) % myQueue.maxSize;
myQueue.size++;
return true;
}
/// <summary>
/// 隊尾出隊
/// </summary>
/// <param name="edges"></param>
/// <param name="t"></param>
public T Pop_Tail()
{
//判斷隊列是否已空
if (myQueue.size == 0)
return default(T);
//逆時針旋轉(防止負數(shù))
myQueue.tail = (--myQueue.tail + myQueue.maxSize) % myQueue.maxSize;
var temp = myQueue.list[myQueue.tail];
//賦予空值
myQueue.list[myQueue.tail] = default(T);
myQueue.size--;
return temp;
}
/// <summary>
/// 隊首入隊
/// </summary>
/// <param name="t"></param>
/// <returns></returns>
public bool Push_Head(T t)
{
//判斷隊列是否已滿
if (myQueue.size == myQueue.list.Length)
return false;
//逆時針旋轉(防止負數(shù)產生)
myQueue.head = (--myQueue.head + myQueue.maxSize) % myQueue.maxSize;
//賦予元素
myQueue.list[myQueue.head] = t;
myQueue.size++;
return true;
}
/// <summary>
/// 隊首出隊
/// </summary>
/// <param name="edges"></param>
/// <param name="t"></param>
public T Pop_Head()
{
//判斷隊列是否已空
if (myQueue.size == 0)
return default(T);
//獲取隊首元素
var temp = myQueue.list[myQueue.head];
//原來單位的值賦默認值
myQueue.list[myQueue.head] = default(T);
//順時針旋轉
myQueue.head = (myQueue.head + 1) % myQueue.maxSize;
myQueue.size--;
return temp;
}
}到此這篇關于C#實現(xiàn)雙端隊列的示例代碼的文章就介紹到這了,更多相關C# 雙端隊列內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了C#實現(xiàn)會移動的文字效果，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-04-04
RTF（Rich Text Format）是一種通用的文檔格式,允許用戶在不同的文字處理軟件中保存和交換格式化文本,下面我們就來看看如何使用C#實現(xiàn)將RTF轉換為PDF吧2025-11-11
本文主要介紹了幾種常見的破解密碼的方法，為密碼加鹽（Salt）以及在.NET中的實現(xiàn)等。具有一定的參考價值，下面跟著小編一起來看下吧2017-01-01
本文介紹了使用WINDOWS API判斷一個磁盤驅動器的類型和使用System.IO.DriveInfo判斷一個磁盤驅動器的二種方法，大家參考和吧2014-01-01
這篇文章主要介紹了C#編寫COM組件的方法,結合實例形式分析了C#編寫COM組件的具體步驟與相關實現(xiàn)技巧,需要的朋友可以參考下2017-06-06
在許多C#和.NET應用程序中,程序化拆分PDF文件是自動化文檔管理的重要步驟,本指南詳細介紹了如何使用Spire.PDF for .NET庫,在C#中程序化拆分或分割PDF文件,并提供了實用的方法和清晰的代碼示例,需要的朋友可以參考下2025-11-11
在使用泛型定義類的過程中遇到了不少問題，特記錄如下，需要的朋友可以參考下2013-07-07
這篇文章主要為大家詳細介紹了如何基于C#實現(xiàn)一個rar文件密碼破解工具,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2025-07-07
Unity UGUI的EventTrigger事件監(jiān)聽器組件介紹使用示例
這篇文章主要為大家介紹了Unity UGUI的EventTrigger事件監(jiān)聽器組件介紹及使用,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-08-08
這篇文章主要給大家介紹了關于C#中explicit與implicit的相關資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用C#具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2019-05-05