Datawhale | 编程第6期 Test 1
2019-04-08 本文已影响0人
youthcity
栈
1. 用数组实现一个顺序栈
栈: 当某个数据集只涉及在一端插入和删除数据, 并且满足后进先出, 就该使用栈这种数据结构
顺序栈
function Stack() {
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.length = length;
this.clear = clear;
function push(element) {
return this.dataStore[this.top++] = element;
}
function pop() {
if (this.top > 0) {
return this.dataStore[--this.top];
} else {
return undefined;
}
}
function peek() {
return this.dataStore[this.top - 1];
}
function length() {
return this.top;
}
function clear() {
delete this.dataStore;
this.dataStore = [];
this.top = 0;
}
}
// Test
const stack = new Stack();
stack.push(1);
console.log(stack.length());
console.log(stack.pop());
2. 用链表实现一个链式栈
class Stack {
constructor() {
this.top = null;
this.size = 0;
}
push(value) {
++this.size;
const Node = new StackNode(value);
if (this.top == null) {
this.top = Node;
} else {
Node.next = this.top;
this.top = Node;
}
}
pop() {
if (this.size <= 0) {
return null;
}
--this.size;
const PopedNode = this.top;
this.top = this.top.next;
return PopedNode.value;
}
empty() {
while (this.top != null) {
const currentNode = this.top;
currentNode = null;
--this.size;
this.top = this.top.next;
}
}
}
class StackNode {
constructor(data) {
this.value = data;
this.next = null;
}
}
// Test
const stack = new Stack();
stack.push(1);
console.log(stack.size);
3. 编程模拟实现一个浏览器的前进、后退功能
class History {
constructor() {
this.length;
this.st = Stack();
this.vice_st = Stack();
}
go(url) {
this.st.push(url);
}
forward(url) {
this.st.push(url);
}
back() {
const poped = this.st.pop();
this.vice_st.push(poped);
}
}
// 链式栈
class Stack {
constructor() {
this.top = null;
this.size = 0;
}
push(value) {
++this.size;
const Node = new StackNode(value);
if (this.top == null) {
this.top = Node;
} else {
Node.next = this.top;
this.top = Node;
}
}
pop() {
if (this.size <= 0) {
return null;
}
--this.size;
const PopedNode = this.top;
this.top = this.top.next;
return PopedNode.value;
}
empty() {
while (this.top != null) {
const currentNode = this.top;
currentNode = null;
--this.size;
this.top = this.top.next;
}
}
}
class StackNode {
constructor(data) {
this.value = data;
this.next = null;
}
}
队列
1.用数组实现一个顺序队列
class Queue {
constructor() {
this.items = [];
}
/**
* 向队尾添加一个（或多个）新的元素
* @param {*} element 新元素
*/
enqueue(element) {
this.items.push(element)
}
/**
* 移除队列的第一（即排在队列最前面的）项，并返回被移除的元素
*/
dequeue() {
// 根据队列的先进先出原则，使用shift方法
// shift方法会从数组中移除存储在索引为0的元素
return this.items.shift()
}
/**
* 返回队列中的第一个元素--最先被添加，也将是最先被移除的元素。
* 队列不做任何变动（不移除元素，只返回元素信息）
*/
front() {
return this.items[0]
}
/**
* 清除队列中的所有元素
*/
clear() {
this.items = []
}
/**
* 如果队列中不包含任何元素，返回true，否则返回false
*/
isEmpty() {
return this.items.length === 0
}
/**
* 返回队列包含的元素个数，与数组length属性类似
*/
size() {
return this.items.length
}
/**
* 队列内容字符串化
*/
toString() {
return this.items.toString()
}
}
2. 用链表实现一个链式队列
//节点
function Node(data){
this.data = data;
}
function Queue() {
var node = new Node(null);
this.front = node;
this.rear = node;
}
//长度
Queue.prototype.length = function(){
var length = 0;
var node = this.front;
while(node!=this.rear){
node = node.next;
length++;
}
return length;
}
Queue.prototype.enterQueue = function(node){
node.next = null;
this.rear.next = node;
this.rear = node;
return 0;
}
Queue.prototype.deleteQueue = function(){
var p = this.front.next;
if(this.rear == this.front){
return 1;
}
this.front.next = p.next;
if(this.rear == p){
this.rear = this.front;
}
delete p;
}
3. 实现一个循环队列
function Queue(maxSize) {
this.data = new Array(maxSize);
this.front = 0;//头指针
this.rear = 0;//尾指针
this.maxSize = maxSize;
}
//长度
Queue.prototype.length = function(){
return (this.rear-this.front+this.maxSize)%this.maxSize;
}
Queue.prototype.enterQueue = function(data){
if((this.rear+1)%this.maxSize==this.front){
//满
return 1;
}
this.data[this.rear] = data;
this.rear = (this.rear+1)%this.maxSize;
return 0;
}
Queue.prototype.deleteQueue = function(){
if(this.front == this.rear){
//空
return 1;
}
this.front = (this.front+1)%this.maxSize;
return 0;
}
链表
1. 实现单链表、循环链表、双向链表，支持增删操作
class Node { // 链表节点
constructor(element) {
this.element = element;
this.next = null; // 节点的指向下个节点的指针
}
}
class NodeList { // 链表
constructor(item) {
this.head = new Node(item); // 初始化链表的头节点
}
/**
* @description 插入元素
* @param {需要插入的元素} newItem
* @param {插入到某一元素之后} beforeItem
*/
insertInNext(newItem, beforeItem) {
let newNode = new Node(newItem);
if (beforeItem) { // 判读是否是插入到指定节点后面，如果不是则插入到最后一个节点。
let currNode = this.find(beforeItem);
newNode.next = currNode.next;
currNode.next = newNode;
} else {
let lastNode = this.findLastNode();
lastNode.next = newNode;
}
}
/**
* @description 删除元素
* @param {删除的元素} newItem
*/
remove(item) {
let preNode = this.findPreNode(item); // 找到前一节点，将前一节点的next指向该节点的next
if (preNode.next != null) {
preNode.next = preNode.next.next;
}
}
/**
* @description 查找元素的节点
* @param {查找的元素} item
*/
find(item) { // 根据元素查找节点
let currNode = this.head;
while (currNode.element !== item && currNode) {
if (currNode.next) {
currNode = currNode.next;
} else {
currNode = null;
}
}
return currNode;
}
/**
* @description 查找最后一个节点
*/
findLastNode() {
let currNode = this.head;
while (currNode.next) {
currNode = currNode.next;
}
return currNode;
}
/**
* @description 查找元素的前一节点
* @param {查找的元素} item
*/
findPreNode(item) {
let currNode = this.head;
while (currNode && currNode.next && currNode.next.element !== item) {
if (currNode.next) {
currNode = currNode.next;
} else {
currNode = null;
}
}
return currNode;
}
toString() {
let currNode = this.head;
let strList = [];
while (currNode.next) {
strList.push(JSON.stringify(currNode.element));
currNode = currNode.next;
}
strList.push(JSON.stringify(currNode.element));
return strList.join('->')
}
}
2. 实现单链表反转
// 判断对象是否为空
function isEmptyObject(obj) {
for (var name in obj) {
return false;
}
return true;
}
function ReverseList(pHead) {
if (isEmptyObject(pHead)) {
return false;
}
var pre = null;
var next = null;
while (pHead != null) {
next = pHead.next;
pHead.next = pre;
pre = pHead;
pHead = next;
}
return pre;
}
3. 实现两个有序的链表合并为一个有序链表
var mergeTwoLists = function(l1, l2) {
if (!l1) return l2;
if (!l2) return l1;
let head;
if (l1.val <= l2.val) {
head = l1;
head.next = mergeTwoLists(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoLists(l1, l2.next);
}
return head
}
4. 实现求链表的中间结点
var middleNode = function(head) {
var tail = mid = head; // 尾部和中间结点指针
var count = 0;
while (tail.next !== null) {
tail = tail.next;
count ++;
if (count === 2) {
mid = mid.next;
count = 0;
}
}
if (count === 1) {
mid = mid.next;
}
return mid;
}
