栈与队列

时游大约 10 分钟

栈与队列

栈如同叠猫猫，而队列则如同猫猫排队。两者分别代表了先入后出和先入先出的逻辑关系。

栈

栈是一种遵循先入后出逻辑的线性数据结构。好比一摞盘子，想取出中间的盘子，必须先把前面的盘子依次拿出。

栈顶部称为“栈顶”，底部称为“栈底”，将元素添加到栈顶的操作叫“入栈”，删除栈顶元素叫“出栈”

栈的常用操作

push：入栈
pop：出战
peek：查看栈顶元素

栈的实现

栈遵循先入后出原则，因此只能在栈顶添加或删除元素。对于数组和链表而言，都可以在任意位置添加或删除元素，因此栈可以被视为一种受限制的数组或链表。

基于链表实现

基于链表实现栈时，将链表的头节点视为栈顶，尾节点视为栈底。对于入栈操作，只需要将元素插入链表头部，被称为“头插法”。对于出栈操作，只需要将头节点从链表中删除即可。

基于链表实现栈的入栈出栈操作1 基于链表实现栈的入栈出栈操作2 基于链表实现栈的入栈出栈操作3

/* 基于链表实现的栈 */
class LinkedListStack {
	#stackPeek; // 将头节点作为栈顶
	#stkSize = 0; // 栈的长度

	constructor() {
		this.#stackPeek = null;
	}

	/* 获取栈的长度 */
	get size() {
		return this.#stkSize;
	}

	/* 判断栈是否为空 */
	isEmpty() {
		return this.size === 0;
	}

	/* 入栈 */
	push(num) {
		const node = new ListNode(num);
		node.next = this.#stackPeek;
		this.#stackPeek = node;
		this.#stkSize++;
	}

	/* 出栈 */
	pop() {
		const num = this.peek();
		this.#stackPeek = this.#stackPeek.next;
		this.#stkSize--;
		return num;
	}

	/* 访问栈顶元素 */
	peek() {
		if (!this.#stackPeek) throw new Error("栈为空");
		return this.#stackPeek.val;
	}

	/* 将链表转化为 Array 并返回 */
	toArray() {
		let node = this.#stackPeek;
		const res = new Array(this.size);
		for (let i = res.length - 1; i >= 0; i--) {
			res[i] = node.val;
			node = node.next;
		}
		return res;
	}
}

基于数组实现

使用数组实现栈时，可以将数组的尾部作为栈顶，入栈和出栈操作分别对应数组尾部添加和删除元素，时间复杂度为 O(1)。

基于数组实现栈的入栈出栈操作1 基于数组实现栈的入栈出栈操作2 基于数组实现栈的入栈出栈操作3

/* 基于数组实现的栈 */
class ArrayStack {
	stack;
	constructor() {
		this.stack = [];
	}

	/* 获取栈的长度 */
	get size() {
		return this.stack.length;
	}

	/* 判断栈是否为空 */
	isEmpty() {
		return this.stack.length === 0;
	}

	/* 入栈 */
	push(num) {
		return this.stack.push(num);
	}

	/* 出栈 */
	pop() {
		if (this.isEmpty()) throw new Error("栈为空");
		return this.stack.pop();
	}

	/* 访问栈顶元素 */
	top() {
		if (this.isEmpty()) throw new Error("栈为空");
		return this.stack[this.stack.length - 1];
	}

	/* 返回 Array */
	toArray() {
		return this.stack;
	}
}

两种实现方式对比

支持操作：两种实现都支持栈定义中的各种操作，数组额外的实现了随机访问，但是一般不会使用到。
时间效率：
1. 在基于数组的实现中，入栈和出栈操作都在预先分配好的连续内存空间中进行，具有很好的缓存本地性，效率很高。但是假如入栈的元素超出数组容量，则会触发扩容机制，导致该次入栈的时间复杂度变为 O(n)。
2. 在基于链表的实现中，链表的扩容非常灵活，不存在触发扩容机制问题。但是入栈的操作会初始化节点对象以及修改引用指针，因此效率较低。
空间效率：
1. 基于数组实现时，存在空间扩容问题，扩容后的容量可能超出实际需求造成浪费。
2. 基于链表实现时，由于链表的节点需要存储引用以及值，所占用的空间相对较大

栈的典型应用

在浏览器中的后退和前进、软件中的撤销和反撤销。
程序中的内存管理：每次调用一个函数时，系统都会在栈顶添加一个栈帧，记录函数的上下文。

队列

队列是一种遵循先进先出原则的线性数据结构，新的元素不断加入队列尾部，而位于队列头部的逐个离开。将队列头部称为“队首”，尾部称为“队尾”，加入队尾的操作称为“入队”，删除队首元素的操作被称为“出队”。

队列的常用操作

push：入栈
pop：出战
peek：查看栈顶元素

队列实现

1.基于链表实现

将链表的头节点和尾节点，分别视为“队首”和“队尾”。规定队尾仅可添加节点，队首仅可删除节点。

基于链表实现队列的入队出队操作1 基于链表实现队列的入队出队操作2 基于链表实现队列的入队出队操作3

/* 基于链表实现的队列 */
class LinkedListQueue {
	#front; // 头节点 #front
	#rear; // 尾节点 #rear
	#queSize = 0;

