The stack
A Stack, also known as a Stack, is a linear table with limited operations. Defines linear tables that only perform insert and delete operations at the end of the table. This end is called the top of the stack, and the other end is called the bottom of the stack. Adding a new element to a stack is also called pushing, pushing, or pushing. It is done by placing the new element on top of the top element to make it the new top element. To remove an element from a stack, also known as unstack or unstack, is to remove the top element from the stack so that the adjacent element becomes the new top element.
A stack is an abstract data structure with “first in, last out” characteristics, which can be implemented using arrays or linked lists. Stacks implemented using arrays also become sequential stacks, and stacks implemented using linked lists become linked stacks
“First in, last out” can be compared to a pistol magazine, in which the first bullet in the clip is fired last, while the last bullet in the clip is fired first.
The name of the pushing method is usually called push, and the name of the pushing method is usually called pop.
Which method name you use is entirely up to you, but for the sake of specification, we’ll stick with push and pop, okay
So let’s draw a picture of what’s going on and what’s going on
stack.push(1); // Element 1 is pushed
stack.push(2); // Element 2 is pushed
stack.pop(); // unstack -> element 2
stack.pop(); // unstack -> element 1
Copy the code
There’s no problem. That seems pretty straightforward. So-called into after the first like you go to work by bus, the passengers to get on the bus driver always told you to walk in, because it “location”, but always get off the bus after the bus passengers get off first, because near the door, but passengers to get on the bus because inside the sitting position, far from the door, always after get off.
Advantages and disadvantages of sequential stack and linked stack
As mentioned above, stacks can be implemented using arrays or linked lists. Stacks implemented using arrays are also called sequential stacks, and stacks implemented using linked lists are called linked stacks
But what are the pros and cons of the two stacks, and how should we choose between them? First we need to know the pros and cons of arrays and linked lists
If you don’t know about arrays and linked lists, see:
Array structure (Array)
Linked- List data structure
Advantages and disadvantages of arrays:
Advantages: Arrays have very efficient random access, as long as the subscript is given, you can find the corresponding element in constant time.
Disadvantages: The disadvantages of arrays are the insertion and deletion of elements. As array elements are continuously and closely stored in memory, inserting or deleting elements will cause a large number of elements to be moved or re-opened for memory expansion, affecting efficiency.
Bottom line: Arrays are best suited for scenarios with lots of reads and few writes!
Advantages and disadvantages of linked lists:
Advantages: Fast insertion and deletion, retain the original logical order, when inserting or deleting an element, only need to change the pointer pointer. There is no space limit, there is no upper limit to the storage elements, only the size of the memory space.
Disadvantages: The search speed is slow, because in the search, you need to loop through the list.
Summary: Linked lists are suitable for scenarios with fewer reads and more writes!
Stack features:
- The number of elements is not fixed
- Frequent insert and delete operations (push and pop) on the end of a linear table
In any case, using a linked list to implement a stack is a better choice, but sequential storage of arrays can also be beneficial if we can avoid the disadvantages of arrays by using stacks.
Js arrays already contain stack-compliant push and pop methods, so arrays are often used as stacks in JS, so you don’t have to implement them yourself. However, due to the expansion and contraction mechanism of v8 arrays, performance may not be perfect
For those unfamiliar with the v8 Array expansion and contraction mechanism, check out my previous article: How do Array structures and deep V8-JS arrays allocate memory
Order of the stack
Sequential stacks are implemented using arrays, with the first entry of the array as the bottom of the stack, and then maintaining a pointer to the top of the stack. Due to the disadvantages of arrays, we should try to use a fixed stack size, that is, limit the number of elements on the stack. Below is a stack of size 5.
When the top pointer is -1, there is no element in the stack, that is, the empty stack
Let’s look at a simple simulation implementation
class Stack{
constructor(length) {
this.stack = Array(length);
this.maxLength = length;
this.stackTop = -1;
}
push(value){
// Check whether the stack is full
if(this.stackTop === this.maxLength-1) {return false;
}
this.stack[++this.stackTop] = value
return true
}
pop(){
// Check whether the stack is empty
if(this.stackTop === -1) {return ;
}
// Move the pointer to the top of the stack. The next push is automatically overwritten
return this.stack[this.stackTop--];
}
toString(){
if(this.stackTop === -1) {return 'empty stack'
}
return this.stack
.slice(0.this.stackTop+1)
.join('- >')}}const stack = new Stack(5)
console.log(stack.toString());// empty stack
console.log('push(1)', stack.push(1));// push(1) true
console.log(stack.toString());/ / 1
console.log('push(2)', stack.push(2));// push(2) true
console.log(stack.toString());/ / 1 - > 2
console.log('pop()', stack.pop());// pop() 2
console.log(stack.toString());/ / 1
console.log('pop()', stack.pop());// pop() 1
console.log(stack.toString());// empty stack
Copy the codeExtension – Shared stack
Let’s start with a scene
There are now two stacks of capacity 5, where stack 1 is full and stack 2 has only one element. Now if you want to push a new element 2 onto stack 1, the push will fail because stack 1 is full, but stack 2 has a lot of empty space.
This is annoying because memory space is not being used well. So people came up with a way to make the two stacks share the same memory space to make better use of the space. This stack is also called a shared stack
A shared stack uses two Pointers to the top of each stack
Shared stacks are rarely used in algorithms, but they are common in operating systems or hardware layers, where resources are limited and need to be shared to optimize resource utilization
Chain stack
There is a problem with implementing a stack using a linked list: do you use the head or tail pointer of the list as the top of the stack?
Since all stack operations operate from the top of the stack, the bottom of the stack does not need to worry about Pointers. Now we just need to choose between the head pointer and the tail pointer as the top of the stack.
Select tail pointer:
If we choose the tail pointer as the top of the stack, then when we push it, we just put rear. Next = node; Rear = node. Tail Pointers make it easy to add nodes to the end of a list.
The only way to get the previous element is to iterate over the ab initio pointer, because the only way to get the previous element is to iterate over the ab initio pointer. But traversal can be time consuming.
Select header pointer:
Next = head; node.next = head; head = node; Head = head. Next; . As you can see, header insertions and header deletions are very fast.
In contrast, we can see that it is better to use the header pointer as the top of the stack. Therefore, we choose to use the header pointer as the top of the stack. With the header pointer, we can complete the header insertion and deletion operation quickly and conveniently.
/ / stack node
class StackNode {
constructor(value, next = null) {
this.value = value;
this.next = next; }}/ / stack
class Stack {
constructor(){
this.head = null
}
/ / into the stack
push(value){
// Create a new node and point next to the header pointer, which then points to the new node
this.head = new StackNode(value, this.head);
// If you can't read above, you can read below
// let pushNode = new StackNode()
// pushNode.value = value
// pushNode.next = this.head
// this.head = pushNode
}
/ / out of the stack
pop(){
// Check whether the stack is empty
if(!this.head){
return ;
}
// Get the node to be removed from the stack
let popNode = this.head
// The header pointer moves back
this.head = popNode.next
return popNode.value
}
toString(){
let str = ' '
let node = this.head
while (node){
str += node.value + '- >'
node = node.next
}
return `Stack(${str.slice(0, -2)}) `; }}let stack = new Stack()
console.log(stack.toString());// Stack()
stack.push(1); // Element 1 is pushed
console.log(stack.toString());// Stack(1)
stack.push(2); // Element 2 is pushed
console.log(stack.toString());// Stack(2->1
stack.pop(); // unstack -> element 2
console.log(stack.toString());// Stack(1)
stack.pop(); // unstack -> element 1
console.log(stack.toString());// Stack()
Copy the codeThe implementation of the stack is very simple. If you are not familiar with the operation and principle of Linked lists, you can refer to my other article on data structure diagram JS – Linked-list structure.
Leetcode of actual combat
Once we understand the implementation and principle of the stack, we also need to know when to switch to the stack and how to use the stack structure to solve problems.
Here are two examples of typical topics in Leetcode
Difficulty: one easy and one medium (why not? Because I can’t handle the hard ones.
The following questions have a high interview record
20. Valid brackets
Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.
A valid string must meet the following requirements:
- An open parenthesis must be closed with a close parenthesis of the same type.
- The left parentheses must be closed in the correct order.
Example 1: Input: s = "()" Output: true Example 2: Input: S = "()[]{}" Output: true Example 3: Input: S = "(]" Output: false Example 4: Input: S = "([)]" Output: false Example 5: Input: s = "{[]}" Output: trueCopy the codeTip:
1 <= s.length <= 104, s consists only of parentheses ‘()[]{}’
Symbol matching in pairs and postfix expression topic can first consider stack, such as the subject, for example, whenever meet ({[into the stack, met)}] into the top of stack elements, if the pair continue, not to return the failure;
/ * * *@param {string} s
* @return {boolean}* /
var isValid = function(s) {
// The Stack structure is not provided in javascript, so you need to copy the above Stack implementation. I won't copy it here for space reasons
let stack = new Stack()
for(let char of s){
// open parenthesis on the stack
if('({['.includes(char)){
stack.push(char)
}else {
// The left parenthesis matches the right parenthesis. If it does not match or is empty, the parenthesis is invalid
switch (stack.pop()){
case '(':
if(char ! = =') ') return false;
break;
case '{':
if(char ! = ='} ') return false;
break;
case '[':
if(char ! = ='] ') return false;
break;
/ / is empty
default: return false; }}}// If the stack is empty, all parentheses match and return true, otherwise return false
return! stack.pop() };Copy the code143. String decoding
Given an encoded string, return its decoded string.
The encoding rule is k[encoded_string], indicating that the encoded_string inside the square brackets is repeated exactly K times. Note that k is guaranteed to be a positive integer.
You can assume that the input string is always valid; There are no extra Spaces in the input string, and the input square brackets are always formatted.
In addition, you can assume that the raw data does not contain numbers, and that all numbers represent only the number of repetitions k, such as no input like 3a or 2[4].
Example 1: Input: S = "3[a]2[BC]" Output: "aaABCBC" Example 2: Input: S = "3[A2 [c]]" Output: "Accaccacc" Example 3: Input: S = "2[ABC]3[CD]ef" Output: "Abcabccdcdcdef" Example 4: Input: s = "abc3[CD]xyz" Output: "abccdcdcdXYZ"Copy the code
- Store two pieces of information on the stack at a time (string before parenthesis, number before parenthesis)
3[a2[c]]When the first open parenthesis is encountered, is pushed onto the stack(" ", 3)“, and iterates through the string in parenthesesa2[c], the second open parenthesis is pushed into the stack("a", 2)“, and then continue iterating through the stack to get a new string when a close parenthesis is encounteredstr = t[0] + str.repeat(t[1])That isacc, and then it hits the second close bracket and continues out of the stack, and getsaccaccacc - Open parenthesis is used to push the stack, close parenthesis is used to pop the stack, the element of the stack is very important.
function decodeString(s){
let stack = new Stack()
// Record characters
let str = ' ';
// Record the number
let num = ' ';
for(let char of s){
// it encounters [, and is pushed
if(char === '['){
stack.push([str, num]);
/ / reset
str = ' '
num = ' '
}
else if(char === '] ') {// Close parenthesis is encountered and the result is concatenated
let t = stack.pop();
str = t[0] + str.repeat(+t[1]);
}
else if(char >= '0' && char <= '9') {// When a number is encountered, record
num += char;
}else {
// When a character is encountered, record itstr += char; }}return str;
}
Copy the code