A Stack is a LIFO (LAST IN FIRST OUT) Data Structure that allows you to push more than one value onto the stack without first popping previous values off the stack. Using stack you should be able to do at least four operations:

In this topic, I’m going to cover two different types of implementation of a stack, Linked-list and Arrays.

Linked-list implementation

A linked list is a sequence of elements, except most implementations, refer to the elements as nodes (a node is an abstract entity that might hold any kind of data). In a linked list, the nodes are not contained in an array structure, but rather a node exists in memory to identify the first element. Then each node contains a link to the subsequent node in the list, by convention, the link in the last node is null, to indicate that it terminates the list.

Array implementation

Representing stacks with arrays usually is a natural idea, but there are a few problems in this implementation that we are going to check. The first problem that you may encounter is the array size, one solution for this problem is to start the array with a predefined size, and every time that you need to increase the size you need to copy the holding structure to a new array with a new size, which is unnecessarily inefficient and cumbersome. (I will create a constructor with a predefined size, for now, we will return to this item in the topic below). The second problem is the way how we access the elements in the stack, the most recent item in items[0] and the least recently inserted item in items[n-1]. Usually, when you pop or push an element from the stack we would have to move all of the other items to reflect the new state of the stack (not efficient), what we can do to fix it is use the positions to access the right information N > 0 ? N-1 : 0.

Considerations

The number of items in the stack is N.

The stack is empty when N is 0.

The stack items are stored in the array in the order in which they were inserted.

The most recently inserted item (if not empty) is items[n-1].

Underflow: throw an exception if pop from an empty stack

Overflow: use resizing array for array implementation

Null items are allowed to be inserted

Loitering, holding a reference to an object when it is no longer needed.

Resizing Arrays

As I mentioned in the section above I’m going to talk about our old “problem”, how to resize the array. In the previous example, we used a fixed size in the constructor to help us create our stack but that was not a solution was just a small fix, regular arrays of objects or primitives can’t be dynamically resized, every time that we decide to include information in a full array the common solution is to copy all item to a new array and replace the old one but the problem is this resizing is not cheap and this is what I’m going to show how to handle it.

Before we start one thing that we need to ensure is the array resizing happens infrequently, so the idea is to modify the array implementation to dynamically adjust the length of the array so that it is sufficiently large to hold all of the items but not so large as to waste an excessive amount of memory.

First, in push(), we check whether the array is too small. In particular, we check whether there is room for the new item in the array by checking whether the stack size n is equal to the array length items.length. If there is room, we simply insert the new item with the code items[n++] = item as before; if not, we double the length of the array by creating a new array of twice the length, copying the stack items to the new array, and resetting the items[] instance variable to reference the new array.

public void push(String item) {
    if (n == items.length) {
      resize(items.length * 2);
    }
    items[n++] = item;
}
private void resize(int capacity) {
    String[] temp = new String[capacity];
    for (int i = 0; i < n; i++) {
      temp[i] = items[i];
    }
    items = temp;
}

Similarly, in pop(), we begin by checking whether the array is too large, and we halve its length if that is the case. If you think a bit about the situation, you will see that an appropriate test is whether the stack size is less than one-fourth of the array length. Then, after the array is halved, it will be about half full and can accommodate a substantial number of push() and pop()operations before having to change the length of the array again. This characteristic is important: for example, if we were to use a policy of having the array when the stack size is one-half the array length, then the resulting array would be full, which would mean it would be doubled for a push(), leading to the possibility of an expensive cycle of doubling and halving.

public String pop() {
    String item = items[--n];
    items[n] = null;
    if (n > 0 && n == items.length / 4) {
      resize(items.length / 2);
    }
    return item;
}

Resuming, now that we know how the Linked List and Array implementation of a Stack works, Which one is better?

Linked-list implementation:

Every operation takes constant time in the worst case.

Uses extra time and space to deal with the links.

(Resizing) Array Implementation:

Every operation takes constant amortized time.

Less wasted space

To answer the question, there is not a better solution, there are two options and now that you know how it works you can decide which one should you pick!

https://github.com/tiarebalbi/algorithms-demo/tree/master/src/main/java/com/tiarebalbi/section_one

----

“I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” — Linus Torvalds (creator of Linux)