	constructor() {
		this.#front = null;
		this.#rear = null;
	}

	/* 获取队列的长度 */
	get size() {
		return this.#queSize;
	}

	/* 判断队列是否为空 */
	isEmpty() {
		return this.size === 0;
	}

	/* 入队 */
	push(num) {
		// 在尾节点后添加 num
		const node = new ListNode(num);
		// 如果队列为空，则令头、尾节点都指向该节点
		if (!this.#front) {
			this.#front = node;
			this.#rear = node;
			// 如果队列不为空，则将该节点添加到尾节点后
		} else {
			this.#rear.next = node;
			this.#rear = node;
		}
		this.#queSize++;
	}

	/* 出队 */
	pop() {
		const num = this.peek();
		// 删除头节点
		this.#front = this.#front.next;
		this.#queSize--;
		return num;
	}

	/* 访问队首元素 */
	peek() {
		if (this.size === 0) throw new Error("队列为空");
		return this.#front.val;
	}

	/* 将链表转化为 Array 并返回 */
	toArray() {
		let node = this.#front;
		const res = new Array(this.size);
		for (let i = 0; i < res.length; i++) {
			res[i] = node.val;
			node = node.next;
		}
		return res;
	}
}

2.基于数组实现

在数组中删除首元素的时间复杂度为 O(n)，这会导致出队操作效率较低。然而，我们可以采用以下巧妙方法来避免这个问题。

我们可以使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义 rear = front + size ，这个公式计算出的 rear 指向队尾元素之后的下一个位置。

基于此设计，数组中包含元素的有效区间为 [front, rear - 1]，各种操作的实现方法如图所示。入队操作：将输入元素赋值给 rear 索引处，并将 size 增加 1 。出队操作：只需将 front 增加 1 ，并将 size 减少 1 。可以看到，入队和出队操作都只需进行一次操作，时间复杂度均为 O(1)。

基于数组实现队列的入队出队操作1 基于数组实现队列的入队出队操作2 基于数组实现队列的入队出队操作3

/* 基于环形数组实现的队列 */
class ArrayQueue {
	#nums; // 用于存储队列元素的数组
	#front = 0; // 队首指针，指向队首元素
	#queSize = 0; // 队列长度

	constructor(capacity) {
		this.#nums = new Array(capacity);
	}

	/* 获取队列的容量 */
	get capacity() {
		return this.#nums.length;
	}

	/* 获取队列的长度 */
	get size() {
		return this.#queSize;
	}

	/* 判断队列是否为空 */
	isEmpty() {
		return this.#queSize === 0;
	}

	/* 入队 */
	push(num) {
		if (this.size === this.capacity) {
			console.log("队列已满");
			return;
		}
		// 计算队尾指针，指向队尾索引 + 1
		// 通过取余操作实现 rear 越过数组尾部后回到头部
		const rear = (this.#front + this.size) % this.capacity;
		// 将 num 添加至队尾
		this.#nums[rear] = num;
		this.#queSize++;
	}

	/* 出队 */
	pop() {
		const num = this.peek();
		// 队首指针向后移动一位，若越过尾部，则返回到数组头部
		this.#front = (this.#front + 1) % this.capacity;
		this.#queSize--;
		return num;
	}

	/* 访问队首元素 */
	peek() {
		if (this.isEmpty()) throw new Error("队列为空");
		return this.#nums[this.#front];
	}

	/* 返回 Array */
	toArray() {
		// 仅转换有效长度范围内的列表元素
		const arr = new Array(this.size);
		for (let i = 0, j = this.#front; i < this.size; i++, j++) {
			arr[i] = this.#nums[j % this.capacity];
		}
		return arr;
	}
}

双向队列

双向队列提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。

1. 基于双向链表的实现

/* 双向链表节点 */
class ListNode {
    prev; // 前驱节点引用 (指针)
    next; // 后继节点引用 (指针)
    val; // 节点值

