使用链接列表的队列实现: C#
使用链接列表的队列实现: C#
提问于 2019-12-27 05:25:16
我在学习数据结构。今天，我想使用链接列表来实现队列。因为我们有前面和后面的第一个索引的入口点的队列。如果有人要求我用链表实现一个队列，请确认我下面的实现(我能够实现队列目标而没有后面的对象)。
这个实现有效吗？
class Queue
{
Node head;
class Node
{
public int Value;
public Node next;
public Node()
{
next = null;
}
}
public void addElement(int val)
{
if (head == null)
{
Node temp = new Node();
temp.Value = val;
head = temp;
return;
}
Node tempNode = head;
while (tempNode.next != null)
{
tempNode = tempNode.next;
}
Node newElement = new Node();
newElement.Value = val;
tempNode.next = newElement;
}
public void Dequeue()
{
if (head != null)
{
if (head.next != null)
{
head = head.next;
return;
}
head = null;
}
}
}
class Program
{
static void Main(string[] args)
{
Queue queue = new Queue();
queue.addElement(10);
queue.addElement(20);
queue.addElement(30);
queue.addElement(40);
queue.Dequeue();
queue.Dequeue();
queue.Dequeue();
queue.Dequeue();
}
}回答 1
Stack Overflow用户
回答已采纳
发布于 2019-12-27 07:32:43
好吧，如果我们想要前部和后部，就让他们：
private Node m_Head;
private Node m_Tail;您只有一个Node head;字段，这就是为什么您的实现至少效率低下的原因:您有O(N)时间复杂度到addElement
...
while (tempNode.next != null)
{
tempNode = tempNode.next;
}
...当您可以轻松地拥有O(1)时
我建议使用典型的名称，如Enqueue，而不是addElement，并使用Try方法(通常，如果队列为空，我们不希望出现异常)。最后，让我们使用泛型：MyQueue<T>，其中T是项的类型。
public class MyQueue<T> {
private class Node {
public Node(Node next, T value) {
Next = next;
Value = value;
}
public Node Next { get; internal set; }
public T Value { get; }
}
private Node m_Head;
private Node m_Tail;
public void Enqueue(T item) {
Node node = new Node(null, item);
if (m_Tail == null) {
m_Head = node;
m_Tail = node;
}
else {
m_Tail.Next = node;
m_Tail = node;
}
}
public bool TryPeek(out T item) {
if (m_Head == null) {
item = default(T);
return false;
}
item = m_Head.Value;
return true;
}
public T Peek() {
if (m_Head == null)
throw new InvalidOperationException("Queue is empty.");
return m_Head.Value;
}
public bool TryDequeue(out T item) {
if (m_Head == null) {
item = default(T);
return false;
}
item = m_Head.Value;
m_Head = m_Head.Next;
return true;
}
public T Dequeue() {
if (m_Head == null)
throw new InvalidOperationException("Queue is empty.");
T item = m_Head.Value;
m_Head = m_Head.Next;
return item;
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/59496346
复制相关文章
相似问题
腾讯云开发者
