FE-Interview
FE-Interview copied to clipboard
Published
20 hours ago •
lgwebdream
lgwebdream
单向链表实现队列
// ES5
function Node(data){
this.data = data;
this.next = null;
}
function Queue(){
// 队列的头节点指向null
this.head = null;
}
// 入队,创建一个新的节点, 然后将它添加到链表的尾部,如果链表为空,则头指针指向该节点
Queue.prototype.add = function(node) {
let head = this.head;
const newNode = new Node(node);
if(head) {
// 循环找出尾节点
while(head.next !== null) {
head = head.next;
}
// 将链表的为尾节点指向node
head.next = newNode;
}else {
this.head = newNode;
}
}
// 队首节点出队,头指针指向第一个节点, 头指针的next指针指向该节点的下一个指针,最后返回该节点的值
Queue.prototype.remove = function(){
if(this.head) {
const current = this.head;
const data = current.data;
this.head = current.next;
return data;
}
}
// 判空
Queue.prototype.isEmpty = function(){
// 看头节点是否为nulll
return this.head === null;
}
// 获取队头节点
Queue.prototype.getHead = function(){
return this.head;
}
// 打印队列
Queue.prototype.printQueue = function(){
let node = this.head;
while(node) {
console.log(`node.data`, node.data);
node = node.next;
}
}
const queue = new Queue();
queue.add(1);
queue.add(2);
queue.add(3);
queue.printQueue();
console.log('--------split1--------');
queue.remove();
queue.add(4);
queue.printQueue();
console.log('--------split1--------');
console.log(queue.getHead());
console.log(queue.isEmpty())
// ES6 class
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class Queue {
constructor() {
// 队列的头节点指向null
this.head = null;
}
// 入队,创建一个新的节点, 然后将它添加到链表的尾部,如果链表为空,则头指针指向该节点
add(node) {
let head = this.head;
const newNode = new Node(node);
if (head) {
// 循环找出尾节点
while (head.next !== null) {
head = head.next;
}
// 将链表的为尾节点指向node
head.next = newNode;
} else {
this.head = newNode;
}
}
// 队首节点出队,头指针指向第一个节点, 头指针的next指针指向该节点的下一个指针,最后返回该节点的值
remove() {
if (this.head) {
const current = this.head;
const data = current.data;
this.head = current.next;
return data;
}
}
// 链表判空
isEmpty() {
// 看头节点是否为nulll
return this.head === null;
}
// 获取队头节点
getHead() {
return this.head;
}
// 打印队列
printQueue() {
let node = this.head;
while (node !== null) {
// 打印队列
console.log(`node.data`, node.data);
node = node.next;
}
}
}
const queue = new Queue();
queue.add(1);
queue.add(2);
queue.add(3);
queue.printQueue();
console.log('--------split1--------');
queue.remove();
queue.add(4);
queue.printQueue();
console.log('--------split1--------');
console.log(queue.getHead());
console.log(queue.isEmpty());
// node.data 1
// node.data 2
// node.data 3
// --------split1--------
// node.data 2
// node.data 3
// node.data 4
// --------split1--------
// Node {
// data: 2,
// next: Node { data: 3, next: Node { data: 4, next: null } } }
// false
function Node(value){
this.value = value
this.next = null
}
function Queue(){
this.dummyHead = new Node(-1)
}
Queue.prototype.add = function(node) {
var curr = this.dummyHead
while (curr.next){
curr = curr.next
}
curr.next = new Node(node)
return curr.next
}
Queue.prototype.remove = function(){
var node
if(this.dummyHead.next){
node = this.dummyHead.next
this.dummyHead.next = this.dummyHead.next.next
}
return node
}
Queue.prototype.isEmpty = function(){
return !!this.dummyHead.next
}
Queue.prototype.getHead = function(){
return this.dummyHead.next
}
Queue.prototype.printQueue = function(){
var curr = this.dummyHead.next
while (curr){
console.log(curr.value)
curr = curr.next
}
}
function Node(value){
this.value = value
this.next = null
}
function Queue(){
this.dummyHead = new Node(-1)
}
Queue.prototype.add = function(node) {
var curr = this.dummyHead
while (curr.next){
curr = curr.next
}
curr.next = new Node(node)
return curr.next
}
Queue.prototype.remove = function(){
var node
if(this.dummyHead.next){
node = this.dummyHead.next
this.dummyHead.next = this.dummyHead.next.next
}
return node
}
Queue.prototype.isEmpty = function(){
return !!this.dummyHead.next
}
Queue.prototype.getHead = function(){
return this.dummyHead.next
}
Queue.prototype.printQueue = function(){
var curr = this.dummyHead.next
while (curr){
console.log(curr.value)
curr = curr.next
}
}
class ListNode<T> {
val: T;
next: ListNode<T> | null = null;
constructor(val: T) {
this.val = val;
}
}
class Queue<T> {
private head: ListNode<T> | null;
private tail: ListNode<T> | null;
length: number = 0;
constructor() {
this.head = null;
this.tail = null;
}
append(val: T) {
if (this.tail) {
this.tail.next = new ListNode(val);
this.tail = this.tail.next;
} else {
const node = new ListNode(val);
this.head = node;
this.tail = node;
}
this.length += 1; // 更新长度
}
remove(index: number = 0) {
let fast = this.head; // 记录当前节点
let slow = this.head; // 记录上一个节点
let counter = 0;
while (fast && counter <= index) {
// 找到删除元素
if (counter === index) {
// 如果删除目标为队头
if (index === 0) {
// 如果队列里不只有队头一个元素
if(fast.next) {
this.head = fast.next;
} else {
this.head = null;
this.tail = null;
}
// 删除队尾元素
} else if (!fast.next) {
slow!.next = null;
this.tail = slow;
} else {
// 删除非队首或者非队尾
slow!.next = fast.next;
}
this.length -= 1; // 更新长度
return fast.val;
}
slow = fast;
fast = fast.next;
counter++;
}
return undefined;
}
// 增加迭代器
[Symbol.iterator]() {
let ptr = this.head;
return {
next(){
if(ptr) {
const value = ptr.val;
ptr = ptr.next;
return { done: false, value }
}
return { done: true, value: undefined }
}
}
}
}
const queue = new Queue<number>();
queue.append(1);
queue.append(2);
queue.append(3);
queue.append(4);
queue.append(5);
for(const value of queue) {
console.log(value);
}
// 删除队头
queue.remove();
for(const value of queue) {
console.log(value);
}
// 删除指定位置
queue.remove(2);
for(const value of queue) {
console.log(value);
}
console.log('length：', queue.length);
function LinkNode(val) {
this.val = val
this.next = null
}
function LinkList(val) {
this.head = null
}
class Queue {
constructor() {
this.queue = new LinkList()
this.last = null
}
// 尾部追加
push(val) {
if (!this.queue.head) {
this.queue.head = new LinkNode(val)
this.last = this.queue.head
} else {
this.last.next = new LinkNode(val)
this.last = this.last.next
}
}
// 获取队列头部元素并将其从队列中移除
shift() {
if (!this.queue.head) return null
const headNext = this.queue.head.next
const shiftNode = this.queue.head
shiftNode.next = null
this.queue.head = headNext
if (!this.queue.head) {
this.last = null
}
return shiftNode
}
}
const queue = new Queue()
queue.push(1)
queue.push(2)
queue.push(3)
queue.push(4)
queue.push(5)
queue.shift()
console.log(queue);