    constructor(val) {
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

/* 基于双向链表实现的双向队列 */
class LinkedListDeque {
    #front; // 头节点 front
    #rear; // 尾节点 rear
    #queSize; // 双向队列的长度

    constructor() {
        this.#front = null;
        this.#rear = null;
        this.#queSize = 0;
    }

    /* 队尾入队操作 */
    pushLast(val) {
        const node = new ListNode(val);
        // 若链表为空，则令 front 和 rear 都指向 node
        if (this.#queSize === 0) {
            this.#front = node;
            this.#rear = node;
        } else {
            // 将 node 添加至链表尾部
            this.#rear.next = node;
            node.prev = this.#rear;
            this.#rear = node; // 更新尾节点
        }
        this.#queSize++;
    }

    /* 队首入队操作 */
    pushFirst(val) {
        const node = new ListNode(val);
        // 若链表为空，则令 front 和 rear 都指向 node
        if (this.#queSize === 0) {
            this.#front = node;
            this.#rear = node;
        } else {
            // 将 node 添加至链表头部
            this.#front.prev = node;
            node.next = this.#front;
            this.#front = node; // 更新头节点
        }
        this.#queSize++;
    }

    /* 队尾出队操作 */
    popLast() {
        if (this.#queSize === 0) {
            return null;
        }
        const value = this.#rear.val; // 存储尾节点值
        // 删除尾节点
        let temp = this.#rear.prev;
        if (temp !== null) {
            temp.next = null;
            this.#rear.prev = null;
        }
        this.#rear = temp; // 更新尾节点
        this.#queSize--;
        return value;
    }

    /* 队首出队操作 */
    popFirst() {
        if (this.#queSize === 0) {
            return null;
        }
        const value = this.#front.val; // 存储尾节点值
        // 删除头节点
        let temp = this.#front.next;
        if (temp !== null) {
            temp.prev = null;
            this.#front.next = null;
        }
        this.#front = temp; // 更新头节点
        this.#queSize--;
        return value;
    }

    /* 访问队尾元素 */
    peekLast() {
        return this.#queSize === 0 ? null : this.#rear.val;
    }

    /* 访问队首元素 */
    peekFirst() {
        return this.#queSize === 0 ? null : this.#front.val;
    }

    /* 获取双向队列的长度 */
    size() {
        return this.#queSize;
    }

    /* 判断双向队列是否为空 */
    isEmpty() {
        return this.#queSize === 0;
    }

    /* 打印双向队列 */
    print() {
        const arr = [];
        let temp = this.#front;
        while (temp !== null) {
            arr.push(temp.val);
            temp = temp.next;
        }
        console.log('[' + arr.join(', ') + ']');
    }
}

2. 基于数组的实现

/* 基于环形数组实现的双向队列 */
class ArrayDeque {
    #nums; // 用于存储双向队列元素的数组
    #front; // 队首指针，指向队首元素
    #queSize; // 双向队列长度

    /* 构造方法 */
    constructor(capacity) {
        this.#nums = new Array(capacity);
        this.#front = 0;
        this.#queSize = 0;
    }

    /* 获取双向队列的容量 */
    capacity() {
        return this.#nums.length;
    }

    /* 获取双向队列的长度 */
    size() {
        return this.#queSize;
    }

    /* 判断双向队列是否为空 */
    isEmpty() {
        return this.#queSize === 0;
    }

    /* 计算环形数组索引 */
    index(i) {
        // 通过取余操作实现数组首尾相连
        // 当 i 越过数组尾部后，回到头部
        // 当 i 越过数组头部后，回到尾部
        return (i + this.capacity()) % this.capacity();
    }

    /* 队首入队 */
    pushFirst(num) {
        if (this.#queSize === this.capacity()) {
            console.log('双向队列已满');
            return;
        }
        // 队首指针向左移动一位
        // 通过取余操作实现 front 越过数组头部后回到尾部
        this.#front = this.index(this.#front - 1);
        // 将 num 添加至队首
        this.#nums[this.#front] = num;
        this.#queSize++;
    }

    /* 队尾入队 */
    pushLast(num) {
        if (this.#queSize === this.capacity()) {
            console.log('双向队列已满');
            return;
        }
        // 计算队尾指针，指向队尾索引 + 1
        const rear = this.index(this.#front + this.#queSize);
        // 将 num 添加至队尾
        this.#nums[rear] = num;
        this.#queSize++;
    }

    /* 队首出队 */
    popFirst() {
        const num = this.peekFirst();
        // 队首指针向后移动一位
        this.#front = this.index(this.#front + 1);
        this.#queSize--;
        return num;
    }

    /* 队尾出队 */
    popLast() {
        const num = this.peekLast();
        this.#queSize--;
        return num;
    }

    /* 访问队首元素 */
    peekFirst() {
        if (this.isEmpty()) throw new Error('The Deque Is Empty.');
        return this.#nums[this.#front];
    }

    /* 访问队尾元素 */
    peekLast() {
        if (this.isEmpty()) throw new Error('The Deque Is Empty.');
        // 计算尾元素索引
        const last = this.index(this.#front + this.#queSize - 1);
        return this.#nums[last];
    }

    /* 返回数组用于打印 */
    toArray() {
        // 仅转换有效长度范围内的列表元素
        const res = [];
        for (let i = 0, j = this.#front; i < this.#queSize; i++, j++) {
            res[i] = this.#nums[this.index(j)];
        }
        return res;
    }
}

栈与队列

# 栈与队列

# 栈

# 栈的常用操作

# 栈的实现

# 基于链表实现

# 基于数组实现

# 两种实现方式对比

# 栈的典型应用

# 队列

# 队列的常用操作

# 队列实现

# 1.基于链表实现

# 2.基于数组实现

# 双向队列

# 1. 基于双向链表的实现

# 2. 基于数组的实现

栈与队列

栈

栈的常用操作

栈的实现

基于链表实现

基于数组实现

两种实现方式对比

栈的典型应用

队列

队列的常用操作

队列实现

1.基于链表实现

2.基于数组实现

双向队列

1. 基于双向链表的实现

2. 基于数组的实现