1. Introduction

There are several possible implementations of the stack data structure, based on fixed-size arrays, dynamic arrays, and linked lists.

In this tutorial, we’ll implement the stack using the fixed-size array representation.

2. Fixed-size Array Representation

In this representation, the stack effectively consists of the following data:

  • elements[] – the fixed-size array for keeping the stack elements
  • top – an integer counter holding the index of the stack’s top element
  • capacity – an integer value that defines the size of the elements[] array

In our discussion, we assume the array elements[] to be 1-indexed. So, the first inserted element of the stack has index 1. Similarly, the last inserted element has an index equal to the capacity.

Let’s go over the process of stack modification so we understand how the implementation operates. Assume we have an empty stack of integers with capacity=6:


empty stack

Let’s add integer 11 to the stack:


element stack

Next, we add two more integers, 7 and 25, to the stack. Note how top changes according to the elements added:


element stack

Finally, we remove the top element of the stack and get the following stack. Note that we do nothing with the element previously pointed by the top (25 in this case). We only update the top counter, and the previous top element will just get overwritten by a new value when new elements are added to the stack:


element stack

We ignore adding new elements to the stack when it’s full. Similarly, we do nothing when requests to remove elements and the stack is empty. Practically, it’s worth adding error-handling logic in these situations.

3. Stack Operations and Pseudocodes

Now, we’ll show how to implement the stack operations using the fixed-size array representation. The pseudocodes are short and easy to understand. Additionally, it’s straightforward to translate the pseudocodes to a programming language implementation.

3.1. Push

Below we can find the pseudocode of the push operation. The operation first checks if there’s a space for the new element. Then, it updates the top counter and adds the new element on top of the stack:

Rendered by QuickLaTeX.com

3.2. Pop

The pop operation’s logic is the opposite of push. First, it checks if there’re elements in the stack. Then, it updates the top counter to show the new top element of the stack:

Rendered by QuickLaTeX.com

3.3. Top

Top simply returns the top element of the stack:

Rendered by QuickLaTeX.com

3.4. Empty

To check if the stack contains any elements, the empty operation is used:

Rendered by QuickLaTeX.com

3.5. Full

The full operation checks another boundary condition – whether the stack is full and can’t accept new elements to be added:

Rendered by QuickLaTeX.com

4. Strengths and Weaknesses of the Implementation

The immediate benefit of the implementation is its easiness – it’s quite straightforward to understand and implement. Another benefit is the restriction on the number of elements that can be put into the stack. Consequently, the implementation naturally fits applications where the stack size needs to be limited.

On the other hand, the same feature of the limited size introduces a weakness – the implementation is hard to use for cases when the elements count is variable and isn’t known beforehand. In this case, reserving a big chunk of memory may be redundant. Contrarily, reserving a small chunk of memory may cause the to stack run out of memory, and we may have to use multiple stacks. Dynamic array and linked list implementations don’t have this limitation as they grow their capacity as needed.

5. Conclusion

In this topic, we’ve presented the fixed-size array representation of stacks. Additionally, we’ve provided the pseudocodes for the operations of the stack based on the representation. Finally, we’ve pointed out the strengths and weaknesses of the implementation.

Comments are closed on this article!