01_Stack structure개념과 구현

- 후입선출(Last In First Out)의 구조

- 저장된 데이터의 역순으로 데이터를 처리함

- '짐을 쌓아 올린 형태'라는 의미의 구조

- 데이터의 저장은 push(밀어 넣기)라고 하며, 데이터의 처리는 pop(꺼내기)이라고 한다.

 

예) 인터넷 탐색의 '뒤로가기'기능,

    '실행취소'기능(Ctrl+z),

    텍스트 입력 커서,

    STACK 메모리 영역(변수의 선언, 함수의 return),

    CPU의 사칙 연산 (역폴리쉬 표기법)

 

시간복잡도 : stack 구조에서 커서top이 가지는 의미가 크다. 만약 top 변수가 없다면 for문으로 배열의 빈자리를 찾아야 하기 때문에, 반복문을 사용해야하고 결국은 O(n)의 시간복잡도를 가지게 된다. 그러나 top의 변수가 있다면 direct로 자리를 찾아 갈 수 있기 때문에 O(1) 시간복잡도를 갖게 된다.

 ex) 처리해야할 데이터 갯수가 100000개라면? top이 있는 경우 O(1), 없는 경우 O(100000) → 처리속도가 무지막지하게 차이난다.

 

아래 코드1,코드2 이미지는 stack구조를 구현한것. 

코딩의 특징을 말하자면,

1. 각 *함수의 초두에 error가 날 요소에 대한 예외처리를 가장 먼저 하는 것.

2. push와 pop은 따로 return값이 필요없지만, 아래와 같이 TRUE&FALSE를 return하여 switch문 내의 if문을 보다 더욱 쉽게 다룰 수 있음.

 

*함수란? 함수와 프로시저는 다르다.

            함수는 매개변수를 받으며 반환값이 존재하는 서브루틴(↔메인루틴main())을 함수라고 한다.

            프로시저는 함수의 일종이지만 반환값이 없는 함수다. void함수/void메서드

            따라서 위에서 언급한 함수란, pop과 push functions를 뜻한다.

Figure : 코드1

Figure : 코드2