[자료구조] 비전공자 자바스크립트 자료구조와 알고리즘 이해하기 - 자바스크립트 스택(Stack)

[자료구조] 비전공자 자바스크립트 자료구조와 알고리즘 이해하기 - 자바스크립트 스택(Stack)

자바스크립트 자료구조 스택에 대해 가볍게 배워봅시다 ;0 !! 

 

 

 

[자료구조] 비전공자 자바스크립트 자료구조와 알고리즘 이해하기 - 자바스크립트 스택(Stack)

 

 

 

스택이란? (Stack)

스택이란(stack): 먼저 들어온 데이터가 나중에 나가는 자료구조 형식이다. 

새로운 원소를 삭제할 때에는 마지막 원소가 삭제 된다.

 

스택에 대한 설명

 

 

자바스크립트 스택(Stack) 자료구조에 대한 시간 복잡도

연산	복잡도	설명
삽입(push)	O(1)	스택에 원소를 삽입하는 연산
추출(pop)	O(1)	스택에 원소를  추출하는 연산
최상위요소(top)	O(1)	스택의 최상위 요소 -> 마지막에 들어온 원소를 확인하는 연산
empty (true/false 반환)	O(1)	스택이 비어있는지 확인하는 연산

 

 

 

자바스크립트에서 배열(Array)로 스택(Stack)을 구현하는 방법

• push(): 마지막 위치에 원소를 삽입한다. O(1)
• pop(): 마지막 위치에 원소를 삭제한다. O(1)

// 배열로 스택 구현

let stack = [];

stack.push(5);
stack.push(2);
stack.push(1);
stack.push(7);
stack.pop();
stack.push(3);


console.log(stack)

배열로 스택 구현 결과값

자바스크립트에서 연결리스트로 스택(Stack)을 구현 시

• 연결리스트로 스택 구현시 > 삽입/삭제에 있어서 시간복잡도 O(1)이 보장된다.
• 머리(head)를 가리키는 한 개의 포인터만 가진다.
  • head(머리): 남아있는 원소 중 가장 마지막에 들어온 데이터를 가리키는 포인터