js：数组实现队列和栈、栈实现队列、队列实现栈

悠悠 2024-04-17 05:55 245阅读 0赞

**目录**

一、利用数组结构实现大小固定的队列和栈

二、仅用队列结构实现栈结构

三、仅用栈结构实现队列结构

四、总结

--------------------

### 一、利用数组结构实现大小固定的队列和栈 ###

**1.数组结构 实现 队列**

①队列的特点：先进先出，后进后出。

② 注意：需要定义 start、end变量，以标记 出队和入队位置；还要定义一个size变量，约束出入队的行为。

<script type="text/javascript">
    	// arrayToQueue
    	var start = 0,end = 0,size = 0;
    	function peek(arr){  // 返回队头元素
    		if (size == 0) {
    			console.log("This Queue is empty!");
    			return;
    		}
    		console.log("队头元素："+ arr[start]);
    	}
    	function push(arr,n){  // 入队操作
    		if (size == arr.length-1 ) {
    			console.log("This Queue is full!")
    			return;
    		}
    		arr[end] = n;
    		console.log(arr[end]+"入队列成功！")
    		size++;
    		end = end == arr.length-1 ? 0 : end+1;
    		
    	}
    	function pop(arr){  // 出队操作
    		if (size == 0) {
    			console.log("This Queue is empty!")
    			return;
    		}
    		console.log(arr[start]+"出队列成功！")
    		size--;
    		start = start == arr.length-1 ? 0 : start+1;
    	}
    	var arr = [];
    	arr.length = 3;  // 设置队列长只有3
    	push(arr,18)  // 18入队列成功！
    	push(arr,3)  // 3入队列成功！
    	pop(arr)  // 18出队列成功！
    	pop(arr)  // 3出队列成功！
    	pop(arr)  // This Queue is null!
    	peek(arr)  // This Queue is null!
    	push(arr,5)  // 5入队列成功！
    	peek(arr)  // 栈顶元素：5
    </script>

**2.数组结构 实现 栈**

① 栈的特点：先进后出，后进先出

② 需要一个 size 变量来记录位置

<script type="text/javascript">
    	// arrayToStack
    	var size =0;
    	function peek(arr){  // 返回栈顶元素
    		if (size == 0) {
    			console.log(" This Stack is empty!")
    			return;
    		}
    		console.log(" 栈顶元素： "+arr[size-1]);
    	}
    	function push(arr,n){  // 入栈操作
    		if (size == arr.length) {
    			console.log(" This Stack is full!")
    			return;
    		}
    		arr[size++] = n;
    		console.log( n + " 成功入栈！");
    	}
    	function pop(arr){  // 出栈操作
    		if (size == 0) {
    			console.log(" This Stack is empty!")
    			return;
    		}
    		console.log( arr[--size] + " 成功出栈！");
    	}
    	var arr = [];
    	arr.length = 3;
    	push(arr,3);  // 3 成功入栈！
    	push(arr,5);  // 5 成功入栈！
    	peek(arr);  //  栈顶元素： 5
    	pop(arr);  // 5 成功出栈！
    	peek(arr);  // 栈顶元素： 3
    </script>

### 二、仅用队列结构实现栈结构 ###

1.思路：

① 先准备两个队列 queue、help；

② queue 用来实现出入栈操作；

③ 出栈时： queue先把前面的值push进help里，然后弹出栈顶的数；

④ 入栈：queue的队尾push一个数；

⑤ 出栈后，交换queue和help两个队列。

<script type="text/javascript">
    	// queueToStack
    	var queue = [],help = [],length = 3;  // 先默认长度为3
    	function peek(){  // 返回栈顶元素
    		if (queue.length == 0) {
    			console.log("This Stack is empty!");
    			return;
    		}
    		console.log("栈顶元素：" + queue[queue.length-1]);
    	}
    	function pushStack(n){  // 入栈操作
    		if (queue.length == length) {
    			console.log("This Stack is full!");
    			return;
    		}
    		queue.push(n);
    		console.log( n + " 成功入栈！");
    	}
    	function popStack(){  // 出栈操作
    		if (queue.length == 0) {
    			console.log("This Stack is empty!");
    			return;
    		}
    		help = queue.splice(0,queue.length-1);
    		console.log( queue.pop() + " 成功出栈！");
    		swap();
    	}
    	function swap(){
    		var temp;
    		temp = queue;
    		queue = help;
    		help = temp; 
    	}
    	pushStack(5);  // 5 成功入栈！
    	pushStack(3);  // 3 成功入栈！
    	pushStack(1);  // 1 成功入栈！
    	peek();  // 栈顶元素：1
    	popStack();  // 1 成功出栈！
    	peek();  // 栈顶元素：3
    	pushStack(8);  // 8 成功入栈！
    	peek();  // 栈顶元素：8
    </script>

### 三、仅用栈结构实现队列结构 ###

1.思路：

① 先准备两个栈 stackPush、stackPop；

② 入队时：只在 stackPush 进行 push 操作；

