DS Lec.6 - Stacks

Stack

• LIFO
• top에서 삽입, 삭제가 일어남.
• 주로 array나 linked list로 구현됨.
• Stack class in JAVA : Vector의 subclass ... not very desirable.

operations

• Main
  • push(object) : top에 원소 삽입.
  • Object pop() : top 원소 삭제 및 리턴.
• Others
  • Object top() : return top elem without remove
  • int size() : return # of elements stored
  • boolean isEmpty()

pop, top은 EmptyStackException()을, push는 FullStackException()을 throw한다.

Array-based Stack

• array가 다 차면 FullStackException()을 던진다.
• 이는 Stack ADT에 본질적이지 않다.

  Not Intrinsic??

  • Size limitation by characteristics of array
    => Stack ADT에서는 LIFO 기반 무한 Push 가능을 암묵적으로 정의하기 때문에, array 특성에 의한 FullStackException은 본질적으로 이 ADT와 맞지 않다는 것이다.

  ---

  그럼에도 array로 구현을 했다는 것은 'Stack ADT'를 '어떤 방식으로 구현할 것인가'의 문제이기 때문에 시도 자체를 틀렸다고 할 수는 없다.

  다시 살펴보는 ADT의 정의

  Abstract Data Type is consists of

  1. Data structure : A collection of data, its organization, structure, and properties
  2. Operations that can be performed : What can be done to change, manipulate or look at the data

  ---

  그래서 이러한 배열의 한계를 극복하기 위해 'growable array'를 사용한다고 한다. 이게 그 'incremental' or 'doubling' 이 전략들을 따르는 배열인 것 같다.

Application of Stack

ParenMatch Algorithm

Input : An array X of n tokens
Output : true if and only if all the grouping symbols in X match

// Let S be an empty Stack
for i in 0 to n-1 do
	jf X[i] is an opening grouping symbol then
    	S.push(X[i])
    elif X[i] is an closing group symbol then
    	if S.isEmpty() then
        	return False
        if S.pop() does not match the type of X[i] then
        	return False
    if S.isEmpty() then
    	return True
    else
    	return False

Evaluating arithmetic expressions

• operator precedence : *, / have higher precedence over +, -
• Associativity : 같은 precedence 그룹에서의 operators는 left to right 순서로 계산한다.
• ex) x - y + z : (x - y) + z rather than x - (y + z)
• valStk, opStk를 사용하며, 가장 낮은 우선 순위의 $로 끝을 나타낸다.
• IDEA : push each operator on the stack, but first pop and perform higher and equal precedence operations.

Algorithm EvalExp()
Input : a stream of tokens representing an arithmetic expression (with numbers)
Output : the value of the expression

while there is another token z:
	if isNumber(z):
    	valStk.push(z)
    else:
    	repeatOps(z)
        opStk.push(z)
repeatOps($)
return valStk.top()


Algorithm repeatOps(refOp)
while (valStk.size() > 1 and prec(refOp) <= prec(opStk.top())
	doOp()
    

Algorithm doOp(op):
	x <- valStk.pop()
    y <- valStk.pop()
    op <- opStk.pop()
    valStk.push(y op x)

if parenthesis added?
Algorithm EvalExp()
Input : a stream of tokens representing an arithmetic expression
Output: the value of the expression

opStk.push($)   // 바닥 표시자
while there is another token z:
    if isNumber(z):
        valStk.push(z)
    else if z == '(':
        opStk.push(z)
    else if z == ')':
        while opStk.top() != '(':
            doOp()
        opStk.pop()   // '(' 제거
    else:  // 연산자 (+, -, *, /, <= 등)
        repeatOps(z)
        opStk.push(z)

repeatOps($)
return valStk.top()

Algorithm repeatOps(refOp)
while (valStk.size() > 1
       and prec(refOp) <= prec(opStk.top()) 
       and opStk.top() != '(' 
       and opStk.top() != '$'):
    doOp()
    
Algorithm doOp()
x <- valStk.pop()
y <- valStk.pop()
op <- opStk.pop()
valStk.push(y op x)