9.2: Stack Implementation

Last updated
Save as PDF

Page ID: 34684

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

There are two ways to implement a stack:

Using array
- Pros: Easy to implement. Memory is saved as pointers are not involved.
- Cons: It is not dynamic. It doesn’t grow and shrink depending on needs at runtime.
Using linked list
- Pros: The linked list implementation of stack can grow and shrink according to the needs at runtime.
- Cons: Requires extra memory due to involvement of pointers.

We will look at using a Linked list to implement a Stack. Most of what we need to know we have already covered in our discussion of Linked Lists - stacks really only need a 'push' to build the stack. However, there are a couple of pieces that we need to add. In the "stack terminology" we have a 'pop' capability, which is just like the delete in our linked list. We also need to implement the 'peek' functionality - this simply returns the value that is sitting on the top of the stack, but does not alter the stack in any way. Lastly we will have to be able to determine if the stack is empty.

We will look at some of the code pieces next.

Adapted from: "Stack Data Structure (Introduction and Program)" by Bhupendra Rathore is licensed under CC BY-SA 4.0