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 StackThe 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{ 2. Stack only need to keep track of the top node (first node in the linked list) public class Stack{ 3. Flush out the implementation with boundary conditions in mind class Stack { Implement a QueueThe 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{ 2. Queue must keep track of the first and last nodes public class Stack{ 3. Flush out the implementation with boundary conditions in mind. Enqueue to the last node, dequeue from the first. class Queue {
0 Comments
Leave a Reply. |
Categories
All
Archives
May 2020
|