Stack

Stack이란?

스택은 last - in first - out(LIFO) 구조를 가진 자료구조이다 (후입선출, 마지막에 들어간 데이터가 먼저 나오는 구조.)

주요 operations:

• push(object): element 삽입.
• pop(): 가장 위 element(최근에 삽입된 데이터)를 빼냄.
  보조 operations:
• top(): 가장 위 element 제거하는 것 없이 출력만 함.
• int size(): 사이즈 나타냄.
• bool empty(): 스택이 비었는지 아닌지 나타냄.

Exeptions(예외처리)

• 스택이 비었을 때 pop(), top() 불가능 -> 예외처리

스택의 적용(보류)

Array-based Stack(배열 기반 스택)

가장 간단한 방법이다.
데이터를 배열을 이용해 저장하고, 배열에 대한 함수를 만들어주어 class로 관리한다.
왼쪽에서부터 오른쪽으로(0번 인덱스 → top) 데이터 추가한다.

오직 'top'을 통해서만 데이터가 들어가고 나간다.

methods

t = top index
size(): return = t+1

pop(): t <- t-1, return = S[t+1] (스택이 empty()라면 예외처리(StackEmpty))

push(o): t <- t+1, S[t] <- o (top의 인덱스가 사이즈랑 동일하면 예외처리(StackFull))

수행과 한계

Perfomance

• 각 operation은 O(1)의 시간복잡도를 갖는다.

Limitations

• 최대 사이즈를 미리 규정해주어야 하면 바뀔 수 없다.
• 스택이 꽉 차있을 때 새로운 element를 삽입하려하면 에러가 발생하여 예외처리를 해주어야 한다.

Parentheses Matching(X, n) (괄호 매칭)

Evaluating Arithmetic Expressions(스택을 이용한 사칙연산)(어렵)

• 각 연산은 우선순위를 따른다.[ * 는 +/-보다 우선순위가 높다.]
• 같은 우선순위 그룹 안의 연산은 왼쪽에서 오른쪽으로 계산한다.

발상: 각각의 연산자를 스택에 저장 -> 우선순위가 높은 순서대로 pop을 한다.

Stack as a Linked List

singly linked list를 이용하여 구현한다.
top element는 리스트의 첫번째 노드에 저장된다.
사용되는 공간은 O(n), operation of stack ADT = O(1)