The stack profile
What is a stack? The stack is a last in, first out (LIFO) data structure. What does a stack do? Stacks can simulate algorithms or lifo scenarios, such as:
- To convert from decimal to binary, you need to print the remainder in reverse order.
- The stack is used for middle and then non-recursive traversal of binary trees.
- In life, stack can simulate coal stove and briquettes and other scenes.
There is no need for JavaScript engineers to implement a stack in development. Because JavaScript’s built-in Array object already implements stack-related methods. However, good programmers can’t just use what others have designed and not understand why, so let’s design a stack of our own.
function Stack(){... }module.exports = Stack;
Copy the code
Private variables
The stack class’s private variable is an array of items, which records the elements of the stack. Objects generated by stack class instantiation cannot manipulate items directly, because items are not visible outside the function. You can only manipulate items indirectly along the scope chain through some class method.
function Stack() {
// Private variable items, used to record arrays, objects cannot be manipulated directly
var items = [];
}
Copy the code
Implement push, POP and toString methods and run the following tests:
// Instantiate a stack object
const stack = new Stack();
// Expect the stack to be empty
expect(stack.isEmpty()).toBeTruthy()
stack.push(4)
stack.push(7)
// Expect stack to delete and return 7
expect(stack.pop()).toBe(7)
// Expect stack to convert to string '4'
expect(stack.toString()).toBe('4')
Copy the code
The push, POP, and toString methods are the same as the Array push, POP, and toString methods, so the implementation code is as follows:
function Stack() {
// The private items variable is used to record arrays and cannot be manipulated directly
let items = [];
// The class method push, which adds elements to the end of the array, can be called directly
this.push = function (element) {
items.push(element);
}
// Remove and return the element at the end of the array
this.pop = function (element) {
return items.pop()
}
// Convert the array to a string and return it
this.toString = function () {
return items.toString()
}
}
Copy the code
Implement peek, isEmpty, clear, size methods implement peek, isEmpty, clear, size methods, and pass the following tests
stack.push(6)
// Expect the last element of the stack to be 6
expect(stack.peek()).toBe(6)
// Expect a stack length of 2
expect(stack.size()).toBe(2)
// Expect the stack not to be empty
expect(stack.isEmpty()).toBeFalsy()
stack.clear()
// Expect the stack length to be 0
expect(stack.size()).toBe(0)
Copy the code
The above method is relatively simple, directly on the code:
function Stack() {
// Private variable items, used to record arrays, objects cannot be manipulated directly
var items = [];
// Look at the last item in the array
this.peek = function () {
return items[items.length - 1];
};
// Check whether the array is empty
this.isEmpty = function () {
return items.length == 0;
};
// Empty the array
this.clear = function () {
items = [];
};
// Return the length of the array
this.size = function () {
return items.length;
};
}
Copy the code
Example code: github.com/gin280/java…