[알고리즘] 2-3. 스택(Stack)

# 스택(Stack)

- 먼저 들어온 데이터가 나중에 나가는 자료구조

- 흔히 박스가 쌓인 형태, 

- 프링클스 과자 통 !!!

- 박스를 쌓은 뒤에 꺼낼 때는 가장 마지막에 올렸던 박스부터 꺼내야 한다.

- 새로운 원소를 삽입할 때는 마지막 위치에 삽입한다.

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

 

# 스택 자료구조의 중요성

- 스택은 굉장히 기본적인 자료구조이다.

- 다양한 알고리즘/ 코딩 테스트 문제에서 자주 등장한다.

 

# 스택 자료구조의 시간 복잡도

- 스택은 여러 가지 연산을 제공한다.

 

 

# 자바스크립트에서 스택을 구현하는 방법 - 배열 자료형

- 자바스크립트의 기본적인 배열 자료형은 다음의 두가지 메서드를 제공한다.

- push() 메서드: 마지막 위치에 원소를 삽입하며, 시간 복잡도는 O(1)이다.

- pop() 메서드: 마지막 위치에서 원소를 추출하며, 시간 복잡도는 O(1)이다.

- 따라서 일반적으로 스택을 구현할때, 자바스크립트의 배열(array) 자료형을 사용한다.

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();

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

 

결과
[1,3,2,5]
[5,2,3,1]

 

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

- 스택을 연결 리스트로 구현하면, 삽입과 삭제에 있어서 O(1)을 보장할 수 있다.

- 연결 리스트로 구현할 때는 머리(head)를 가리키는 하나의 개의 포인터만 가진다.

- 머리(head): 남아있는 원소 중 가장 마지막에 들어온 데이터를 가리키는 포인터

 

# 연결 리스트로 스택 구현하기 - 삽입 연산

- 삽입할 때는 머리(head) 위치에 데이터를 넣는다.

- 삭제할 때는 머리(head) 위치에서 데이터를 꺼낸다.