Data Structure - Implement Stack and Queue

A clear thought process helps coders to get to the solutions. This post simply walks you through my thought process of how to implement some very basic data structure - a stack and a queue.

Implement a Stack

The approach

Use single linked link to implement a stack. A stack is a single linked list (nodes), first-in-last-out. Each node has an element of something (Object) plus a pointer to the next node. The key thought is to maintain a pointer to the first node in the list (top node of the stack).

Thought Process

1. Define the contract of the functions for Stack

public class Stack{
  public void push(Node);
  public Object pop();
  ...
}

2. Stack only need to keep track of the top node (first node in the linked list)

public class Stack{
  private Node top;
  ...
}

3. Flush out the implementation with boundary conditions in mind

class Stack { 
  private Node top;

  public Object pop() {
    if (top != null) {           // boundary condition - nothing to pop
      Object item = top.data; 
      top = top.next;
      return item;
    }
    return null;
  }

  public void push(Object item){ 
    Node t = new Node(item); 
    t.next = top;
    top = t;
  }
}

Implement a Queue

The approach

Use single linked link to implement a queue. A queue is a linked list (nodes) of first-in-first-out. Each node has an element of something (Object) and points to the next node. The key thought is to maintain a pointer points to the first node and another pointer points last node of the queue. On enqueuing, add node to the last node; on dequeuing, get the first node out. Alternatively, on enqueuing, add node to the first node; on dequeuing, get the last node out.

Thoughts Process

1. Define the contract of the functions for Queue

public class Stack{
  public void enqueue(Node);
  public Object dequeue();
  ...
}

2. Queue must keep track of the first and last nodes

public class Stack{
  private Node first, last;
  ...
}

3. Flush out the implementation with boundary conditions in mind. Enqueue to the last node, dequeue from the first.

class Queue {
  private Node first, last;

  public void enqueue(Object item) {
    if (!first) {
      Node temp = new Node(item); 
      first = temp;
      last = temp;
    } else {
      last.next = new Node(item);
      last = last.next; 
    }
  }

  public Object dequeue() {
    if (first != null) {
      Object item = first.data; 
      first = first.next; 
      return item;
    }
    return null; 
  }
}