A stack is an abstract data structure which uses an order of operations called LIFO (Last In First Out) which does as it says on the tin, the last element added to the stack will be the first one to be removed.
You can think of this like a stack of plates, adding or removing plates is only possible from the top of the stack.
Thus, a stack controls elements held within via two principal operations:
- The
pushoperation adds an element to the collection - The
popoperation removes the most recent element in the collection
There are a few other methods which we will implement but the ordering combined with these operations are the signature of a stack.
Stacks are used in a variety of ways in the real world, for example the JavaScript Call Stack is a stack which tracks function calls and allows the browser to track all the various things being executed as they run without conflicts between calls occurring.
In this article we will explore how I would implement a stack and I will also explain each method we implement in detail.
Tests
For the tests of our stack I will be using the Jest test runner alongside ts-jest which will support us to test our TypeScript implementation.
let stack: Stack<number>;
beforeEach(() => {
stack = new Stack<number>();
});
describe("Stack", () => {
it("Should have predictable defaults", () => {
expect(stack.count).toBe(0);
expect(stack.items).toEqual([]);
});
it("Should add an item to the stack", () => {
stack.push(1);
expect(stack.count).toBe(1);
});
it("Should return the index of the item added to the stack", () => {
expect(stack.push(1)).toBe(0);
});
it("Should remove an item from the stack", () => {
stack.push(1);
expect(stack.count).toBe(1);
expect(stack.items).toEqual([1]);
stack.pop();
expect(stack.count).toBe(0);
expect(stack.items).toEqual([]);
});
it("Should return the value of the item removed from the stack", () => {
stack.push(1);
expect(stack.pop()).toBe(1);
});
it("Should return undefined if no items exist in the stack when trying to pop the top value", () => {
expect(stack.pop()).toBe(undefined);
});
it("Should return undefined if the item being searched for doesn't exist", () => {
expect(stack.find(1)).toBe(undefined);
})
it("Should return the index of the value if it is found", () => {
stack.push(1);
expect(stack.find(1)).toBe(0);
});
it("Should allow us to peek at the item at the top of the stack", () => {
stack.push(1);
expect(stack.peek()).toBe(1);
});
it("Should return undefined if there is no item to peek at", () => {
expect(stack.peek()).toBe(undefined);
});
it("Should let us check if the stack is empty", () => {
expect(stack.empty()).toBe(true);
});
it("Should let us check how many items are in the stack", () => {
expect(stack.size()).toBe(0);
});
it("Should clear the stack", () => {
stack.push(1);
stack.push(1);
expect(stack.count).toBe(2);
expect(stack.items).toEqual([1, 1]);
stack.clear();
expect(stack.count).toBe(0);
expect(stack.items).toEqual([]);
});
});
For the tests I chose to use a Stack using number types for simplicity. If you want to explore and run the tests, you can use the repl below.
Implementation
For this implementation we will be using TypeScript.
class Stack<T> {
public items: T[] = [];
public count: number = 0;
push(item: T): number {
this.items[this.count] = item;
this.count++;
return this.count - 1;
}
pop(): T | undefined {
if(this.count === 0) return undefined;
this.count--;
const deletedItem = this.items[this.count];
this.items = this.items.slice(0, this.count);
return deletedItem;
}
find(value: T): number | undefined {
for(let index = 0; index < this.size(); index++) {
const item = this.items[index];
if(Object.is(item, value)) return index;
}
return undefined;
}
peek(): T | undefined {
return this.items[this.count - 1];
}
empty(): boolean {
return this.count === 0;
}
size(): number {
return this.count;
}
clear(): T[] {
this.items = [];
this.count = 0;
return this.items;
}
}
We are using Generics as a part of the implementation to provide opt-in type strictness for our stack, this is represented by the type T in the implementation above. To see this in action we can do this for example:
const stack = new Stack<number>();
stack.push(1); // Works fine
stack.push("1"); // Throws a TypeError
If no type T is provided then anything can be added into the stack like so:
const stack = new Stack();
stack.push(1); // Works fine
stack.push("1"); // Also works fine
Personally though, I would recommend that if you don't want to lock the types of the items in your stack then add the explicit any type to the T type instead since being explicit is always better than being implicit with such things, for example:
const stack = new Stack<any>();
stack.push(1); // Works fine
stack.push("1"); // Also works fine
Properties
Our Stack contains 2 properties, the items currently within the stack and the count of the items in the stack, we can access these like so:
const stack = new Stack();
console.log(stack.count); // 0
console.log(stack.items); // []
state.push(1);
console.log(stack.count); // 1
console.log(stack.items); // [1]
Methods
Alongside the properties of the Stack are it's methods, let's explore these and what they do a bit more.
push
The push method adds an item to the stack and returns the index of that item once added, for example:
const stack = new Stack();
const idx = stack.push(1);
const idx2 = stack.push(2);
console.log(idx, idx2, stack.items); // 0, 1, [1, 2]
pop
The pop method removes an item from the stack and returns the value of the removed item, for example:
const stack = new Stack();
stack.push(1);
stack.push(2);
const item = stack.pop();
console.log(item, stack.items); // 2, [1]
find
The find method finds an item in the stack and returns its index if it is found or undefined if it isn't, for example:
const stack = new Stack();
console.log(stack.find(1)); // undefined
stack.push(1);
console.log(stack.find(1)); // 0
peek
The peek method lets us check what item is currently at the top of the stack, for example:
const stack = new Stack();
stack.push(1);
console.log(stack.peek()); // 1
empty
The empty method lets us check if the stack is empty or not, for example:
const stack = new Stack();
console.log(stack.empty()); // true
stack.push(1);
console.log(stack.empty()); // false
size
The size method lets us see how many items are in the stack currently, for exmaple:
const stack = new Stack();
console.log(stack.size()); // 0
stack.push(1);
console.log(stack.size()); // 1
clear
The clear method lets us remove all items from the stack, for example:
const stack = new Stack();
stack.push(1);
stack.push(1);
stack.push(1);
console.log(stack.count, stack.items); // 3, [1, 1, 1]
stack.clear();
console.log(stack.count, stack.items); // 0, []
Conclusions
Stacks are really efficient data structures for setting, getting, deleting and finding a value, we can see that with the Big O of these operations coming in as follows:
| Average | Worst | |
|---|---|---|
| Get | Θ(n) | Θ(n) |
| Set | Θ(1) | Θ(1) |
| Delete | Θ(1) | Θ(1) |
| Find | Θ(n) | Θ(n) |
This makes it one of the most efficient data structures that you can use and this is why it one of the most common data structures you will come across when developing software.
I hope this post brought you some value and feel free to leave a comment below!
Top comments (2)
Interesting indeed. Elegantly laid out too! thanks for sharing James!
You're welcome Dan, glad you found some value in the post, thanks for dropping by!