스택.md

스택

• 스택: 먼저 들어온 데이터가 나중에 나가는 자료구조이다.
• 흔히 박스가 스택이라고 생각하면 편하다

• 새로운 원소를 삽입할 때는 마지막 위치에 삽입함

• 새로운 원소를 삭제할 때는 마지막 원소가 삭제됨

스택의 시간 복잡도

• 스택은 여러 가지 연산을 제공함.

배열 자료형

• js의 기본적인 배열 자료형은 두 가지 메서드를 제공한다.
• push() 메서드 : 마지막 위치에 원소를 삽입하며, 시간 복잡도는 O(1)이다.
• pop() 메서드 : 마지막 위치에서 원소를 추출하며, 시간 복잡도는 O(1)이다.

let stack = [];

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

let reversed = stack.slice().reverse();
console.log(reversed); // 최상위 원소부터 출력
console.log(stack);

// [ 1, 3, 2, 5 ]
// [ 5, 2, 3, 1 ]

연결 리스트로 스택 구현하기

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

• 8 삽입 예시)
• 삽입할 때는 머리 위치에 데이터를 넣는다.

• 하나의 데이터 삭제 예시)
• 삭제할 때는 머리 위치를 변경하여 데이터를 꺼낸다.

참고

패캠 자료구조 나동빈