preface
As a data structure, the stack can be used in many places, and it is the data structure of choice when you need to retrieve data that has just been stored.
There are generally two implementations of stacks: arrays and objects, both of which end up doing the same thing, but are quite different in terms of performance.
This article elaborates on the differences between these two implementations and uses TypeScript to implement them. Interested developers are welcome to read this article.
Array implementation stack
This article explains the implementation of stack code, if you are not familiar with the stack data structure, you can move on to my other article: stacks and queues
Implementation approach
The core idea of the stack is last in, first out (LIFO), so we can use arrays to describe the stack.
Next, let’s take a look at what a stack needs to do:
- Adds a new element to the top of the stack (the end of the array).
- Remove the top element from the stack and return the removed element.
- Gets the top of the stack element, and returns the current top of the stack element.
- Check whether the stack is empty, check whether there is data in the stack (array).
- Clear the stack, remove all elements in the stack.
- Gets the stack size and returns the number of elements in the stack.
- Outputs stack data, returning all elements in the stack as strings.
❝
After analyzing what the stack needs to do, we found that arrays provide a lot of ready-made apis to do this. Next, we share the idea of how to do this.
- Push, you can use the array’s push method to add elements directly to the end of the array.
- Out of the stack (POP), you can remove elements from the stack directly using the array’s POP method, which returns the currently removed element.
- Top of stack element (PEEK), the last element in the array can be obtained by the array length -1.
- Whether the stack is isEmpty can be determined by determining whether the length of the array is 0.
- To clear the stack, you can either assign an array value to empty or call the stack method until the data in the stack is empty.
- Stack size (size), which can return the length of the array.
- Output stack data, you can call the array toString method to convert the array to a string.
The implementation code
Now that we have an implementation idea, we can translate the implementation idea into code.
- Create a new stack.ts file
- Define the stack and specify its type
private items: any[];
Copy the code- Initialize the stack in the constructor
constructor() {
this.items = [];
}
Copy the code- According to the implementation of the stack of functions
/ / into the stack
push(item:any) {
this.items.push(item);
}
/ / out of the stack
pop() { return this.items.pop(); } // Return the top element of the stack peek() { return this.items[this.items.length - 1]; } // Check whether the stack is empty isEmpty() { return this.items.length === 0; } // Clear the stack element clear() { this.items = []; } // Get the number of stack elements size():number{ return this.items.length; } // Convert stack elements to strings toString(){ return this.items.toString(); } Copy the codeFor the complete code, go to stack.ts
Write test code
We implemented a stack in the above code, and then we added a few pieces of data to the stack to test whether the method in the stack executed correctly.
- Create a new stacktest.js file
- Instantiate a stack
const stack = new Stack();
Copy the code- Tests whether the stack method executes correctly
/ / into the stack
stack.push("Number one");
stack.push("Number two");
/ / out of the stack
stack.pop(); // Return the top element of the stack console.log(stack.peek()); // Check the stack size console.log(stack.size()); // Check whether the stack is empty console.log(stack.isEmpty()); // Return all elements in the stack console.log(stack.toString()) / / empty stack stack.clear() Copy the codeFor the complete code, go to stacktest.js
The result is as follows
Object implementation stack
The simplest way to implement a stack is to store each element in an array. When dealing with large amounts of data, we need to evaluate how to manipulate the data most efficiently.
When using arrays, most methods are O(n) in time, and we need to iterate through the array until we find the target element, and in the worst case we need to iterate through every position in the array. An array is an ordered collection of elements, which takes up more memory to keep the elements organized.
If we can get the elements directly, take up less memory, and still make sure that everything is arranged the way we want it to be, that would be the optimal solution.
The implementation code
We can use a single object to store all stack elements, keeping them in order and following LIFO principles. Let’s take a look at how to implement stacks using objects.
- Create a new objStack.ts file
- Define the stack object structure
interface StackObj {
[propName: number] : any;
}
Copy the code- Define the stack and specify its type, and count is used to record the stack size.
private items: StackObj;
private count: number;
Copy the code- Initialize stack-related variables in the constructor
this.items = {};
this.count = 0;
Copy the code- The current stack size is the key of the new element.
push(item: any) {
this.items[this.count] = item;
this.count++;
}
Copy the code- Unstack, current stack size -1, retrieves the top element, deletes the top element, and returns the removed top element
pop() {
if(this.isEmpty()){
return undefined;
}
this.count--;
const result = this.items[this.count]; delete this.items[this.count]; console.log(this.items); return result; } Copy the code- Return the top element of the stack, with the current stack size -1 as the key and its corresponding value.
peek() {
if(this.isEmpty()){
return undefined;
}
return this.items[this.count - 1];
} Copy the code- Determine whether the stack is empty, empty the elements in the stack, obtain the number of elements in the stack
// Check whether the stack is empty
isEmpty() {
return this.count === 0;
}
// Clear the stack
clear() { this.items = []; this.count = 0; } // Get the number of stack elements size():number{ return this.count; } Copy the code- Converts the stack element to a string, traverses the data in the current stack object, concatenates the data in the stack with commas and returns it.
toString(){
if (this.isEmpty()){
return "";
}
let objString = `The ${this.items[0]}`;
for (let i = 1; i < this.count; i++){ objString = `${objString}.The ${this.items[i]}` } return objString; } Copy the codeFor the complete code, go to objStack.ts
Write test code
In the above code, we implemented a stack with objects, and then we added a few pieces of data to the stack to test whether the methods in the stack executed correctly.
- Create a new stackObjtest.js file
- Instantiate a stack
const stack = new ObjStack();
Copy the code- Tests whether the stack method executes correctly
/ / into the stack
stack.push("Number one");
stack.push("Number two");
/ / out of the stack
stack.pop(); // Return the top element of the stack console.log(stack.peek()); // Check the stack size console.log(stack.size()); // Check whether the stack is empty console.log(stack.isEmpty()); // Return all elements in the stack console.log(stack.toString()) / / empty stack stack.clear() Copy the codeFor the complete code, go to stackObjtest.js
The result is as follows
The difference between the two
The time complexity of most methods in an array is O(n). The elements in an array are an ordered collection, which takes up more memory space to ensure that the elements are arranged in an orderly manner.
The object can be accessed directly to the target element through the key with the time complexity of O(1). We can operate directly on the target element, which is obviously many times faster than array.
Let’s look at the difference in execution speed between the two using an example.
Decimal to binary
Converting a decimal system to binary requires dividing the decimal system by 2 and rounding the quotient until the result is 0.
- Declares a function argument as a decimal number
const decimalToBinaryStack = function (decNumber) {
}
Copy the code- The function internally declares a variable that receives the value of the currently passed argument by division.
// The decimal number passed in
let number = decNumber;
Copy the code- The function internally instantiates a stack that holds the value of the modular operation.
- The function internally declares two variables, and the user saves the value of the current module operation and the resulting binary string
/ / remainder
let rem;
// Binary result
let binaryString = "";
Copy the code- In the while loop, judge whether the value obtained after the division operation of the current parameter is 0. If not, perform modular operation on the current result, push the value obtained by the modular operation onto the stack, and divide the current result until the current result is 0.
while (number > 0) {
/ / operator
rem = Math.floor(number % 2);
// push the remainder onto the stack
stack.push(rem);
// Divide the current decimal result by two number = Math.floor(number / 2); } Copy the code- A while loop that takes data from the stack and concatenates it into a binary result string
while(! stack.isEmpty()) { binaryString += stack.pop().toString();
}
Copy the code- Returns a binary result string
return binaryString;
Copy the codeFor complete code, go to examples.js
❝
As described above, the only difference is that one uses an object stack and one uses an array stack, so let’s look at the time difference between the stacks.
Write in the last
- If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
- This article was first published in nuggets. Reprint is prohibited without permission 💌