-
-
Save bkyrlach/2afadd1c0461aea22e03 to your computer and use it in GitHub Desktop.
Learning about Stacks and Queues, simultaneously. Please forgive the way that I call this a Stack, and then use all Queue terms for the methods.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections; | |
using System.Collections.Generic; | |
using System.Linq; | |
namespace Stack | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
var doubleList = new DoublyLinkedListQueue<int>(); | |
doubleList.Enqueue(12); | |
doubleList.Enqueue(6); | |
doubleList.Enqueue(18); | |
doubleList.Enqueue(3); | |
doubleList.Enqueue(9); | |
Console.WriteLine(doubleList.Peek()); | |
Console.WriteLine(doubleList.Pop()); | |
Console.WriteLine(doubleList.Peek()); | |
Console.WriteLine(doubleList.Pop()); | |
} | |
public class LinkedList<T> : IEnumerable<T> | |
{ | |
private Node<T> Root { get; set; } | |
public void Add(T t) | |
{ | |
var next = new Node<T> | |
{ | |
Value = t | |
}; | |
if (Root == null) | |
{ | |
Root = next; | |
} | |
else | |
{ | |
var temp = Root; | |
temp.Previous = next; | |
Root = next; | |
next.Next = temp; | |
} | |
} | |
public T Remove() | |
{ | |
var retval = Root.Value; | |
Root = Root.Next; | |
return retval; | |
} | |
public T Head() | |
{ | |
return Root.Value; | |
} | |
private class Node<T> : IEnumerable<T> | |
{ | |
public T Value { get; set; } | |
public Node<T> Next { get; set; } | |
public Node<T> Previous { get; set; } | |
public IEnumerator<T> GetEnumerator() | |
{ | |
return new LinkedListEnumerator<T>(this); | |
} | |
IEnumerator IEnumerable.GetEnumerator() | |
{ | |
return GetEnumerator(); | |
} | |
} | |
private class LinkedListEnumerator<T> : IEnumerator<T> | |
{ | |
private Node<T> _head; | |
public LinkedListEnumerator(Node<T> head) | |
{ | |
_head = head ?? new Node<T>(); | |
} | |
public void Dispose() | |
{ | |
} | |
public bool MoveNext() | |
{ | |
var retval = _head.Next != null; | |
if (!retval) | |
{ | |
_head = _head.Next; | |
} | |
return retval; | |
} | |
public void Reset() | |
{ | |
while (_head.Previous != null) | |
{ | |
_head = _head.Previous; | |
} | |
} | |
public T Current => _head.Value; | |
object IEnumerator.Current => Current; | |
} | |
public IEnumerator<T> GetEnumerator() | |
{ | |
return Root.GetEnumerator(); | |
} | |
IEnumerator IEnumerable.GetEnumerator() | |
{ | |
return Root.GetEnumerator(); | |
} | |
} | |
public class DoublyLinkedListQueue<T> | |
{ | |
private readonly LinkedList<T> _storage = new LinkedList<T>(); | |
/// <summary> | |
/// If list is empty, designates node as first element in the list. Else sets the Previous value of new node to lastNode, and sets lastNode.Next value to the new node. | |
/// </summary> | |
/// <param name="input"></param> | |
public void Enqueue(T input) | |
{ | |
_storage.Add(input); | |
} | |
/// <summary> | |
/// Extracts Value of the first node, sets the Previous of the second node to null, sets head to the second node, and decrements the Count. Returns Value from the former first node. | |
/// </summary> | |
/// <returns></returns> | |
public T Pop() | |
{ | |
return _storage.Remove(); | |
} | |
/// <summary> | |
/// Returns the Value of the head. | |
/// </summary> | |
/// <returns></returns> | |
public T Peek() | |
{ | |
return _storage.Head(); | |
} | |
/// <summary> | |
/// Returns the int Count that is updated every time a node is added or subtracted from the list. | |
/// ((Always begins counting from the first node in the list. While a node value exists in Next, adds 1 to the count, and progresses to the next value.)) | |
/// </summary> | |
/// <returns></returns> | |
public int GetLength() | |
{ | |
return _storage.Count(); | |
} | |
public bool Any() | |
{ | |
return _storage.Any(); | |
} | |
public override string ToString() | |
{ | |
var inner = string.Join(",", _storage); | |
return $"Stack({inner})"; | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment