[자료구조]_스택(Stack)

스택(Stack)

• 스택: 먼저 들어온 데이터가 나중에 나가는 자료구조
• 흔히 박스가 쌓인 형태를 스택(stack)이라고 한다
• 우리가박스를쌓은뒤에꺼낼때는,가장마지막에올렸던박스부터꺼내야한다.
• 새로운 원소를 삽입할 때는 마지막 위치에 삽입한다.
• 새로운 원소를 삭제할 때는 마지막 원소가 삭제된다.

 

Stack 시간 복잡도

	연산	시간 복잡도 설명	설명
1	삽입(Push)	𝑂(1)	스택에 원소를 삽입하는 연산
2	추출(Pop)	𝑂(1)	스택에서 원소를 추출하는 연산
3	최상위 원소(Top)	𝑂(1)	스택의 최상위 원소(가장 마지막에 들어온 원소)를 확인하는 연산
3	Empty	𝑂(1)	스택이 비어있는지 확인하는 연산

 

JS에서의 Stack

• JavaScript에서 스택을 구현할 때 배열(Array) 자료형을 사용한다.
• 𝑝𝑜𝑝() 메서드: 마지막 위치에서 원소를 추출하며, 시간 복잡도는 𝑂(1) 이다.
• 𝑝𝑢𝑠h() 메서드: 마지막 위치에 원소를 삽입하며, 시간 복잡도는 𝑂(1) 이다.
   

let stack = [];
// 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.push(5);
stack.push(2);
stack.push(3);
stack.push(7);
stack.pop();
stack.push(1);
stack.push(4);
stack.pop();
console.log(stack); // [ 5, 2, 3, 1 ]

 

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

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