# Stack - Question 2 Answers

## 2 a

\begin{algorithm}
\caption{Stack - Array Implementation}
\begin{algorithmic}
\REQUIRE size = max number of items in the stack
\OUTPUT stack data structure
\FUNCTION{create}{size}
\STATE stack $\gets$ new memory allocation
\STATE stack.array $\gets$ new array with size elements
\STATE stack.size $\gets$ size
\STATE stack.top = -1
\RETURN stack
\ENDFUNCTION
\STATE
\REQUIRE stack = stack data structure
\REQUIRE value = value to add to the stack
\FUNCTION{push}{stack, value}
\IF{stack.top + 1 = stack.size}
\STATE stack overflow
\ENDIF
\STATE stack.top $\gets$ stack.top + 1
\STATE stack.array[stack.top] $\gets$ value
\ENDFUNCTION
\STATE
\REQUIRE stack = stack data structure
\OUTPUT value at the top of the stack
\FUNCTION{pop}{stack}
\IF{stack.top = -1}
\STATE stack underflow
\ENDIF
\STATE stack.top $\gets$ stack.top - 1
\RETURN stack.array[stack.top + 1]
\ENDFUNCTION
\STATE
\REQUIRE stack = stack data structure
\OUTPUT value at the top of the stack
\FUNCTION{peek}{stack}
\IF{stack.top = -1}
\STATE stack underflow
\ENDIF
\RETURN stack.array[stack.top]
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

## 2 b

\begin{algorithm}
\caption{Stack - Linked List Implementation}
\begin{algorithmic}
\OUTPUT stack data structure
\FUNCTION{create}{}
\STATE stack $\gets$ new memory allocation
\STATE stack.list $\gets$ new linked list
\STATE stack.itemCount = 0
\RETURN stack
\ENDFUNCTION
\STATE
\REQUIRE stack = stack data structure
\REQUIRE value = value to add to the stack
\FUNCTION{push}{stack, value}
\STATE stack.itemCount $\gets$ stack.itemCount + 1
\ENDFUNCTION
\STATE
\REQUIRE stack = stack data structure
\OUTPUT value at the top of the stack
\FUNCTION{pop}{stack}
\IF{stack.itemCount = 0}
\STATE stack underflow
\ENDIF
\STATE value $\gets$ stack.list.head
\STATE stack.itemCount $\gets$ stack.itemCount - 1
\RETURN value
\ENDFUNCTION
\STATE
\REQUIRE stack = stack data structure
\FUNCTION{peek}{stack}
\IF{stack.itemCount = 0}
\STATE stack underflow
\ENDIF