Универсален пръстен буфер в C#
Пръстеновият буфер е фиксирана опашка FIFO (First In, First Out). Пространствата в буфера могат да се разглеждат като свързани в пръстен. Елементите в буфера никога не се преместват. Вместо това се използват променливи указатели за идентифициране на главата и опашката на опашката.
Какво е пръстен буфер?
Циркулярният буфер, известен също като кръгова опашка или кръгов буфер, е FIFO опашка с висока производителност. Както при всеки друг тип опашка, стойностите могат да се добавят към края на опашката и да се извличат от началото, така че елементите да се разтоварват в същия ред, в който са поставени на опашка.
В някои структури на опашка, когато елементите се добавят или премахват, съдържанието на опашката се премества физически в паметта. При кръгъл буфер позициите са фиксирани. Главата и опашката на опашката се идентифицират с два указателя, които се актуализират, когато елементите се добавят или премахват. В допълнение, буферните пространства могат да се разглеждат като циклични. След използване на последното пространство в буфера, следващият елемент в опашката се съхранява в първото пространство. Диаграмата по-долу показва концептуалния модел на пръстенов буфер.
Диаграмата е кръгъл буфер с шестнадесет интервала, тринадесет от които се използват. В този случай стойностите от едно до тринадесет бяха добавени по ред. Главата на опашката сочи към последната стойност, тринадесет, а опашката е в пространството, съдържащо числото едно. Когато следващият елемент е в опашката, той ще бъде добавен към следващото налично празно място след тринадесет и показалецът на главата ще бъде изместен, за да сочи към тази позиция. Когаще бъде извършена следващата операция по декомпресия, числото едно в показалеца на опашката ще бъде извлечено и опашката ще се премести на едно място по часовниковата стрелка. Когато изтривате обект, няма нужда да изчиствате старото буферно пространство, тъй като стойността ще бъде презаписана в някакъв момент в бъдеще.
Природата на кръговия буфер е такава, че главата на опашката може да хване опашката. Когато следващият елемент, който трябва да бъде поставен на опашката, презапише опашния елемент, има няколко възможни действия. Най-често срещаните са:
Хвърлете изключение при опит за добавяне към пълна опашка или четене от празен буфер. Това гарантира, че няма да се загубят данни, но е по-малко полезно за опашки в реално време или където скоростите на поставяне и изваждане от опашка не са еднакви.
Внедряване на кръгов буфер
Можем да започнем, като създадем клас за пръстенния буфер. За да позволим на буфер да съхранява данни от всякакъв тип, ние ще го декларираме като общ клас с единичен тип параметър.
След това имаме нужда от няколкопроменливи на ниво клас. Първо, имаме нужда от място, където да съхраняваме буферните данни. За да направим това, ще използваме масив от типа, дефиниран в параметъра тип. Ще използваме две цели числа като указатели към главата и опашката. Те ще съдържат стойностите на индекса за буферния масив. Двете допълнителни цели числа ще съдържат текущата дължина на опашката и размера на буфера. Те ще се използват за определяне дали буферът е пълен или празен. И накрая, за да предотвратим грешки при синхронизиране, ако множество нишки се опитат да се поставят в опашка или да се деактивират едновременно, ще създадем обект за управление на ключалките.
Кодът за променливи на ниво клас изглежда така:
Когато обектът CircularBuffer е създаден, ние инициализираме буфера и указателя към главата с помощта на конструктора. Конструкторът включва един параметър, който ви позволява да укажете размера на буфера. Това се съхранява и използва за инициализиране на масива. Показалецът върху главата е настроен на последния елемент от масива. Когато първият елемент е в опашката, показалецът ще бъде преместен напред към първия елемент, преди да бъде съхранен, след което стойностите на главата и опашката ще бъдат нула.
Добавяне на флагове за състояние на опашка
Когато работим с опашка, трябва да знаем кога буферът е пълен или празен. Тази информация може да бъде полезна и за потребителите на класа, така че ще създадем две булеви свойства, които показват тези състояния. Опашката е празна, когато текущата дължина е нула, и се запълва, когато текущата дължина съответства на размера на буфера.
Кодът за това изглежда така:
Сега можем да добавим метод Dequeue, който извлича и връща най-стария елемент от буфера. Това е прост процес, който се състои от няколкостъпки. Първо, ако опашката е празна, хвърляме изключение. Това не позволява на потребителите да изтеглят твърде много елементи, което може да доведе до връщане на данни, които преди това са били премахнати или извлечени от празни буферни пространства.
След това получаваме стойността на масива в крайната позиция, която ще бъде върната в края на процеса. След това напредваме опашката с едно място, увеличавайки стойността на индекса. Ако указателят достигне размера на буфера, ние го връщаме на нула, за да следим цикличния характер на структурата от данни. В кода това се постига с помощта на командата modulus. Авансът се дефинира в отделен метод NextPosition, тъй като тази функционалност ще се използва повторно. Тъй като броят на елементите в буфера вече е по-малък, намаляваме променливата дължина до правилната стойност.
Кодът на метода е показан по-долу. Имайте предвид, че е добавено заключване, за да се гарантира, че указателите не могат да бъдат модифицирани от друг процес.
Последният метод на внедряване ви позволява да организирате реда на новите стойности. Когато елемент се добави към опашката, първо посочваме главата и съхраняваме новата стойност в новия индекс. Това означава, че показалецът винаги сочи към позицията на новия елемент в опашката. Ако опашката вече е пълна, това ще презапише най-старата стойност в буфера, така че да придвижим позицията на опашката напред, за да сочи към следващия елемент, който сега е най-старият. Ако буферът все още не е пълен, индексът на опашката остава непроменен и текущата дължина се увеличава.
Използване на пръстен буфер
Вече можем да тестваме кръговия буфер чрез стартиране и дезактивиране на елементи. За първи тест опитайте кода, показан по-долу. Той създава малък буфер с пет цели числа.Петте стойности се поставят на опашка и след това се премахват, което показва, че редът на елементите е запазен.
Вторият пример показва какво се случва, когато капацитетът на опашката бъде превишен. Тук шест елемента се добавят към опашка, която може да съдържа само пет. При изтриване виждаме, че най-старият елемент е изхвърлен.
статии IT, SI sharp, стек, буфер, теория на програмирането