forked from TheAlgorithms/C-Sharp
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathStackBasedQueue.cs
More file actions
96 lines (83 loc) · 2.44 KB
/
StackBasedQueue.cs
File metadata and controls
96 lines (83 loc) · 2.44 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
using System;
using System.Collections.Generic;
namespace DataStructures.Queue;
/// <summary>
/// Implementation of a stack based queue. FIFO style.
/// </summary>
/// <remarks>
/// Enqueue is O(1) and Dequeue is amortized O(1).
/// </remarks>
/// <typeparam name="T">Generic Type.</typeparam>
public class StackBasedQueue<T>
{
private readonly Stack<T> input;
private readonly Stack<T> output;
/// <summary>
/// Initializes a new instance of the <see cref="StackBasedQueue{T}" /> class.
/// </summary>
public StackBasedQueue()
{
input = new Stack<T>();
output = new Stack<T>();
}
/// <summary>
/// Clears the queue.
/// </summary>
public void Clear()
{
input.Clear();
output.Clear();
}
/// <summary>
/// Returns the first item in the queue and removes it from the queue.
/// </summary>
/// <exception cref="InvalidOperationException">Thrown if the queue is empty.</exception>
public T Dequeue()
{
if (input.Count == 0 && output.Count == 0)
{
throw new InvalidOperationException("The queue contains no items.");
}
if (output.Count == 0)
{
while (input.Count > 0)
{
var item = input.Pop();
output.Push(item);
}
}
return output.Pop();
}
/// <summary>
/// Returns a boolean indicating whether the queue is empty.
/// </summary>
public bool IsEmpty() => input.Count == 0 && output.Count == 0;
/// <summary>
/// Returns a boolean indicating whether the queue is full.
/// </summary>
public bool IsFull() => false;
/// <summary>
/// Returns the first item in the queue and keeps it in the queue.
/// </summary>
/// <exception cref="InvalidOperationException">Thrown if the queue is empty.</exception>
public T Peek()
{
if (input.Count == 0 && output.Count == 0)
{
throw new InvalidOperationException("The queue contains no items.");
}
if (output.Count == 0)
{
while (input.Count > 0)
{
var item = input.Pop();
output.Push(item);
}
}
return output.Peek();
}
/// <summary>
/// Adds an item at the last position in the queue.
/// </summary>
public void Enqueue(T item) => input.Push(item);
}