队列(Queue)
李艳生
湖北师范大学
物理与电子科学学院
2020年春季
目录
队列
双端队列
回文问题
队列
图1 排队
队列概念
- 一组遵守先进先出(FIFO)的有序集合
- 一个队列包含队头，队尾
- 添加在队尾，删除在队头
- 新元素在队尾，旧元素在队头
- 生活实例:排队
- 计算机实例:文档打印队列
队列操作
- 建队列
- 入队
- 出队
- 查看队头
- 检查队空
- 清空队列
算法演示
队列实现
- 基于数组的队列
- 基于对象的队列
数组队列
- 创建一个类封装队列
- 利用数组操作实现队列操作
class Queue{
constructor(){
this.items = [];
}
enqueue(element){}
dequeque(){}
peek(){}
isEmpty(){}
clear(){}
}
入队
- 入队只能在队列添加元素
- 利用数组push操作实现入队
enqueue(element){
this.items.push(element);
}
出队
- 出队只能在队头删除元素
- 利用数组shift操作实现出队
dequeue(){
return this.items.shift();
}
查看队头元素
- 查看队头只获取队头元素,不删除
- 利用数组第一个元素
peek(){
return this.items[0];
}
检查队空
- 队空返回true,不空返回false
- 利用数组length属性
isEmpty(){
return this.items.length === 0;
}
清空队列
- 将队列中所有元素清空
clear(){
this.items = [];
}
队列使用
- 利用new创建队列对象
//建队列
let queue = new Queue();
//判队空
console.log(queue.isEmpty());
//入队
queue.enqueue(1);
queue.enqueue(2);
//查看队头
console.log(queue.peek());
//出队
console.log(queue.dequeue());
//清空队列
queue.clear();
console.log(queue.isEmpty());
对象队列
- 创建一个类封装队列
- 利用对象操作实现队列操作
class Queue{
constructor(){
this.tailCount = 0;
this.headCount = 0;
this.items = {};
}
enqueue(element){}
dequeue(){}
peek(){}
isEmpty(){}
clear(){}
}
入队
- 入队只能在队尾添加元素
- 利用对象键值对操作实现入队,this.tailCount作为键，插入元素作为值
- 递增tailCount变量
enqueue(element){
this.items[this.tailCount] = element;
this.tailCount++;
}
检查队空
- 队空返回true,不空返回false
- 利用变量headCount,tailCount
isEmpty(){
return this.tailCount - this.headCount === 0;
}
出队
- 出队只能在队头删除元素
- 利用变量headCount操作实现出栈
dequeue(){
const ret = this.items[this.headCount];
delete this.items[this.headCount];
this.headCount++;
return ret;
}
查看队头元素
- 查看队头只获取队头元素,不删除
- 利用变量headCount
peek(){
return this.items[this.headCount];
}
清空队列
- 将队列中所有元素清空
clear(){
this.tailCount = 0;
this.headCount = 0;
this.items = {};
}
队列使用
- 利用new创建队列对象
//建队列
let queue = new Queue();
//判队空
console.log(queue.isEmpty());
//入队
queue.enqueue(1);
queue.enqueue(2);
//查看队头
console.log(queue.peek());
//出队
console.log(queue.dequeue());
//清空队列
queue.clear();
console.log(queue.isEmpty());
双端队列概念
- 遵守先进先出(FIFO)和后进先出(LIFO)的有序集合
- 将队列和栈相结合
- 一个双端队列包含队头，队尾
- 可在队尾，队头添加删除元素
- 生活实例:排队
- 计算机实例:撤销操作队列
双端队列操作
- 建队列
- 队尾添加
- 队头添加
- 队尾删除
- 队头删除
- 查看队尾
- 查看队头
- 检查队空
- 清空队列
双端队列实现
- 基于数组的双端队列
- 基于对象的双端队列
数组双端队列
- 创建一个类封装双端队列
- 利用数组操作实现双端队列操作
class Deque{
constructor(){
this.items = [];
}
addHead(element){}
addTail(element){}
removeHead(){}
removeTail(){}
peekHead(){}
peekTail(){}
isEmpty(){}
clear(){}
}
对象双端队列
- 创建一个类封装双端队列
- 利用对象操作实现双端队列操作
class Deque{
constructor(){
this.tailCount = 0;
this.headCount = 0;
this.items = {};
}
addHead(element){}
addTail(element){}
removeHead(){}
removeTail(){}
peekHead(){}
peekTail(){}
isEmpty(){}
clear(){}
}
检查队空
- 队空返回true,不空返回false
- 利用变量headCount,tailCount
isEmpty(){
return this.tailCount - this.headCount === 0;
}
队尾添加元素
- 利用变量tailCount
addTail(element){
this.items[this.tailCount] = element;
this.tailCount++;
}
队尾删除元素
- 利用变量tailCount
removeTail(){
this.tailCount--;
let ret = this.items[this.tailCount];
delete this.items[this.tailCount];
return ret;
}
队头添加元素
- 利用变量headCount
- 分三种情况:空队列,headCount>0,headCount=0
队头添加元素
addHead(element){
if(this.isEmpty()){
this.addTail(element);
}
else if(this.headCount > 0){
this.headCount--;
this.items[this.headCount] = element;
}
else {
for(let i = this.tailCount; i > 0; i--){
this.items[i] = this.items[i - 1];
}
this.tailCount++;
this.headCount = 0;
this.items[this.headCount] = element;
}
}
队头删除元素
- 利用变量headCount操作实现出队
removeHead(){
const ret = this.items[this.headCount];
delete this.items[this.headCount];
this.headCount++;
return ret;
}
查看队尾元素
- 查看队尾只获取队尾元素,不删除
- 利用变量tailCount
peekTail(){
return this.items[this.tailCounti - 1];
}
查看队头元素
- 查看队头只获取队头元素,不删除
- 利用变量headCount
peekHead(){
return this.items[this.headCount];
}
清空队列
- 将队列中所有元素清空
clear(){
this.tailCount = 0;
this.headCount = 0;
this.items = {};
}
双端队列使用
- 利用new创建双端队列对象
//建队列
let queue = new Deque();
//判队空
console.log(queue.isEmpty());
//入队
queue.addTail(1);
queue.addTail(2);
queue.addTail(3);
queue.addHead(4);
//查队
console.log(queue.peekHead());
console.log(queue.peekTail());
//出队
console.log(queue.removeHead());
console.log(queue.removeTail());
//清空队列
queue.clear();
console.log(queue.isEmpty());
回文问题
- 正反都能读通的单词、词组、数或一系列字符的序列
- 单个字符即是回文
- 例如:madam,racecar,a,b
循环检测回文
- 分别从头尾两个方向i,j遍历
- 若i<=j每个字符都相同，则为回文
function isPalindrome(str) {
for(let i = 0, j = str.length - 1; i <= j;i++,j--){
if(str.charAt(i) !== str.charAt(j)) return false;
}
return true;
}
alert(isPalindrome('madam'));
alert(isPalindrome1('a'));
alert(isPalindrome1('aa'));
alert(isPalindrome1('客上天然居；居然天上客'))
alert(isPalindrome1('ab'))
数组检测回文
- 先字符串1转成数组
- 利用数组reverse()方法反转
- 再将数组转成字符串2
- 若字符串1和2一样，则为回文
数组检测回文
function isPalindrome(str) {
let a = str.split('');
let b = a.reverse().join('');
if(str === b){
return true;
}
return false;
}
alert(isPalindrome('madam'));
栈检测回文
- 先将每个字符进栈
- 再依次出栈形成新字符串
- 比较两个字符串，若相同则为回文
栈检测回文
function isPalindrome(str) {
let stack = new Stack();
let temp = '';
for(let i = 0; i < str.length; i++){
stack.push(str.charAt(i));
}
while(!stack.isEmpty()){
temp += `${stack.pop()}`;
}
if(str === temp) return true;
return false;
}
alert(isPalindrome('madam'));
队列检测回文
- 先将每个字符入队
- 再分别从队列两端出队
- 比较出队字符，若相同则继续，直到队列长度大于1
队列检测回文
function isPalindrome(str) {
let deque = new Deque();
let s,e;
for(let i = 0; i < str.length; i++){
deque.addTail(str.charAt(i));
}
while(deque.size() > 1){
s = deque.removeHead();
e = deque.removeTail();
if(s !== e) return false;
}
return true;
}
alert(isPalindrome('madam'));