Stacks

Stacks

Implementation:

• Array
• Linked List

Operations:

• Push(S, x):

S.top == S.top + 1
S[S.top] = x

• Pop(S):

if IsEmpty(S)
    error "underflow"
else S.top = S.top - 1
    return S[S.top + 1]

• IsEmpty(S):

if S.top == 0
    return True
else return False

• StackTop(S):

if IsEmpty(S)
    error "underflow"
else return S[top]

• StackSize(S):

return top + 1

Errors:

• Underflow: An attempt was made to pop an empty stack.
• Overflow: An attempt was made to push an item onto a full stack.

Complexity:

• Time:
  • Access:
    • Worst Case:
    • Average Case:
  • Search:
    • Worst Case:
    • Average Case:
  • Insertion:
    • Worst Case:
    • Average Case:
  • Deletion:
    • Worst Case:
    • Average Case:
• Space:
  • Worst Case:

Applications:

• Parantheses Matching
• Infix to postfix expressions
• Infix expression computation
• Backtracking
• Activation records