Circular stack implementation

We had a recent post regarding circular queues implementation.

Let’s try to implement a circular stack. As previously, we have a pointer to the last element in the circular linked list. We can insert items in the last position, in the first position and we can remove items from the first position.

In order to obtain a LIFO behavior we can support inserting items in the first position and removing items from the first position.

An example will help us illustrate that:

1. last = null;

2. insert 1: last = 1;

3. insert 2: last = 1; 1->2-1>…

4. insert 3: last = 1; 1->3->2->1….

5. pop: last = 1; 1->2->1….

public class CircularStack<Item> implements Iterable<Item>{
    private CircularLinkedList<Item> items = new CircularLinkedList<Item>();
    
    public void push(Item item){
        items.insertFirst(item);
    }
    
    public Item pop(){
        return items.removeFirst();
    }
}

public class CircularLinkedList<Item> implements Iterable<Item> {

    private Node last;
    private int size;

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void insertFirst(final Item item) {
        if (last == null) {
            last = new Node();
            last.item = item;
            last.next = last;
        } else {
            Node first = last.next;
            Node newNode = new Node();
            newNode.item = item;
            last.next = newNode;
            newNode.next = first;
        }
        size++;
    }

    public Item removeFirst() {
        if (last == null) {
            return null;
        } else {
            Item result = last.next.item;
            if (last.next == last) {
                last = null;
            } else {
                last.next = last.next.next;
            }
            size--;
            return result;
        }
    }
}
Advertisements