Circular-Stack/CircularStack.cs at master · shpun817/Circular-Stack · GitHub

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
using System;

public class CircularStack<T> {

    private T[] _arr;
    private int _maxSize; // This is fixed
    private int _top;
    private int _bottom;
	private bool _isEmpty;

    public CircularStack (int maxSize) {
        if (maxSize <= 0)
            throw new OverflowException("Size of CircularStack not positive.");
        _arr = new T[maxSize];
		for (int i = 0; i < maxSize; ++i) {
			_arr[i] = default(T);
		}
        _top = _bottom = 0;
        _maxSize = maxSize;
		_isEmpty = true;
    }

    public int GetSize() {
		if (_top > _bottom) {
			return (_top - _bottom + 1);
		} else if (_top < _bottom) {
			return (_maxSize - _bottom + _top + 1);
		} else if (_isEmpty) {
			return 0;
		} else {
			return 1;
		}
	}
    public int GetMaxSize() { return _maxSize; }

    public void Push(T obj) {
        if (_isEmpty) {
			_isEmpty = false;
			_top = _bottom = 0; // Reset to play safe
		} else {
			_top = (_top + 1) % _maxSize;
			if (_bottom == _top) {
				_bottom = (_bottom + 1) % _maxSize;
			}
		}
		_arr[_top] = obj;
    }

	public T Peek() {
		if (_isEmpty) {
			return default(T);
		}
		return _arr[_top];
	}

    public T Pop() {
        if (_isEmpty) {
			return default(T);
		} else {
			T obj = _arr[_top];
			if (_top == _bottom) {
				_isEmpty = true;
			} else {
				if (_top == 0) {
					_top = _maxSize;
				}
				--_top;
			}
			return obj;
		}
    }

    public void Resize(int newSize) {
        if (newSize <= 0)
			throw new OverflowException("Size of CircularStack not positive.");
        T[] tempArr = new T[newSize];
		int currentSize = GetSize();
		int tempSize = newSize<currentSize?newSize:currentSize;
		for (int i = 0; i < tempSize; ++i) {
			tempArr[i] = _arr[(_bottom+i)%_maxSize];
		}
		_arr = tempArr;
		_bottom = 0;
		_top = newSize<currentSize?newSize-1:currentSize-1;
		_maxSize = newSize;
    }

	public void Clear() {
		for (int i = 0; i < _maxSize; ++i) {
			_arr[i] = default(T);
		}
       _top = _bottom = 0;
	   _isEmpty = true;
	}

    public override String ToString() {
        String str = "";
		int size = GetSize();
        for (int i = 0; i < size; ++i) {
            str += _arr[(_bottom+i)%_maxSize] + " ";
        }
        return str.TrimEnd();
    }

}

/* FOR TESTING
class Program
{
	static void Main(string[] args)
	{
		CircularStack<int> cs = new CircularStack<int>(5);
		cs.Push(2);
		cs.Push(1);
		cs.Push(3);
		cs.Push(4);
		cs.Push(11);
		cs.Resize(3);
		cs.Resize(4);
		Console.WriteLine(cs.Peek());
		Console.WriteLine(cs);
	}
}
*/