C＃中的FIFO字符串分配＃

Question

我目前遇到了我现在创建的程序有问题。我已经在寻找答案，但它与我想要发生的不同，因为这里给出的是字符串。

我们被要求创建一个FIFO分配，这里是程序作为控制台应用程序的流量预计：

输入no。页框：2

输入no。的页将被插入：要被插入4

页：插在帧1中断产生的

。

要插入的页面：B

插入帧2.产生中断。要被插入

页：甲

插入失败。 A是常驻页面。

要插入的页面：C

插入帧1.产生中断。

根据FIFO分配算法，如果插入新的不同页面，它将删除插入帧中的最早页面。如果该页面已经在框架中，则页面插入将被拒绝。

我已经做了一个，虽然我目前在试图找出如何找到数组中最早插入的元素。

我希望你能帮助我。我已经花了很多时间，但我不知道该怎么做。这里是我的代码。：

class Program 
{ 
    static void Main(string[] args) 
    { 
     int f, p, interrupt; 

     Console.WriteLine("Enter the number of frames: "); 
     f = Int32.Parse(Console.ReadLine()); 
     string[] frame = new string[f]; 
     Console.WriteLine("Enter the number of pages: "); 
     p = Int32.Parse(Console.ReadLine()); 

     for (int i = 0; i < p; i++) { 


      Console.WriteLine("Page to be inserted: "); 

      string x = Console.ReadLine(); 

      if (frame.Contains(x)) 
      { 

       Console.WriteLine(x + " is a resident page."); 


      } 
      else { 

       frame[i] = x; 
       Console.WriteLine("Inserted in frame " + (i + 1) + ". Interrupt generated")); 
       interrupt +=1; 

      } 
     } 





     Console.ReadKey(); 
    } 
} 

Answer 1

不要使用数组。 “先入先出”模式是队列http://msdn.microsoft.com/en-us/library/system.collections.queue.aspx

如果您使用队列，它将保留订单。您只能删除第一个项目。它的概念就是它像一个交通队列一样工作，前面的物体在其他任何物体移动之前都必须移动。在排队之前，只需执行for each或LINQ查询以确保该项目不重复。 Dequeue方法将始终删除添加到队列中的第一个项目。

// for each example. For LINQ just use Where then check the length of the IEnumerable 
// if it 0 then item is unique. 
bool duplicate = false; 
foreach (string s in MyQueue) 
{ 
    if (s == inputString) 
     duplicate = true; 
} 

if (!duplicate) 
    MyQueue.Enqueue(inputString); 



// to get first item added simply do 
string firstIn = MyQueue.Dequeue(); 

Answer 2

我建议你使用除了数组之外的东西，比如evanmcdonnal suggested。总之，用你的代码，你需要，当你达到极限帧添加一个单独的变量来检测：

int j= 0; 

    for (int i = 0; i < p; i++) { 


     Console.WriteLine("Page to be inserted: "); 

     string x = Console.ReadLine(); 

     if (frame.Contains(x)) 
     { 

      Console.WriteLine(x + " is a resident page."); 


     } 
     else { 

      if(j >= f) 
       int insertAt = 0; 
      else 
       int insertAt = j; 

      frame[insertAt ] = x; 
      Console.WriteLine("Inserted in frame " + (insertAt + 1) + ". Interrupt generated")); 
      interrupt +=1; 

      j++; 

     } 
    } 

Answer 3

您的问题是你的代码混淆的数据结构，以及它与实际的程序方法。你需要更多地分解你的程序。您需要首先创建一个实现您的FIFO队列的类。验证它的行为是否符合您的预期。然后，使用该类编写您需要的实际程序。

正如其他人所指出的，您实际需要的数据结构似乎是一个队列。

与某些人所说的（“不使用数组”）相反，固定容量的队列使用数组作为后备存储实现是微不足道的。

您需要将您的数组用作循环缓冲区。除了阵列本身，你需要跟踪其他3条信息：

• 队列头的偏移量。这是队列中最近添加的项目中最少的项目，并且将被删除。

• 队列的尾部的偏移量。这是队列中最近添加的项目，并且是最后删除的项目。

从理论上讲，您不再需要任何信息。然而，有一个奇点，头部和尾部相撞的状态是'排队空'状态或'排队满状态'。因此，您需要跟踪队列的长度。

的Dequeue()操作是容易的：

• 检查队列长度。如果小于1，则队列为空。抛出一个下溢异常。否则，继续。
• 头部偏移量是要移除的下一个项目。从数组中获取该项目。
• 清除数组插槽，因此不会留下可能会阻止对象被垃圾收集的悬挂引用。
• 减少长度。

• 递增头指针，如果它超过了磁盘阵列的capacacity包装为零 - 1。要做到这一点是通过模运算的最简单方法：

  OffsetHead = (OffsetHead+1) % MyBackingStoreArray.Length ; 
  

• 将卸下的物品。

的Enqueue()操作并不复杂得多，虽然有一个特殊的情况下，当队列为空：

• 检查队列长度。
• 如果队列长度为0，第一个项目添加到队列：
  • 的项添加到阵列在偏移0
  • 设置偏移量到头部和偏移到尾为0。

