The stack and queue
An array of
- We know that arrays are linear structures and that you can insert and delete data anywhere in the array
- Sometimes, however, we need to implement certain features, and we must limit this arbitrariness
- Stacks and queues are common constrained linear structures
Stack Stack
A stack, “stack,” is a constrained linear table,Last in first Out (LIFO)
- The limitation is that only one end of the table is allowed for insert and delete operations. This end is called the top of the stack, and the other end is called the bottom of the stack
- LIFO(Last in First out) is the element that comes in later, the first one that pops out takes up space, similar to loading a gun into a magazine.
- 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, making 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.
Stack structure interview question
Option C is not a valid stack exit sequence resolution:
- Option A: 6, 5 in, 5 out, 4 in and out, 3 in and out, 6 out, 2, 1 in, 1 in, 2 out
- Option B: 6, 5, 4 in, 4 out, 5 out, 3 in and out, 2 in and out, 1 in and out, 6 out
- Option D: 6, 5, 4, 3, 2 on the stack, 2 off the stack, 3 off the stack, 4 off the stack, 1 on the stack, 5 off the stack, 6 off the stack
Implementation of common stack structure operations
Common stack operations:
- Push elements onto the stack
- Remove the top element and return the removed element (POP)
- Return top of stack element (peek)
- Check whether the stack is isEmpty
- Returns the number of elements in the stack (size)
- Returns the contents of the stack structure as characters (toString)
Stack operations based on arrays (JS code) :
// Implement stack operations based on arrays
class Stack{
// Attributes in the stack
items = []
// Stack related operations
// 1. Push the element to push
push(element){
this.items.push(element)
}
// 2. Fetch element pop from stack
pop(){
return this.items.pop()
}
// 3. Check the top element of the stack
peek(){
return this.items[this.items.length -1]}// 4. Check whether the stack is empty
isEmpty() {
return this.items.length === 0
}
// 5. Get the number of elements in the stack
size() {
return this.items.length
}
// 6. ToString method
toString() {
return this.items.join("")}}const s = new Stack()
s.push(10)
s.push(20)
s.push(30)
console.log(s);
s.pop()
console.log(s);
console.log(s.peek());
console.log(s.isEmpty());
console.log(s.size());
console.log(s.toString());
Copy the code
Use a stack structure to convert decimal to binary
The decimal to binary logic is shown below:
Decimal to binary code:
// Convert decimal to binary
function dec2Bin(decNumber) {
// 1. Define the stack object
const stack = new Stack()
// 2
while (decNumber > 0) {
// Get the remainder and put it on the stack
stack.push(decNumber % 2)
// Get the divisible result as a number for the next run
decNumber = Math.floor(decNumber / 2)}// return stack.items.reverse().join(""
// 3. Fetch 0 and 1 from stack
let binaryString = ' '
while(! stack.isEmpty()) { binaryString += stack.pop() }return binaryString
}
console.log(dec2Bin(100)); / / 1100100
console.log(dec2Bin(10)); / / 1010
console.log(dec2Bin(1000)); / / 001111101000
Copy the code
Queue Queue
A Queue, which is a limited linear list, FIFO First In First Out
- The limitation is that it only allows deletions at the front of the table
- Inserts are performed at the rear end of the table
Application scenarios of queues
Print queue:
- There are five documents that need to be printed, and these documents are placed in the print queue in order
- The printer will take the documents out of the queue in turn, and the documents that are put in first will be taken out first and printed.
- And so on, until there are no more documents in the queue.
Thread queue:
- In development, it is common to start multiple threads so that tasks can be processed in parallel.
- However, we can’t have too many threads running at the same time.
- At this point, thread queues are used if there is a situation where a thread needs to be opened to handle a task.
- Thread queues start threads in order and process tasks.
Implementation of common operations on queues
Common operations on queues:
- Enqueue (Element): Adds one (or more) new items to the end of the queue.
- Dequeue (): removes the first item in the queue and returns the removed element.
- Front (): Returns the first element in the queue — the first element added and will be the first element removed. No changes are made to the queue (only element information is returned without removal – similar to Stack class peek)
- IsEmpty (): Returns true if the queue contains no task elements, and vice versa
- Size (): Returns the number of elements contained in the queue.
- ToString (): Converts the contents of a queue to a string.
Code implementation of common operations on queues:
class Queue {
items = []
// 1. Add elements to the queue
enqueue(element) {
this.items.push(element)
}
// 2. Remove the front element from the queue
dequeue() {
return this.items.shift()
}
// 3. Look at the front-end elements
front() {
if (this.items.length === 0) return null
return this.items[0]}// 4. Check whether the queue is empty
isEmpty() {
return this.items.length === 0
}
// 5. Check the number of elements in the queue
size() {
return this.items.length
}
}
const q = new Queue()
q.enqueue('a')
q.enqueue('b')
q.enqueue('c')
q.enqueue('d')
console.log(q);
q.dequeue()
q.dequeue()
console.log(q);
console.log(q.front());
console.log(q.isEmpty());
console.log(q.size());
Copy the code
musical
// Beat the drum and pass the flowers
function passGame(nameList,num) {
1. Create a queue structure
const queue = new Queue()
// 2. Put everyone in the queue in turn
for (let i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i])
}
while (queue.size() > 1) {
// 3. Start counting
for (let i = 0; i < num - 1; i++) {
// the person before the num number is put back to the end of the queue
queue.enqueue(queue.dequeue())
}
// num corresponds to this person and is removed from the queue directly
queue.dequeue()
}
// / 4. Get the remaining person
console.log("Last remaining number:"+queue.size());
const endName = queue.front()
console.log('The people who were left at the end were:' + endName);
return nameList.indexOf(endName) // Returns the last remaining subscript value
}
names = ["Zhu Yuanzhang"."Zhu di"."Zhu Gaochi"."Zhu Zhanji".Zhuqi Town]
console.log(passGame(names, 3));
Copy the code
Priority queue
We know that a normal queue only allows elements to be added at the bottom and taken from the top.
But priority queues, when inserting an element, consider the priority of the data. Rather than in the order pushed into the queue.
Priority queues are mainly concerned with:
- Each element is no longer a piece of data, but contains the priority of the data
- In the add mode, the correct position is placed according to the priority.
Priority queue application:
- Check-in at the airport takes into account the priority of first class and business class, as well as economy
- The hospital’s waiting room gives priority to the most seriously ill patients.
class QueueElement {
constructor(element,priority) {
this.element = element
this.priority = priority
}
}
class PriorityQueue extends Queue {
enqueue(element, priority) {
// 1. Create QueueElement
const queueElement = new QueueElement(element, priority)
// 2. How to insert new elements
if (this.isEmpty()) {
this.items.push(queueElement)
} else {
let added = false
for (let i = 0; i < this.items.length; i++) {
if (this.items[i].priority > queueElement.priority) {
this.items.splice(i, 0, queueElement)
added = true
break; }}if(! added) {this.items.push(queueElement)
}
}
}
}
const queue = new PriorityQueue()
queue.enqueue('a'.10)
queue.enqueue('b'.20)
queue.enqueue('c'.5)
queue.enqueue('d'.8)
queue.items.forEach(item= > {
console.log(item.element,item.priority);
})
Copy the code