c'è in C# un contenitore generico già definito che può essere utilizzato come Stack e come Queue allo stesso tempo? Voglio solo essere in grado di aggiungere elementi sia alla fine o verso la parte anteriore della codacombinazione C# stack queue
grazie
Controllare la classe .
LinkedList<int> list = new LinkedList<int>();
list.AddFirst(1);
list.AddLast(2);
list.AddFirst(0);
Quello che vogliamo è un linked list - c'è uno nella BCL - che ha AddFirst e AddLast metodi
Ecco la mia implementazione di un deque immutabile:
Si noti che si tratta di un immutabile doppio attacco coda . Normalmente probabilmente pensi a una coda come qualcosa che muti:
queue.Enqueue(10);
Una coda immutabile rimane sempre la stessa; quando si aggiunge un nuovo elemento, ti dà indietro una completamente nuova coda, in modo da utilizzare come:
queue = queue.Enqueue(10);
se vi interessa non riguarda più il vecchio valore.
Buono vecchio List<T> lo farà.
Add() per accodare, Insert(0,T) per inviare, Remove(0) per pop/dequeue.
Inserisci e Rimuovi saranno entrambe operazioni O (n). Un elenco collegato sarà O (1) – thecoop
Cool - il mio primo downvote. Grazie per aver segnalato la O (n). Ma per essere pignoli, non sarebbe solo O (n) sugli inserimenti nella parte anteriore dell'Elenco ma non fino alla fine (dal momento che è basato su Array)? –
Dipende dal costo a cui ti riferisci. Stai parlando del costo * ammortizzato * o del * peggiore singolo caso *? Il costo ammortizzato per l'inserimento di n elementi alla fine di una lista double-when-full è O (1). Il costo nel caso peggiore di inserire un elemento in una lista doppia al completo di n elementi è O (n). –
Ecco una classe per aiutare le persone a implementare facilmente questo:
public class StackQueue<T>
{
private LinkedList<T> linkedList = new LinkedList<T>();
public void Push(T obj)
{
this.linkedList.AddFirst(obj);
}
public void Enqueue(T obj)
{
this.linkedList.AddFirst(obj);
}
public T Pop()
{
var obj = this.linkedList.First.Value;
this.linkedList.RemoveFirst();
return obj;
}
public T Dequeue()
{
var obj = this.linkedList.Last.Value;
this.linkedList.RemoveLast();
return obj;
}
public T PeekStack()
{
return this.linkedList.First.Value;
}
public T PeekQueue()
{
return this.linkedList.Last.Value;
}
public int Count
{
get
{
return this.linkedList.Count;
}
}
}
Con tutto il rispetto, questo non sembra rispondere alla sua domanda. – StriplingWarrior
Il collegamento ha una classe che definisce ciò che l'OP stava cercando. L'esempio fornito in questa risposta non lo dimostra in realtà. –
StriplingWarrior, non ho idea di cosa tu stia parlando. Il poster richiede un contenitore generico esistente che si comporta come una pila o una coda. Tale contenitore è chiamato "deque" e ho fornito un link al codice sorgente per un'implementazione di tale. Esattamente quale parte della domanda non ha avuto risposta? –