js 데이터 구조와 알고리즘의 스택과 큐에 대한 자세한 설명

1. 정의

스택은 중요한 선형 구조입니다. 스택은 선입선출(LIFO) 선형 목록으로, 테이블 끝에서만 삭제 및 삽입 작업이 필요합니다. 스택의 경우 이 꼬리를 스택의 상단이라고 하며 해당 헤더를 스택의 하단이라고 합니다.

스택 작업은 이 선형 테이블의 끝에서만 수행될 수 있습니다.

스택의 삽입 작업(푸시)을 푸시라고 하며 푸시 또는 푸시라고도 합니다.

스택의 삭제 작업(팝)을 스택 팝핑이라고 하며, 스택 팝핑이라고도 합니다.

2. 스택의 순차 저장 구조

스택의 본질은 선형 테이블이고, 선형 테이블은 두 가지 저장 형태를 가지므로 스택도

스택의 순차 저장 구조로 나뉜다. 그리고 스택의 체인 저장 구조.

순차적 저장 구조: 데이터 요소는 연속된 주소를 가진 저장 단위에 저장되며, 데이터 간의 논리적, 물리적 관계는 일관됩니다.

예를 들어 우리 프로그래밍 언어의 배열 구조는 다음과 같습니다.

체인 저장 구조: 모든 저장 단위에 데이터 요소를 저장합니다. 이 저장 단위 그룹은 연속적이거나 불연속적일 수 있습니다.

분명히 체인 저장 구조에서 데이터 요소의 저장 관계는 논리적 관계를 반영하지 않으므로 데이터 요소의 주소를 저장하기 위해 포인터를 사용해야 관련 데이터 요소의 위치를 ​​알 수 있습니다. 주소를 통해 찾았습니다.

초기 스택에는 데이터가 포함되어 있지 않으며, 이를 빈 스택이라고 합니다. 이때 스택의 맨 위가 스택의 맨 아래가 됩니다. 그러면 스택의 상단에서 데이터가 들어오고 스택의 상단과 하단이 분리되어 전체 스택의 현재 용량이 더 커집니다. 스택에서 데이터가 팝되면 스택의 상단이 아래로 이동하고 전체 스택의 현재 용량이 작아집니다.

3. 스택 작업

(1). 기본 작업

/** * 
 * 栈的构造函数 
 * */ 
function Stack() { 
 	// 用数组来模拟栈 
	this.dataStore = []; //底层数据结构是数组
	this.top = 0; //top应该是等于数组的length的
}
//栈需要有如下的方法
Stack.prototype = {
	/**
	 * 1. push()
	 * 向栈中压入一个新元素， 需要将其保存在数组中变量 top 所对
	 * 应的位置， 然后将 top 值加 1， 让top指向数组中下一个空位置
	 * 特别注意 ++ 操作符的位置， 它放在 this.top 的后面， 这样新入栈的元素就被放在
	 * top 的当前值对应的位置， 然后再将变量 top 的值加 1， 指向下一个位置
	 * */
	push:function(element){
		this.dataStore[this.top++] = element;
	},
	/**
	 * pop() 方法恰好与 push() 方法相反——它返回栈顶元素， 同时将变量 top 的值减 1
	 * 也可以改造一下,只--this.top,不返回栈顶元素
	 * */
	pop:function(){
		return this.dataStore[--this.top];
	},
	/**
	 * peek() 方法返回数组的第 top-1 个位置的元素， 即栈顶元素
	 * */
	peek:function(){
		return this.dataStore[this.top-1];
	},
	length:function(){
		return this.top;
	},
	clear:function(){
		 this.top = 0;
	}
};
//测试 Stack 类的实现
var s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
console.log("length: " + s.length());//length: 3
console.log(s.peek());//Bryan
var popped = s.pop();
console.log("The popped element is: " + popped);//The popped element is: Bryan
s.push("Cynthia");
s.clear();
console.log("length: " + s.length());//length: 0

관련 권장 사항:

PHP 배열 기반 스택 및 대기열 기능 예제 공유

위 내용은 js 데이터 구조와 알고리즘의 스택과 큐에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!