Application Development, Product to Market
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use

Data Structure - Implement Stack and Queue

10/29/2013

0 Comments

 
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; 
  }
}
0 Comments



Leave a Reply.

    Categories

    All
    Algorithm
    Concurrency
    CQ
    Data Structure
    Design Pattern
    Developer Tool
    Dynamic Programming
    Entrepreneur
    Functional Programming
    IDE
    Java
    JMX
    Marketing
    Marklogic
    Memory
    OSGI
    Performance
    Product
    Product Management
    Security
    Services
    Sling
    Social Media Programming
    Software Development

    Feed Widget

    Archives

    May 2020
    March 2020
    April 2018
    March 2018
    February 2018
    December 2017
    March 2017
    November 2016
    June 2016
    May 2016
    April 2016
    October 2015
    September 2015
    August 2015
    September 2014
    July 2014
    June 2014
    May 2014
    March 2014
    January 2014
    December 2013
    November 2013
    October 2013
    September 2013
    August 2013
    July 2013
    June 2013

    RSS Feed

in loving memory of my mother  and my 4th aunt
Photos used under Creative Commons from net_efekt, schani, visnup, Dan Zen, gadl, bobbigmac, Susana López-Urrutia, jwalsh, Philippe Put, michael pollak, oskay, Creative Tools, Violentz, Kyknoord, mobilyazilar