/
021_QueueWithTwoStacks.cs
87 lines (71 loc) · 2.01 KB
/
021_QueueWithTwoStacks.cs
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
// Coding Interviews: Questions, Analysis & Solutions
// Harry He
using System;
using System.Collections.Generic;
namespace QueueWithStacks
{
public class QueueWithTwoStacks<T>
{
public void Enqueue(T item)
{
stack1.Push(item);
}
public T Dequeue()
{
if (stack2.Count == 0)
{
while (stack1.Count > 0)
{
T item = stack1.Peek();
stack1.Pop();
stack2.Push(item);
}
}
if (stack2.Count == 0)
throw new InvalidOperationException("Queue is Empty");
T head = stack2.Peek();
stack2.Pop();
return head;
}
private Stack<T> stack1 = new Stack<T>();
private Stack<T> stack2 = new Stack<T>();
}
class Program
{
static void Test(char actual, char expected)
{
if (actual == expected)
Console.WriteLine("Test passed.");
else
Console.WriteLine("Test failed.");
}
static void Main(string[] args)
{
QueueWithTwoStacks<char> queue = new QueueWithTwoStacks<char>();
queue.Enqueue('a');
queue.Enqueue('b');
queue.Enqueue('c');
char head = queue.Dequeue();
Test(head, 'a');
head = queue.Dequeue();
Test(head, 'b');
queue.Enqueue('d');
head = queue.Dequeue();
Test(head, 'c');
queue.Enqueue('e');
head = queue.Dequeue();
Test(head, 'd');
head = queue.Dequeue();
Test(head, 'e');
try
{
head = queue.Dequeue();
Console.WriteLine("Test failed.");
}
catch(InvalidOperationException)
{
Console.WriteLine("Test passed.");
}
}
}
}