C#数组和链表实现队列

C#数组和链表实现队列

//基于数组的队列实现 public class MyArrayQueue { private T[] items; private int size; private int head; private int tail; public MyArrayQueue(int capacity) { this.items = new T[capacity]; this.size = 0; this.head = this.tail = 0; } ///

/// 入队 ///

/// 入队元素 public void EnQueue(T item) { if (Size == items.Length) // 扩大数组容量 ResizeCapacity(items.Length * 2); items[tail] = item; tail++; size++; } ///

v /// 出队 ///

/// 出队元素 public T DeQueue() { if (size == 0) return default(T); T item = items[head]; items[head] = default(T); head++; if (head > 0 && Size == items.Length / 4) ResizeCapacity(items.Length / 2); size--; return item; } ///

/// 重置数组大小 ///

/// 新的容量 public void ResizeCapacity(int newCapacity) { T[] newItems = new T[newCapacity]; int index = 0; if (newCapacity > items.Length) { for (int i = 0; i < items.Length; i++) newItems[index++] = items[i]; } else { for (int i = 0; i < items.Length; i++) { if (!items[i].Equals(default(T))) { newItems[index++] = items[i]; } } head = tail = 0; } items = newItems; } ///

/// 栈是否为空 ///

/// true/false public bool IsEmpty() { return this.size == 0; } ///

/// 栈中节点个数 ///

public int Size { get { return this.size; } } }

public class Node { public T Item { get; set; } public Node Next { get; set; } public Node(T item) { this.Item = item; } public Node() { } } ///

/// 基于链表的队列实现 ///

/// 类型 public class MyLinkQueue { private Node head; private Node tail; private int size; public MyLinkQueue() { this.head = null; this.tail = null; this.size = 0; } ///

/// 入队操作 ///

/// 节点元素 public void EnQueue(T item) { Node oldLastNode = tail; tail = new Node(); tail.Item = item; if (IsEmpty()) { head = tail; } else { oldLastNode.Next = tail; } size++; } ///

/// 出队操作 ///

/// 出队元素 public T DeQueue() { T result = head.Item; head = head.Next; size--; if (IsEmpty()) { tail = null; } return result; } ///

/// 是否为空队列 ///

/// true/false public bool IsEmpty() { return this.size == 0; } ///

/// 队列中节点个数 ///

public int Size { get { return this.size; } } }

class Program { static void Main(string[] args) { // 01.基于链表的队列 QueueWithLinkListTest(); // 02.基于数组的队列 //QueueWithArrayTest(); } #region Method01.基于链表的队列的测试 ///

/// 基于链表的队列的测试 ///

static void QueueWithLinkListTest() { MyLinkQueue queue = new MyLinkQueue(); Console.WriteLine("Is Empty:{0}", queue.IsEmpty()); Random rand = new Random(); // 顺序插入5个元素 for (int i = 0; i < 5; i++) { int num = rand.Next(1, 10); queue.EnQueue(num); Console.WriteLine("{0} enqueue.", num); } Console.WriteLine("Size:{0}", queue.Size); Console.WriteLine("-------------------------"); // 5个元素依次出队 for (int i = 0; i < 5; i++) { Console.WriteLine("{0} dequeue.", queue.DeQueue()); } Console.WriteLine("Size:{0}", queue.Size); Console.WriteLine("-------------------------"); // 顺序插入10个元素 for (int i = 0; i < 10; i++) { int num = rand.Next(1, 10); queue.EnQueue(num); Console.WriteLine("{0} enqueue.", num); } Console.WriteLine("Size:{0}", queue.Size); Console.WriteLine("-------------------------"); // 10个元素依次出队 for (int i = 0; i < 10; i++) { Console.WriteLine("{0} dequeue.", queue.DeQueue()); } Console.WriteLine("Size:{0}", queue.Size); } #endregion #region Method02.基于数组的队列的测试 ///

/// 基于数组的队列的测试 ///

static void QueueWithArrayTest() { MyArrayQueue queue = new MyArrayQueue(5); Console.WriteLine("Is Empty:{0}", queue.IsEmpty()); Console.WriteLine("Size:{0}", queue.Size); Random rand = new Random(); // Test1.1:顺序插入5个数据元素 for (int i = 0; i < 5; i++) { int num = rand.Next(1, 10); queue.EnQueue(num); Console.WriteLine("{0} enqueue.", num); } Console.WriteLine("Is Empty:{0}", queue.IsEmpty()); Console.WriteLine("Size:{0}", queue.Size); // Test1.2:临时插入1个数据元素验证数组是否扩容 queue.EnQueue(rand.Next(1, 20)); Console.WriteLine("Size:{0}", queue.Size); Console.WriteLine("-------------------------"); // Test2.1:前5个元素出队 for (int i = 0; i < 5; i++) { Console.WriteLine("{0} dequeue.", queue.DeQueue()); } Console.WriteLine("Is Empty:{0}", queue.IsEmpty()); Console.WriteLine("Size:{0}", queue.Size); Console.WriteLine("-------------------------"); // Test2.2:最后一个数据元素出队验证数组是否收缩容量 queue.DeQueue(); Console.WriteLine("Size:{0}", queue.Size); Console.WriteLine("-------------------------"); queue.DeQueue(); } #endregion }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。