栈和队列

1. 栈

1. 概念

• 运算受限的线性表
• 栈顶【TOP】，栈底【Bottom】
• 栈stack是限制仅在表的一端进行插入和删除运算的线性表
• LIFO后进先出
• 顺序栈 & 链栈
• 上溢，下溢
• 两个栈，栈底分别在两头，一起向中间入栈

2. 顺序栈(JavaScript)

// 我们从0开始算数组,所以栈顶指针初始化在-1
// 栈顶指针指向的位置是当前位置,当前位置应当有值,即栈顶元素
function Stack() {
	// 确保只读,不向外暴露，对栈进行运算操作只能通过pop和push
	var maxSize = 10; // 栈容量
	var data = []; // 顺序数组
	var top = -1; // 栈顶指针
	this.getTop = function() {
		return top;
	}
	this.getSize = function() {
		return maxSize;
	}
	// 栈置空
	this.empty = function() {
		top = -1;
	}
	// 判栈空
	this.isEmpty = function() {
		return top == -1;
	}
	// 判栈满
	this.isFull = function() {
		return top == this.getSize() - 1; // top指向9的时候已经满了
	}
	// 进栈
	this.push = function(value) {
		if (this.isFull()) {
			console.log('栈满:' + data);
		} else {
			data[++top] = value;
		}
	}
	// 出栈
	this.pop = function() {
		if (this.isEmpty()) {
			console.log('栈空:' + data);
		} else {
			return data[top--];
		}
	}
	// 读栈顶元素
	this.stackTop = function() {
		if (this.isEmpty()) {
			console.log('栈空:' + data);
		} else {
			return data[top];
		}
	}
}

3. 实例：进制转换，除N取余法

function to_n_base(d, n){
	var result = ''; // 返回值
	var s = new Stack(1000); // 栈
	while(d){
		s.push(d%n); // 入栈
		d = Math.floor(d/n); // 更新d
	}
	// 弹出
	while(!s.isEmpty()){
		result += s.pop();
	}
	return result + `(${n})`;
}

2. 队列

1. 概念

• 队列queue允许在一端插入，另一端删除的线性表
• 队首【front】，队尾【rear】
• FIFO先进先出
• 顺序队列 & 链队列

栈与队列对比：队列实际上是队首工作人员在不停地往队尾移动，而不是现实生活中真实队列，队首出队后，所有人都往前窜一位来接近工作人员，当队伍不停地入队出队，最终我们借以实现顺序队列的数组会溢出，称为“假上溢”。队列会在入队出队的过程中“祸活”所经历的内存，而栈则是一直在自己的一亩三分地上不会出界。

2. 顺序队列(JavaScript)

// 队列需要首和尾两个指针,初始均为0
// 队首和队尾指针指向的位置都是可以直接拿来操作的位置
// 队首位置可以直接出队,队尾位置可以直接入队
function Queue(size) {
	var front = 0;
	var rear = 0;
	var maxSize = size;
	var data = [];
	this.getFront = function() {
		return front;
	}
	this.getRear = function() {
		return rear;
	}
	this.getSize = function() {
		return maxSize;
	}
 
	// 判空
	this.isEmpty = function() {
		return front == rear;
	}
	// 判满
	this.isFull = function() {
		return rear == front + maxSize;
	}
	// 置空
	this.empty = function() {
		// 让头等于尾,不要头尾之间的数据了
		front = rear;
	}
	// 入队
	this.enQueue = function(value) {
		if (this.isFull()) {
			console.log("队满");
		} else {
			data[rear++] = value;
		}
	}
	// 出队
	this.deQueue = function() {
		if (this.isEmpty()) {
			console.log("队空");
		} else {
			return data[front++];
		}
	}
	// 查看队首元素
	this.queueFront = function() {
		return data[front];
	}
}

3. 循环队列

• 为了防止“假上溢”，出现了首尾相接的循环队列
• 循环队列实现有两个问题
  1. 头尾指针到达上界QueueSize-1时，其加1操作需要指向下界0，有两种方法解决
     • if判读语句

     if(front+1 == QueueSize-1){
     	front = 0
     } else {
     	front++
     }
     

     • %求余

     front = (front+1)%QueueSize
     

  2. 判空判满条件front == rear不适用
     • 增加flag记录空满
     • 空出一个空位置，rear始终指向空位置
     • 计数器记录队列元素总数

4. 循环队列(TypeScript)

export class CircleQueue {
    // fields
    private data: any[];
    private size: number;
    front: number;
    rear: number;
    count: number;
    // constructor
    constructor(size) {
        this.empty();
        this.size = size;
        this.data = new Array(size);
    };
    // methods
    empty(): void {
        this.front = 0;
        this.rear = 0;
        this.count = 0;
    };
    enQueue(value) {
        if (this.isFull()) {
            console.log('Full')
        } else {
            this.count++;
            this.data[this.rear] = value;
            this.rear = (this.rear + 1) % this.size;
        }
    };
    deQueue() {
        if (this.isEmpty()) {
            console.log('Empty')
        } else {
            this.count--;
            let temp = this.data[this.front];
            this.front = (this.front + 1) % this.size;
            return temp;
        }
    };
    isFull(): boolean {
        return this.count == this.size;
    };
    isEmpty(): boolean {
        return this.count == 0;
    };
    queueFront() {
        return this.data[this.front];
    }
}

5. 实例：舞伴问题(TypeScript)

import { CircleQueue } from "./CircleQueue";

// 舞者类
class Dancer {
    name: string;
    gender: string;
    constructor(name, gender) {
        this.name = name;
        this.gender = gender;
    }
}
// 生成名字
function getName(x: number, y: number): string {
    var firstName = '赵钱孙李周吴郑王冯陈褚卫蒋沈韩杨朱秦尤许何吕施张孔曹严华金魏陶姜'.split("");
    var lastName = '甲乙丙丁戊己庚辛壬癸子丑寅卯辰巳午未申酉戌亥'.split("");
    x = x % firstName.length;
    y = y % lastName.length;
    return firstName[x] + lastName[y];
}
// 随机性别
function getGender(): string {
    var genders = ['男', '女', '男'];
    return genders[Math.floor(Math.random() * 3)];
}
// 随机生成舞者(10~20)
function initDancers(): Dancer[] {
    var num = Math.random() * 10 + 10;
    var result: Dancer[] = [];
    for (let i = 0; i < num; i++) {
        result.push(new Dancer(getName(i, i), getGender()));
    }
    console.log(result);
    return result;
}
// 初始化男女两队
var men = new CircleQueue(20);
var women = new CircleQueue(20);
// 舞会开始,男女分别入队
var dancers: Dancer[] = initDancers();
for (let dancer of dancers) {
    if (dancer.gender === '女') {
        women.enQueue(dancer);
    } else {
        men.enQueue(dancer);
    }
}
// 依次出队，准备嗨皮
console.log('舞队名单：\n');
while (!women.isEmpty() && !men.isEmpty()) {
    console.log('女:' + women.deQueue().name + 'vs 男:' + men.deQueue().name + '\n');
}
// 没有配对成功的单身狗，打印示众
console.log("***丝：\n")
while (!men.isEmpty()) {
    console.log(men.deQueue().name + '\n')
}
console.log("剩女：\n")
while (!women.isEmpty()) {
    console.log(women.deQueue().name + '\n')
}