✔ 1. 스택이란?

칵테일처럼 데이터를 차곡차곡 쌓아올린 형태이다. 따라서 스택에 저장된 원소는 top(맨 위)으로 정한 곳에서만 접근이 가능하며, 삽입/ 삭제 또한 top에서만 가능하다. 마지막에 삽입한 원소가 가장 먼저 삭제되는 후입선출 구조(LIFO, Last-In-First-Out)이다.

스택을 구현할 때에는, 배열(단순연결리스트)로 구현할 수 도 있고, 링크드리스트(이중연결리스트)로도 가능하다. 하지만 배열이 더 편하다!

✔ 2. 스택의 기능

• 원소 가져오기 : 스택의 top에 있는 원소를 가져온다.
• 삽입 : 새 원소를 top에 삽입한다.
• 삭제 후 반환 : top에 있는 원소를 삭제한 후 반환한다. 삭제할 때에는 underflow가 발생하는지 체크해야한다.

✔ 3. 스택의 응용

회문(palindrome) 검사

회문은 앞에서 읽나 뒤에서 읽나 동일한 문자열이다.(ex. 우영우, 토마토) 문자열의 길이가 짝수일때면 1/2로 나누어 전반부를 스택에 push 한 후, 후반부 문자를 차례대로 pop한 문자와 비교한다. 문자열의 길이가 홀수일때면 1/2한 결과의 몫 까지 전반부로 생각해 전반부를 스택에 push한 후, 가운데 문자는 버리고 후반부 문자를 차례대로 pop한 문자와 비교한다.
마지막까지 비교결과 두 문자가 동일하고 스택이 empty가 되면 해당 문자열은 회문인 것으로 판단한다.

후위표기법(postfix notation) 수식 계산

후위표기법은 괄호 없이 수식을 표현하는 것이다. 앞에서 부터 피연산자이면 스택에 push하고 연산자(op)이면 pop을2회 수행하여 나온 두개의 피연산자는 연산을 수행하고 그 결과 값을 push 한다.

✔ 4. 스택 수행시간

• 상각분석(각 연산의 평균 수행시간) : O(1)
• 삽입/ 삭제 : O(1)
• overflow/underflow : O(N)