[자료구조] 스택(Stack)

🤔 스택이란

"stack"은 쌓다라는 의미로 데이터를 차곡차곡 쌓아올린 형태의 자료구조입니다.
예시로는 책상위에 쌓아올린 책, 프링글스 등이 있는데 이처럼 맨 위에 올려진, 가장 최근에 들어온 데이터가 가장 먼저 나가는 후입선출('LIFO')의 특징을 가지고 있습니다.

🧮 스택의 연산

pop(): 스택에서 가장 위에 있는 항목을 제거한다.
push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
peek(): 스택의 가장 위에 있는 항목을 반환한다.
isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

📝 스택의 구현

배열을 이용해서 구현할 때를 예로 들어보자. 처음으로 스택을 위한 배열을 하나 잡아 놓고, index 값을 0으로 잡는다. index가 0이면 스택이 비어 있는 것이고, 스택에 뭔가를 집어넣을 때는 index의 자리에 집어넣고 index를 하나 올리면 된다. index가 초기 배열 크기 이상이면 스택이 꽉 찬 것이다. 스택에서 뭔가를 뺄 때는 index에 있던 값을 돌려주고 index를 하나 뺀다.

연결 리스트로 구현하는 방법은 보다 단순하다. 메모리 상에 아이템을 위한 공간을 할당하고 새로운 아이템이 추가될 때 마다 포인터로 연결하기만 하면 된다.

🔍 스택의 사용 사례

• 웹브라우저 방문기록(뒤로 가기)
• 실행 취소(undo)
• 역순 문자열 만들기
• 후위 표기법 계산

출처 / 나무위키