• 如果队列长度是> 0，

  • 偏移到所述第一空闲时隙是1过去当前尾指针，模与上述阵列的长度。
  • 如果计算的偏移量与队列头部的偏移量冲突，则队列已满：抛出溢出异常。
  • 否则，将该新项目添加到该计算出的偏移量的数组中。
  • 将尾部的偏移量设置为计算偏移量。

• 最后，增加队列长度。

您可能要实施的其它操作：

• Peek()。有时查看队列中的下一个项目而不排出队列可能会很有用。
• Contains()。形式上，队列是一个不透明的数据结构。您只能将项目添加到尾部并将其从头部移除。然而，检查是否已经入队是有用的，但我认为使用集合式语义来装饰队列将会是一个更好的设计。

对于将队列的当前长度作为属性公开也非常有用。

你应该可以从那里弄清楚。如果你还没有弄明白，我会在明天实施这个答案。

。 。 。

正如所承诺的，这里的固定长度的队列的实现：

class ArrayQueue<T> 
{ 
    private T[] backingStore ; 
    private int head ; // offset to head of the queue (least recently added item) 
    private int tail ; // offset to tail of the queue (most recently added item) 

    /// <summary> 
    /// current queue length 
    /// </summary> 
    public int Length { get ; private set ; } 
    /// <summary> 
    /// Maximum Queue Length 
    /// </summary> 
    public int Capacity { get { return this.backingStore.Length ; } } 

    /// <summary> 
    /// Add an item to the queue 
    /// </summary> 
    /// <param name="value"></param> 
    public void Enqueue(T value) 
    { 

    if (Length == 0) 
    { 
     this.backingStore[0] = value ; 
     this.head = 0 ; 
     this.tail = 0 ; 
    } 
    else 
    { 
     // A head/tail collision means the queue is full: throw an overflow exception 
     if (this.tail == this.head) { throw new OverflowException("Maximum capacity exceeded") ; } 
     this.backingStore[this.tail] = value ; 
    } 

    // increment the tail and the length, wrapping the tail point if necessary 
    this.tail = (this.tail+1) % this.backingStore.Length ; 
    ++this.Length ; 

    return ; 
    } 

    /// <summary> 
    /// Remove the next (oldest) item from the queue 
    /// </summary> 
    /// <returns></returns> 
    public T Dequeue() 
    { 
    if (this.Length < 1) { throw new InvalidOperationException("queue is empty") ; } 

    T value = this.backingStore[head] ; 
    this.backingStore[head] = default(T) ; // lose the reference so the newly dequeued item can be garbage-collected. 

    --this.Length; 
    this.head = (this.head+1) % this.backingStore.Length ; 

    return value ; 
    } 

    /// <summary> 
    /// Examine the head of the queue, without removing it 
    /// </summary> 
    /// <returns></returns> 
    public T Peek() 
    { 
    if (this.Length < 1) { throw new InvalidOperationException("queue is empty") ; } 

    T value = this.backingStore[head] ; 
    return value ; 
    } 

    /// <summary> 
    /// Clear/Empty the queue 
    /// </summary> 
    public void Clear() 
    { 
    // clear any object references to the queue so they can be garbage-collected 
    Array.Clear(this.backingStore,0,this.backingStore.Length); 
    this.head = 0 ; 
    this.tail = 0 ; 
    this.Length = 0 ; 
    return ; 
    } 

    /// <summary> 
    /// indicates whether or not the specified item is present in the queue 
    /// </summary> 
    /// <param name="value"></param> 
    /// <returns></returns> 
    public bool Contains(T value) 
    { 
    bool found = false ; 
    for (int i = 0 ; !found && i < this.Length ; ++i) 
    { 
     int p = (this.head+1) % this.Capacity ; 
     found = this.backingStore[p].Equals(value) ; 
    } 
    return found ; 
    } 

    /// <summary> 
    /// Create an instance of an ArrayQueue&lt;T&gt; having the specified fixed capacity 
    /// </summary> 
    /// <param name="capacity"></param> 
    /// <returns></returns> 
    public static ArrayQueue<T> CreateInstance(int capacity) 
    { 
    if (capacity < 0) throw new ArgumentOutOfRangeException("capacity","capacity must be non-negative"); 

    ArrayQueue<T> instance = new ArrayQueue<T>(capacity) ; 

    return instance ; 
    } 

    /// <summary> 
    /// private (and only constructor) 
    /// </summary> 
    /// <param name="capacity"></param> 
    private ArrayQueue(int capacity) 
    { 
    this.backingStore = new T[capacity] ; 
    this.Clear() ; 
    return ; 
    } 

} 

Answer 4

我敢打赌，这将帮助。打开此页面并使用相同的示例。

http://msdn.microsoft.com/en-us/library/ee789351(v=vs.110).aspx

只是使这种变化的Main（）方法下的线。

 // Create a scheduler that uses 1 threads first-in, first-out (FIFO) execution order. 
     LimitedConcurrencyLevelTaskScheduler lcts = new LimitedConcurrencyLevelTaskScheduler(1);