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ù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
Lambda，希臘字母λ，在C#編程語言中，被引入為Lambda表達式，表示為匿名函數(shù)（匿名方法）。本文將利用Lambda表達式進行代碼的簡化，感興趣的可以了解一下2022-12-12
C# paddlerocrsharp識別身份證號的實現(xiàn)示例
paddlerocrsharp可以進行圖片識別,本文主要介紹了C# paddlerocrsharp識別身份證號的實現(xiàn)示例,具有一定的參考價值,感興趣的可以了解一下2024-02-02
在C#中,同步回調和異步回調都是用于處理任務或事件完成的機制,本文主要介紹了C#中同步和異步回調的實現(xiàn),具有一定的參考價值,感興趣的可以了解一下2025-04-04
這篇文章主要介紹了使用C#代碼獲取存儲過程返回值,需要的朋友可以參考下2015-11-11
這篇文章主要介紹了C#實現(xiàn)的Win32控制臺線程計時器功能,結合實例形式分析了C#基于控制臺的時間操作相關技巧,需要的朋友可以參考下2016-08-08
這篇文章主要給大家介紹了關于c#中string的特性介紹及注意事項的相關資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用c#具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2019-11-11
這篇文章主要介紹了c# await，async執(zhí)行流的相關知識，文章講解的非常細致，代碼幫助理解和學習，感興趣的朋友可以了解下2020-06-06
C#中創(chuàng)建統(tǒng)一API接口的實現(xiàn)方案
在 C# 中創(chuàng)建統(tǒng)一 API 接口需要從架構設計、技術選型和代碼實現(xiàn)等多個層面進行規(guī)劃,本文給大家詳細介紹了實現(xiàn)方案和完整示例代碼,對大家的學習或工作有一定的幫助,需要的朋友可以參考下2025-04-04
這篇文章主要介紹了C#生成單頁靜態(tài)頁簡單實例,是一個非常實用的技巧,需要的朋友可以參考下2014-10-10
本篇文章介紹了，C#詞法分析器之輸入緩沖和代碼定位的應用分析。需要的朋友參考下2013-05-05