[모두가 기술 면접에 합격하는 그날까지]
https://github.com/Lee-Jin-Hyeok/technical-interview-question
목차
- 스택이란?
- 스택의 용어
- 스택의 구현
- 스택의 사용
3-1. 실생활에서의 스택
3-2. 프로그래밍에서의 스택 - 마무리
1. 스택이란?
스택은 후입선출 구조의 자료구조입니다.
여기서 후입선출이란 '마지막에 입력한 값이 먼저 출력된다'라는 뜻으로,
흔히 영어로 LIFO (Last In First Out) 라고 합니다.
따라서 자료 A -> 자료 B -> 자료 C 순서로 스택에 삽입 연산을 하였을 때,
자료 C -> 자료 B -> 자료 A 순서로 꺼낼 수 있습니다.
LIFO가 아니라 FILO (First In Last Out) 라고 쓸 수도 있는데,
보통 LIFO라고 많이 쓰고 마찬가지로 선입후출보다는 후입선출이라고 많이 씁니다.
2. 스택의 용어
스택은 간단한 자료구조인만큼 타 자료구조에 비해서 용어가 적고 제한적인 편입니다.
-
PUSH
PUSH는 스택에 자료를 삽입하기 위해서 사용하는 명령으로,
스택의 가장 위에 자료가 쌓이게 됩니다.
흔히 '푸쉬' 또는 '푸시'라고 읽습니다.스택을 구현할때 스택 포인터 (Stack Pointer)를 지정하게 되는데,
스택 포인터는 보통 가장 마지막에 쌓인 자료의 위치
또는 다음에 쌓일 자료의 위치를 가리킵니다.
따라서 PUSH 명령은 스택 포인터 또는 스택 포인터 다음 위치에
자료를 삽입하는 형태로 구현됩니다. -
POP
POP은 스택에 쌓인 자료를 꺼내기 위해서 사용하는 명령으로,
스택의 가장 위에 있는 자료를 꺼냅니다.
흔히 '팝'이라고 부릅니다.PUSH와 마찬가지로 스택 포인터가 가리키는 자료를 꺼내거나,
스택 포인터가 가리키는 자료 전의 자료를 꺼내는 형태로 구현됩니다. -
PEEK
PEEK은 스택에 샇인 자료 중
가장 위에 쌓인 자료를 읽기 위해서 사용하는 명령입니다.POP 명령은 데이터를 꺼냄과 동시에 삭제하는 반면에,
PEEK 명령은 데이터를 꺼내기만 하고 삭제는 하지 않습니다.
-
EMPTY
EMPTY는 스택이 비어 있다면 TRUE, 비어있지 않다면 FALSE를 리턴하는 명령입니다.
-
Stack Overflow
Stack Overflow는 스택이 가득차 있을 때 PUSH 명령을 수행하면 발생하는 오류입니다.Stack Overflow라는 유명한 개발관련 질문/답변 사이트가 존재합니다.
Stack Overflow는 개발자라면 반드시 한 번은 접속하게 되어있는 사이트로,
외국 사이트이기 때문에 보통 영문으로 대화합니다. -
Stack Underflow
Stack Underflow는 스택이 비어있을 때 POP 명령을 수행하면 발생하는 오류입니다.
3. 스택의 구현
스택은 간단한 자룍조인만큼 간단한 알고리즘으로 구현이 가능합니다.
구현하는 방법은 보통 배열과 리스트를 많이 사용하는데,
스택을 사용하는 경우에 수많은 저장 공간을 요구하는데 사용되지 않기 때문에
보통 크기가 결정되어 있는 배열로 간단하게 구현하는 경우가 많습니다.
4. 스택의 사용
4-1. 실생활에서의 스택
실생활에서 스택과 비슷한 현상을 많이 찾아볼 수 있습니다.
- 책을 쌓아 놓을 경우 가장 위에 있는 책부터 꺼낼 수 있다.
- 막다른 길에 차를 주차한 경우 가장 마지막에 주차한 차부터 나올 수 있다.
4-2. 프로그래밍에서의 스택
프로그래밍에서 '스택'이라는 자료구조를 사용하는 경우는 생각보다 많습니다.
- 브라우저의 '뒤로가기'
이동하는 페이지를 뒤로가기 스택에 쌓아두었다가
뒤로가기 버튼을 누르면 스택에서 꺼내서 그 페이지로 이동한다. - Ctrl + Z (Undo)
Ctrl + Z 를 누르면 실행된 수행을 취소하고 이전의 상태로 되돌립니다.
이는 스택에 이전의 상태를 차곡히 저장해두었다가
스택에서 가져와서 이전의 상태로 복구하기 때문에 가능합니다.
메모장에서는 이러한 스택의 크키가 하나(그냥 하나만 저장하는듯),
타 에디터(한글, word, ppt)의 경우에는 큰 스택의 크키를 가지고 있고
Ctrl + Z 를 여러번 사용해보면 스택의 크기에 제한이 있다는 것을 알 수 있습니다. - C나 Java의 메모리의 경우에 Stack이라는 공간이 존재하는데,
이 Stack과 여기서 말하는 스택은 같은 의미의 스택입니다.
함수 안에서 함수를 호출하는 경우 그 함수 스택이 쌓여,
후에 호출된 함수가 처리를 마쳐야 전에 호출된 함수가 마저 실행될 수 있습니다.
4. 마무리
스택은 너무나도 간단한 자료구조이기 때문에
별로 할 말이 없어서 글이 짧은 것 같습니다.
그래도 제 글을 보고 도움이 되셨을 분들, 그리고 제 글을 읽어주신 분들에게 감사드립니다.
더 나은 개발자가 되기 위해서 노력하겠습니다!!