③ 出队时： 考虑3种情况：

- stackPush、stackPop 都为空，则无法出队；

- stackPush不为空，stackPop为空：将stackPush除了第一个数去，都移到stackPop里，出队数为第一个数；

- stackPush、stackPop 都不为空：出队数为stackPop的最后一个数；

<script type="text/javascript">
    	// stackToQueue
    	var stackPush = [],stackPop = [],length = 3;
    	function peek(){  // 返回队头元素
    		if (stackPush.length == 0 && stackPop.length == 0) {
    			console.log("This Queue is empty!");
    			return;
    		}
    		if(stackPop.length != 0){
    			console.log("队头元素：" + stackPop[stackPop.length-1]);
    			return;
    		}
    		console.log("队头元素：" + stackPush[0]);
    	}
    	function pushQueue(n){  // 入队操作
    		if (stackPush.length == length) {
    			console.log("This Queue is full!");
    			return;
    		}
    		stackPush.push(n);
    		console.log( n + " 成功入队！");
    	}
    	function popQueue(){  // 出队操作
    		if (stackPush.length == 0 && stackPop.length == 0) {
    			console.log("This Queue is empty!");
    			return;
    		}
    		if (stackPop.length == 0 && stackPush.length != 0) {
    			stackPop = (stackPush.splice(1,stackPush.length-1)).reverse();
    			console.log( stackPush.pop() + " 成功出队！");
    			return;
    		}
    		console.log( stackPop.pop() + " 成功出队！");
    	}
    	pushQueue(3);  // 3 成功入队！
    	pushQueue(5);  // 5 成功入队！
    	pushQueue(8);  // 8 成功入队！
    	peek();  // 队头元素：3
    	popQueue();  // 3 成功出队！
    	pushQueue(1);  // 1 成功入队！
    	peek();  // 队头元素：5
    	popQueue();  // 5 成功出队！
    	popQueue();  // 5 成功出队！
    	popQueue();  // 5 成功出队！
    	popQueue();  // This Queue is empty!
    </script>

### 四、总结 ###

通过这次的学习，我完成了数组结构实现队列、栈的逻辑实现，以及仅用队列结构实现栈结构和仅用栈结构实现队列结构的实现。收获还是很大的，更了解了这三者之间的位置转换，也对js的函数、变量等有了更深刻的理解，更深刻的是熟悉了部分数组方法的使用。再接再厉吧！

发表评论取消回复

表情：

评论列表（有 0 条评论，245人围观）

还没有评论，来说两句吧...

相关阅读

相关 js：数组实现队列和栈、栈实现队列、队列实现栈

*目录** 一、利用数组结构实现大小固定的队列和栈二、仅用队列结构实现栈结构三、仅用栈结构实现队列结构四、总结 ------------------...

悠悠/ 2024年04月17日 05:55/ 0 赞/ 246 阅读

相关栈与队列——225. 用队列实现栈

1 题目描述 1. 用队列实现栈请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。实现

àì夳堔傛蜴生んèń/ 2023年10月08日 16:09/ 0 赞/ 61 阅读

相关双队列实现栈？双栈实现队列？

目录双队列实现栈最容易理解的办法双栈实现队列最容易理解的办法 -------------------- 双队列实现栈 > 单个队列是无法实现栈的

女爷i/ 2023年09月28日 17:54/ 0 赞/ 282 阅读

相关实现栈和队列、用栈实现队列，用队列实现栈。

一、实现一个栈就是一个指针下标，入栈加，出栈减。 / 我的栈 / public class MySt

一时失言乱红尘/ 2023年02月16日 12:15/ 0 赞/ 149 阅读

相关【队列栈】 LeetCode232. 用栈实现队列

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

ゞ浴缸里的玫瑰/ 2022年12月02日 15:24/ 0 赞/ 323 阅读

相关【队列栈】 LeetCode225. 用队列实现栈

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

た入场券/ 2022年12月02日 15:24/ 0 赞/ 349 阅读

相关 java：用栈实现队列+用队列实现栈

package com.stackqueue; import java.util.Stack; / 用两个栈模拟一个队列

Love The Way You Lie/ 2022年08月04日 05:26/ 0 赞/ 390 阅读

相关如何实现：双栈实现队列双队列实现栈

看代码就懂咯 package com.galaxy.fym.queueandstack; import java.util.Stack;

电玩女神/ 2022年07月14日 11:17/ 0 赞/ 371 阅读

相关 python队列和栈操作，两个栈实现队列，两个队列实现栈

参考：[http://docs.python.org/2/tutorial/datastructures.html\more-on-lists的官方代码][http_docs.

迈不过友情╰/ 2022年05月06日 11:30/ 0 赞/ 431 阅读

相关用栈实现队列和用队列实现栈

第一队列和栈的了解栈 -- 先进后出(FILO—First-In/Last-Out) 队列 -- 先进先出(FIFO—first in first out) 对

谁践踏了优雅/ 2022年03月17日 09:10/ 0 赞/ 510 阅读