Written earlier, this article is some questions about stack and queue asked by the interviewer during my interview. The answer to the question is summarized by myself. There may be some deviations. Please correct it
If there are more problems in the follow-up, we will continue to add
1. What linear tables do you know? What about nonlinear tables
Linear table: general linear table, stack and queue, string, array and generalized table
Nonlinear tables: trees, graphs, sets
2. Briefly talk about the understanding of stack and queue
The stack is last in first out (LIFO) and the queue is First In First Out (FIFO)
There are only two operations on the stack, push (into the stack, insert data) and pop (out of the stack, delete data). The stack realized by array is called sequential stack, and the stack realized by linked list is called chain stack
Queue: push (queue in, insert data) and pop (queue out, delete data). The stack realized by array is called sequential queue, and the stack realized by linked list is called chain queue
3. According to the code you write, talk about the time complexity of entering the stack, leaving the stack, leaving the team and joining the team
as follows
4. Implement a stack with array (sequential stack)
The time complexity of entering the stack is O(1), and the time complexity of exiting the stack is O(1)
class Stack {
constructor() {
this.stack = []
}
push(item) {
this.stack.push(item)
}
pop() {
this.stack.pop()
}
getTop() {
return this.stack[this.getCount() - 1]
}
getCount() {
return this.stack.length
}
isEmpty() {
return this.getCount() === 0
}
}
5. Implement a stack with a linked list (chain stack)
The time complexity of entering the stack is O(1), and the time complexity of exiting the stack is O(1)
function Node(val) {
this.val = val;
this.next = null;
}
function Stack() {
this.top = null;
this.length = 0;
}
Stack.prototype.push = function (node) {
if (!this.top) {
this.top = node;
this.length++;
} else {
node.next = this.top;
this.top = node;
this.length++;
}
}
Stack.prototype.pop = function () {
let res = this.top || undefined;
if (this.top) {
this.top = this.top.next;
this.length--;
}
return res;
}
6. Implement a queue (sequential queue) with an array
The time complexity of joining the team is O(1), and the time complexity of leaving the team is O(1)
class Queue {
constructor() {
this.queue = []
}
push(item) {
this.queue.push(item)
}
pop() {
this.queue.shift()
}
getHeader() {
return this.queue[0]
}
getLength() {
return this.queue.length
}
isEmpty() {
return this.getLength() === 0
}
}
7. Implement a queue (chain stack) with a linked list
The time complexity of joining the team is O(1), and the time complexity of leaving the team is O(1)
function Node(val) {
this.val = val;
this.next = null;
}
function Queue() {
this.front = null;
this.tail = null;
this.length = 0;
}
Queue.prototype.push = function (node) {
if (!this.front) {
this.front = this.tail = node;
} else {
this.tail.next = null;
this.tail = node;
}
this.length++;
}
Queue.prototype.pop = function () {
if (!this.length) return -1;
let res = this.front;
this.front = this.front.next;
this.length--;
if (!this.length)
this.tail = null;
return res;
}
8. Implement a circular queue
The time complexity of joining the team is O(1), and the time complexity of leaving the team is O(1)
class SqQueue {
constructor(length) {
this.queue = new Array(length + 1)
this.first = 0
this.last = 0
this.size = 0
}
enQueue(item) {
// Judge whether the team tail + 1 is the team head
// If yes, it means that the array needs to be expanded
// %this.queue.length is to prevent the array from going out of bounds
if (this.first === (this.last + 1) % this.queue.length) {
this.resize(this.getLength() * 2 + 1)
}
this.queue[this.last] = item
this.size++
this.last = (this.last + 1) % this.queue.length
}
deQueue() {
if (this.isEmpty()) {
throw Error('Queue is empty')
}
let r = this.queue[this.first]
this.queue[this.first] = null
this.first = (this.first + 1) % this.queue.length
this.size--
// Judge whether the current queue size is too small
// To ensure that space is not wasted, when the queue space is equal to one quarter of the total length
// When it is not 2, the total reduced length is half of the current length
if (this.size === this.getLength() / 4 && this.getLength() / 2 !== 0) {
this.resize(this.getLength() / 2)
}
return r
}
getHeader() {
if (this.isEmpty()) {
throw Error('Queue is empty')
}
return this.queue[this.first]
}
getLength() {
return this.queue.length - 1
}
isEmpty() {
return this.first === this.last
}
resize(length) {
let q = new Array(length)
for (let i = 0; i < length; i++) {
q[i] = this.queue[(i + this.first) % this.queue.length]
}
this.queue = q
this.first = 0
this.last = this.size
}
}
9. Two stacks implement one queue
Stack A and stack B, when there are elements to be inserted, insert them into stack A. When you want to remove elements, first put the elements in stack A out of the stack in turn into stack B, and then output data from the top of stack B. In this way, the first in first out principle is realized based on two stacks
The time complexity of joining the team is O(1), and the time complexity of leaving the team is O(n)
class MyQueue {
constructor() {
this.s1 = []
this.s2 = []
this.front = null
}
enPush(item) {
this.s1.push(item)
}
dePop() {
if (this.s2.length === 0) {
while (this.s1.length !== 0) {
this.s2.push(this.s1.pop())
}
}
this.front = this.s2[1]
return this.s2.pop()
}
peek() {
if (this.s2.length === 0) {
return this.s1[0] ? this.s1[0] : null
}
return this.front
}
isEmpty() {
if (this.s1.length === 0 && this.s2.length === 0) {
return 'Queue is empty'
}
return 'Queue is not empty'
}
}
let ans = new MyQueue()
ans.enPush(2)
ans.enPush(3)
console.log(ans.peek()); // 2
console.log(ans.isEmpty()); // Queue is not empty
console.log(ans);
10. Two queues implement one stack
Queue A and queue B directly insert elements into queue A when stacking operation is required. When the stack out operation is required, first dequeue the first n-1 elements in queue A and move them to queue B, so that the last element left in queue A is actually the element we need to stack. Just dequeue this element
The time complexity of entering the stack is O(1), and the time complexity of exiting the stack is O(n)
class MyStack {
constructor() {
this.q1 = []
this.q2 = []
this.front = null
}
enPush(item) {
this.q1.push(item);
this.front = item;
}
dePop() {
while (this.q1.length > 1) {
this.front = this.q1.shift();
this.q2.push(this.front);
}
// Swap p1 and p2
let val = this.q1.pop();
let temp = this.q2;
this.q2 = this.q1;
this.q1 = temp;
return val;
}
getTop() {
return this.front;
}
isEmpty() {
return this.q1.length === 0;
}
}
let ans = new MyStack()
ans.enPush(2)
ans.enPush(5)
ans.dePop()
console.log(ans.getTop()) // 2
console.log(ans.isEmpty()); // false
console.log(ans); // MyStack {q1: Array(1), q2: Array(0), front: 2}
In fact, there is another solution to this problem. Only one queue is needed to simulate the stack. The idea is: when the stack operation needs to be carried out, first insert the new elements into the tail of the queue, and then take other elements in the queue out of the queue in turn. Of course, the characteristics of the queue are out of the queue from the head of the queue, but the elements come out and let them enter the queue from the tail of the queue, This is done in turn, leaving the new element just inserted unchanged. At this time, the new element is actually pushed to the head of the team, and the action of putting the new element into the stack is completed. When the stack operation needs to be performed, the queue header element is directly out of the queue.
11. Implement a priority queue
priority Queue is a special queue. It does not abide by the principle of first in first out. It is out of the queue according to priority. It is divided into maximum priority Queue (refers to the maximum element out of the queue first) and minimum priority Queue (refers to the minimum element out of the queue first).
The time complexity of joining the team is O(1), and the time complexity of leaving the team is O(n)
class priorityQueue {
constructor() {
this.queue = []
this.front = null
this.back = null
}
enQueue(item) {
this.queue.push(item)
}
deQueue() {
let priority = this.queue[0].code
let fromIndex = 0
this.queue.forEach((item, index) => {
if (item.code < priority) {
fromIndex = index
}
})
// Pop up the highest priority element
return this.queue.splice(fromIndex, 1)
}
getTop() {
return this.queue[this.queue.length - 1]
}
getBack() {
return this.queue[0]
}
isEmpty() {
if (this.queue.length === 0) {
return true
}
return false
}
getCount() {
return this.queue.length
}
}
class Patient {
constructor(name, code) {
this.name = name
// Code stands for priority. The smaller the code, the higher the priority
this.code = code
}
}
let q = new priorityQueue()
let p1 = new Patient('Smith', 4)
let p2 = new Patient('Tom', 2)
let p3 = new Patient('Jane', 6)
q.enQueue(p1)
q.enQueue(p2)
q.enQueue(p3)
console.log(q.getTop()) // Jane...
console.log(q.getBack()) // Smith...
console.log(q.isEmpty()) // false
console.log(q.deQueue()) // Tom...
console.log(q.getCount()) // 2
Reference link
Stack implementation queue, queue implementation stack
Sequential stack, sequential queue, circular queue
Linked list implementation stack and queue
Priority queue