Monday, June 17, 2019

C Sharp Creating a Stack using string array

Here's a pure implementation of push and pop functionality of  string[] array in C Sharp, with timings. 

It does not use Queue<T> or Stack

For reference, Microsoft's own C# Stack implementation copies to an array! 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// Pushes an item to the top of the stack.
        // 
        /// <include file='doc\Stack.uex' path='docs/doc[@for="Stack.Push"]/*' />
        public void Push(T item) {
            if (_size == _array.Length) {
                T[] newArray = new T[(_array.Length == 0) ? _defaultCapacity : 2*_array.Length];
                Array.Copy(_array, 0, newArray, 0, _size);
                _array = newArray;
            }
            _array[_size++] = item;
            _version++;
        }



  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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
using System;

namespace FixedLengthStackImplementationofStackofStringsArray
{
    internal class Stack
    {
        static readonly int MAX = 3; //Max number of elements in string[] array
        int count; 

        string[] stack = new string[MAX];

        public Stack() //constructor
        {
            count = 1;           //initialize stack with how many default values 
            stack = new string[] { "x", "y", "z", "w" }; //w is ignored, no error given
        }

        public bool IsEmpty()
        {
            return (count == 0);
        }

        public bool IsFull()
        {
            return (count == MAX);
        }

        public int Length()
        {
            return MAX;
        }
 
        public int Count()
        {
            return count;
        }

        internal void Push(string data)
        {
            if (count > 0)
            {
                for (int i = 0; i <= MAX - 2; i++) //inline copy fast
                    stack[i] = stack[i + 1];

                stack[MAX - 1] = data; //always same place at top, which in this case is last element of array!

                if (count < MAX) 
                    count++;
                else
                    Console.WriteLine("Max array size exceeded. Roll off the end.");
                
                Console.WriteLine("count=" + count + ", Push = " + data);
                
            }
            else
            {
                count++;
                stack[MAX - 1] = data;

                Console.WriteLine("count=" + count + ", Push = " + data);
            }

        }

        internal string Pop()
        {

            if (count > 0)
                count--;
            else 
                return stack[MAX - 1]; 

            string popValue = stack[MAX - 1]; //pop value on top of array

            Console.WriteLine("count = " + count + ", Pop = " + popValue);

            for (int i = MAX - 1; i >= 1; i--) //inline copy fast
            {
                stack[i] = stack[i - 1];
            }

            stack[0] = "empty"; //initialize bottom of stack, gets empty string

            return popValue;

        }

        internal string Peek() //traditional definition of top
        {
            return stack[MAX - 1];
        }

        internal string Top() 
        {
            return stack[MAX - 1];
        }
        internal void PrintTop()
        {
            Console.WriteLine("The topmost element of Stack is : {0}", stack[MAX - 1]);
        }
        internal void PrintStack()
        {
            Console.WriteLine("Printing Stack with {0} items:", count);
            for (int i = MAX - 1; i >= 0; i--)
            {
                Console.Write("arr[" + i + "]=" + stack[i] + ",");
            }
            Console.WriteLine();
            Console.WriteLine();
        }

    }

    public static class Program
    {
        public static void Main()
        {
            Stack s = new Stack();

            Console.WriteLine("Pop/Push Array Test");
            Console.WriteLine("Arr Len = " + s.Length().ToString());
            Console.WriteLine("Top of stack is at index = " + (s.Length()-1).ToString());
            s.PrintTop();
            s.PrintStack();
            

            s.Push("a");
            s.PrintTop();
            s.PrintStack();
            s.Push("b");
            s.PrintTop();
            s.PrintStack();
            s.Push("c");
            s.PrintTop();
            s.PrintStack();

            s.PrintStack();
            s.Push("d");
            s.PrintTop();
            s.PrintStack();
            s.Push("e");
            s.PrintStack();
            s.PrintTop();
            s.Push("f");
            s.PrintStack();
            s.PrintTop();
            s.Push("g");
            s.PrintStack();
            s.PrintTop();
            Console.WriteLine("Item popped from Stack : {0}", s.Pop());
            s.PrintStack();
            Console.WriteLine("Item popped from Stack : {0}", s.Pop());
            s.PrintStack();
            Console.WriteLine("Item popped from Stack : {0}", s.Pop());
            s.PrintStack();
            Console.WriteLine("Item popped from Stack : {0}", s.Pop());
            s.PrintStack();

            Console.ReadKey(); 
        }
    }
}

1st version below
This investigates using Array.Copy as Microsoft's own C# solution for Stack implementation, but is slow, compared to method above.



 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
using System;using System.Diagnostics;using System.Linq;public static class Program 
{
 public static void PushStringCopyArray(ref string[] array, string pushvalue) {
  
        string[] temp = new string[array.Length];
        temp[0] = pushvalue;

        Array.Copy(array, 0, temp, 1, array.Length - 1);

        array = temp;
 }

 public static void PushStringArray(ref string[] array, string pushvalue) {
  
        int newLength = array.Length;
        string[] temp = new string[array.Length];

        temp[0] = pushvalue; //push new value on top of array

        for (int i = 0; i < array.Length - 1; i++)
        temp[i + 1] = array[i];

        array = temp;

 }
 /// <summary>
 /// Pop value from top of string[] ref array
 /// </summary>
 public static string PopStringArray(ref string[] array) {
  
        int newLength = array.Length;
        //string[] temp = new string[array.Length]; //default value is ""
        string[] temp = Enumerable.Repeat("#", array.Length).ToArray(); //set a default value

        string popvalue = array[0]; ////push new value on top of array

        for (int i = array.Length - 1; i >= 1; i--)
        temp[i - 1] = array[i];

        array = temp;

        return popvalue;
 }

 public static void PrintArray(ref string[] array) {
        for (int i = 0; i < array.Length; i++)
        Console.Write("a[" + i + "]=" + array[i] + ",");
        Console.WriteLine();
        Console.WriteLine();
 }

public static void Main() {
    Stopwatch sw = new Stopwatch();
    string[] test = new string[] {"z","a","b","c"};

    Console.WriteLine("Pop/Push Array Test");
    Console.WriteLine("Arr Len=" + test.Length);
    PrintArray(ref test);
    PushStringArray(ref test, "1st");
    PrintArray(ref test);
    PushStringArray(ref test, "2nd");
    PrintArray(ref test);
    PushStringArray(ref test, "3rd");
    PrintArray(ref test);

    sw.Start();
    PushStringArray(ref test, "4th");
    sw.Stop();
    Console.WriteLine(sw.ElapsedTicks + " ticks. WOW! For loop, but still O(n).");
    PrintArray(ref test);

    sw.Start();
    PushStringCopyArray(ref test, "5th");
    sw.Stop();
    Console.WriteLine(sw.ElapsedTicks + " ticks. Array.Copy:  I thought this would be better.");
    PrintArray(ref test);

    Console.WriteLine(PopStringArray(ref test));
    PrintArray(ref test);
    Console.WriteLine(PopStringArray(ref test));
    PrintArray(ref test);
    Console.WriteLine(PopStringArray(ref test));
    PrintArray(ref test);
    Console.WriteLine(PopStringArray(ref test));
    PrintArray(ref test);
    Console.WriteLine(PopStringArray(ref test));
    PrintArray(ref test);
}
}

No comments:

Post a Comment