[Javascript] 자료구조 - 스택(stack)

스택 : 먼저 들어온 데이터가 나중에 나가는 자료구조
새로운 원소를 삭제할 때는 마지막 원소가 삭제

 

전체 연산: 삽입 3 - 삽입 5 - 삭제 - 삽입 1 - 삭제 - 삽입 8 - 삽입 9

=> 3, 8, 9

 

	연산	시간 복잡도	설명
1	삽입(Push)	O(1)	스택에 원소 삽입
2	추출(Pop)	O(1)	스택에서 원소 추출
3	최상위 원소(Top)	O(1)	스택의 최상위 원소 확인
4	Empty	O(1)	스택이 비어 있는지 확인

 

Javascript 배열 자료형

- 일반적으로 스택을 구현할 때, Javascript의 배열 자료형을 사용

1. push() : 마지막 위치에 원소를 삽입, 시간 복잡도 O(1)

2. pop() : 마지막 위치에서 원소를 추출, 시간 복잡도 O(1)

let stack = [];

stack.push(5);
stack.push(3);
stack.push(1);
stack.push(4);
stack.pop();
stack.push(7);
stack.push(6);
stack.pop();

let reversed = stack.slice().reverse();
console.log(reversed); // [7, 1, 3, 5]
console.log(stack); // [5, 3, 1, 7]

 

* 연결 리스트로 스택 구현

• 스택을 연결 리스트로 구현하면, 삽입과 삭제에 있어서 O(1)을 보장할 수 있다.
• 연결 리스트로 구현할 때는 머리(head)를 가리키는 하나의 포인터만 가진다.
• 머리(head) : 남아있는 원소 중 가장 마지막에 들어온 데이터를 가리키는 포인터
• 삽입할때는 머리 위치에 데이터를 넣는다.
• 삭제할때는 머리 위치에서 데이터를 꺼낸다.