Stack Data Structure

We covered array and linked lists in previous article. Now we got a much simpler data structure "Stack". It represents a simple list which only allows you to extract/read items one by one. One important thing is you can only read/extract the latest inserted item. So, in order to read the last item, you have to pull out all the items. As said earlier, it is a simple data structure but it may have some use cases.

For example, some books placed on top of each other in a video game. Which allows only extracting one item (top one) at a time. Even though other data structures can be used but one can also use stack which is a much simpler and perfect for this use case.

Let's start our implementation by defining a struct for both stack and it's items.

type ItemLink = Option<Box<Item>>; 

pub struct Item
{
    data: i32,
    next: ItemLink
}

pub struct Stack
{
    top: ItemLink
}

Alright, so we got a Stack struct with only one pointer that points to the top item of the stack only. This pointer is also similar to what we used in Singly Linked List so it should be easier to diggest. Next, we got the Item struct which represents items in the stack and it contains a data field representing the data stored and a next field to represent the next item in the stack.

We didn't use generics this time to simply the process, but you can always proceed that path. But for now we are gonna move on like this!

Talking about the implementation of the structs, we need basic operations like push, pop, peek for our stack while the Item struct needs only a constructor. Here are the constructors for both structs:

impl Item
{
    pub fn new(data: i32) -> Item
    {
        Item {
            data,
            next: None
        }
    }
}

impl Stack
{
    pub fn new() -> Stack
    {
        Stack { top: None }
    }
}

Alright, so first we got the push method for the Stack struct:

pub fn push(&mut self, data: i32)
{
    let mut new_item = Item::new(data);

    new_item.next = self.top.take();

    self.top = Some(Box::new(new_item));
}

We got a mutable self reference because we will need to change the top field after pushing the item. First, we created a new item using the Item Constructor by passing the input data. Next, we marked the current top pointed item as next field of this new item. Then finally, we will mark this new item as the new top of the stack.

This was simple enough, but the pop method is even simpler.

pub fn pop(&mut self) -> Option<i32>
{
    if let Some(item) = self.top.take()
    {
        self.top = item.next;

        Some(item.data)
    } else {
        None
    }
}

We are simply marking the second top element as the new top if it exists and then returning the old top element's data.

Alright let's add peek methods to help us see the top item and modify it.

pub fn peek(&self) -> Option<&i32>
{
    if let Some(item) = self.top.as_ref()
    {
        Some(&item.data)
    } else {
        None
    }
}

pub fn peek_mut(&mut self) -> Option<&mut i32>
{
    if let Some(item) = self.top.as_mut()
    {
        Some(&mut item.data)
    } else {
        None
    }
}

Both of these peek and peek_mut methods are similar except the usage of mutable reference instead of immutable reference. We check if the there is an element on the top. If yes then return it's data otherwise return None.

That's all we needed for now. Here is the final code with some extra methods and tests:

type ItemLink = Option<Box<Item>>; 

pub struct Item
{
    data: i32,
    next: ItemLink
}

pub struct Stack
{
    top: ItemLink
}

impl Item
{
    pub fn new(data: i32) -> Item
    {
        Item {
            data,
            next: None
        }
    }
}

impl Stack
{
    pub fn new() -> Stack
    {
        Stack { top: None }
    }

    pub fn push(&mut self, data: i32)
    {
        let mut new_item = Item::new(data);

        new_item.next = self.top.take();

        self.top = Some(Box::new(new_item));
    }

    pub fn pop(&mut self) -> Option<i32>
    {
        if let Some(item) = self.top.take()
        {
            self.top = item.next;

            Some(item.data)
        } else {
            None
        }
    }

    pub fn peek(&self) -> Option<&i32>
    {
        if let Some(item) = self.top.as_ref()
        {
            Some(&item.data)
        } else {
            None
        }
    }

    pub fn peek_mut(&mut self) -> Option<&mut i32>
    {
        if let Some(item) = self.top.as_mut()
        {
            Some(&mut item.data)
        } else {
            None
        }
    }

    pub fn is_empty(&self) -> bool
    {
        self.top.is_none()
    }
}

#[cfg(test)]
mod tests
{
    use super::*;

    #[test]
    fn push()
    {
        let mut st = Stack::new();

        st.push(34);
        st.push(76);

        assert_eq!(st.peek(), Some(&76));
    }

    #[test]
    fn pop()
    {
        let mut st = Stack::new();

        st.push(34);
        st.push(76);

        assert_eq!(st.pop(), Some(76));
        assert_eq!(st.pop(), Some(34));
        assert_eq!(st.pop(), None);
    }

    #[test]
    fn peek()
    {
        let mut st = Stack::new();

        st.push(34);

        assert_eq!(st.peek(), Some(&34));
    }

    #[test]
    fn peek_mut()
    {
        let mut st = Stack::new();

        st.push(34);

        assert_eq!(st.peek_mut(), Some(&mut 34));

        *st.peek_mut().unwrap() = 76;

        assert_eq!(st.peek(), Some(&76));
    }

    #[test]
    fn is_empty()
    {
        let mut st = Stack::new();

        assert_eq!(st.is_empty(), true);

        st.push(34);

        assert_eq!(st.is_empty(), false);
    }
}

Time Complexity

All the operations including push, pop and peek in stack have time complexity of O(1) because it's a straightforward process there are no loops involved. No matter how big the stack gets, we can always say that these operations will take constant time.