Array-based stack

⏱️ Estimated Reading Time: ~6 min read
0
(0)

A stack is a data structure that operates on the LIFO (Last In, First Out) principle. Graphically, a stack can be represented as a column or stack of objects:

 

365

The stack has a top, which is formed by the most recently added element. When the new element is placed on top of the stack, forming a new top. When deleting, the element at the top of the stack is removed, and the previous element forms the new top.

So, in the figure above, the top of the stack is initially “Tom.” After adding a new element, “Bob,” this element is positioned on top of “Tom,” becoming the new top.

The .NET class library already has a class that functions as a stack. This class is System.Collections.Generic.Stack. But let’s look at how we can implement a stack-like structure ourselves.

The stack structure, regardless of programming language, has a certain common functionality, which consists of a method for adding an element (usually called push()) and a method for popping an element from the top of the stack (usually called pop()). Furthermore, stack implementations often include a method for getting an element from the top without popping it, a method for determining the stack size, and several others.

To begin with, to implement the data structure, we define the following class:

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
public class FixedStack<T>
{
private T[] items; // stack elements
private int count; // number of elements
const int n = 10; // default array size

public FixedStack()
{
items = new T[n];
}

public FixedStack(int length)
{
items = new T[length];
}

// whether the stack is empty
public bool IsEmpty
{
get { return count == 0; }
}

// stack size
public int Count
{
get { return count; }
}

// adding an element
public void Push(T item)
{
// if the stack is full, throw an exception
if (count == items.Length)
throw new InvalidOperationException(“Stack overflow”);

items[count++] = item;
}

// extracting an element
public T Pop()
{
// if the stack is empty, throw an exception
if (IsEmpty)
throw new InvalidOperationException(“Stack is empty”);

T item = items[–count];
items[count] = default(T); // reset reference to clear the cell
return item;
}

// returning the element from the top of the stack
public T Peek()
{
// if the stack is empty, throw an exception
if (IsEmpty)
throw new InvalidOperationException(“Stack is empty”);

return items[count – 1];
}
}

This implementation represents a generic class, allowing it to store elements of any type. The elements themselves will actually be stored in the items array. The variable is used to store the actual number of elements added to the stack count.

Two constructors are used to initialize the stack. The constructor without parameters creates an array named items with a length of 10. The constructor with a parameter allows you to manually set the array length.

In the method, Push()we add an element to the array, incrementing the count variable. If the stack (or, in fact, the items array) is already full, we throw an exception.

In the method, Pop()We pop an element from the top of the stack, decrementing the count variable. If there are no elements on the stack, we throw an exception.

Stack usage:

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
static void Main(string[] args)
{
try
{
FixedStack<string> stack = new FixedStack<string>(8);

// adding four elements
stack.Push(“Kate”);
stack.Push(“Sam”);
stack.Push(“Alice”);
stack.Push(“Tom”);

// extracting one element
var head = stack.Pop();
Console.WriteLine(head); // Tom

// simply getting the top of the stack without extracting it
head = stack.Peek();
Console.WriteLine(head); // Alice
}
catch (InvalidOperationException ex)
{
Console.WriteLine(ex.Message);
}

Console.Read();
}

Schematically, all operations can be expressed as follows:

 

365

However, it should be noted that this stack has one significant drawback: if we don’t initially know exactly how many elements the stack will hold—10, 15, 100, 200, etc.—the fixed array length imposes a limitation on stack manipulation. To solve this problem, we need to dynamically change the array length as it grows or shrinks, up to a certain point. So, let’s define the following stack class:

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
public class Stack<T>
{
private T[] items;
private int count;
const int n = 10;

public Stack()
{
items = new T[n];
}

public Stack(int length)
{
items = new T[length];
}

public bool IsEmpty
{
get { return count == 0; }
}

public int Count
{
get { return count; }
}

public void Push(T item)
{
// grow the stack capacity if it’s full
if (count == items.Length)
Resize(items.Length + 10);

items[count++] = item;
}

public T Pop()
{
// if the stack is empty, throw an exception
if (IsEmpty)
throw new InvalidOperationException(“Stack is empty”);

T item = items[–count];
items[count] = default(T); // reset the reference to clear the cell

// shrink the stack capacity if there’s significant unused space
if (count > 0 && count < items.Length – 10)
Resize(items.Length – 10);

return item;
}

public T Peek()
{
if (IsEmpty)
throw new InvalidOperationException(“Stack is empty”);

return items[count – 1];
}

private void Resize(int max)
{
T[] tempItems = new T[max];
for (int i = 0; i < count; i++)
tempItems[i] = items[i];
items = tempItems;
}
}

In this case, compared to the previous example, a method has been added to the stack class Resizethat resizes the array to the max value. To do this, the method simply creates a new array and copies the data from the old one into it.

Now, when adding items to the method, Push()we no longer need to check the stack for overflow. If there’s suddenly no more room in the items array, we’ll call the Resize function, which will increase the array by 10 elements:

1
2
3
if (count == items.Length)

When deleting an element in the Pop method, we similarly change the size if more than 10 empty cells are formed in the items array.

Here, when adding and removing elements, the number of elements changes by 10. This can be increased or decreased by a factor of two, etc. However, it’s important to remember that initially allocating large amounts of memory will increase the total memory consumed by the application. However, there’s no guarantee that even half of this memory will be used.

At the same time, if you gradually increase/decrease the array size, this will increase the frequency of memory reallocation, which ultimately leads to a decrease in performance.

Thus, the stack has become more flexible in terms of array sizes, but it retains a number of the drawbacks associated with arrays, such as the need to reallocate memory when adding or deleting data, and increased complexity of the computational algorithm. We’ll discuss how to address these drawbacks below.

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Explore More IT Terms

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Share this term: Facebook X LinkedIn WhatsApp Email
CONTINUE LEARNING Next: Stack →

RELATED ARTICLES

Complexity of algorithms-Tutorial

    Algorithm complexity: deep parsing O(log n)

    Algorithm complexity: deep parsing O(log n)

      Algorithm Analysis

        Homogeneous vs. non-homogeneous structures

        Homogeneous vs. non-homogeneous structures

          Static vs. dynamic data structures

          Static vs. dynamic data structures

            Linear vs. non-linear data structures

            Linear vs. non-linear data structures

              Leave a Reply

              Your email address will not be published. Required fields are marked *

              Powered by