Bags, Queues and Stacks

1. Stack: Examine the item most recently added. --> FILO
    Queue: Examine the item least recently added. --> FIFO

 

2. Linked list implementation of Stack :

 

public class LinkedStack<Item>
{
    private Node first = null;
    private class Node
    {
      Item item;
      Node next;
     }

    public boolean isEmpty()
    { return first == null; }

     public void push(Item item)
    {
      Node oldfirst = first;
      first = new Node();
      first.item = item;
      first.next = oldfirst;
    }

     public Item pop()
    {
      Item item = first.item;
      first = first.next;
      return item;
    }
 }

 

3. Array implementation of Stack :

  a) Underflow : throw exception if pop from an empty stack.

  b) Loitering : set the reference in array to null when the item is popped

  c) Overflow : If array is full, create a new array of twice the size, and copy items. ( ~3N)

  d) Shrink :  halve size of array when array is one-quarter full.

 

4. Linked List implementation of Queue:

public class LinkedQueue<Item>
{
  private Node first, last;
  
  private class Node
  { /* same as in Stack */ }

  public boolean isEmpty()
  { return first == null; }
  
  public void enqueue(Item item)
  {
    Node oldlast = last;
    last = new Node();
    last.item = item;
    last.next = null;
    if (isEmpty()) first = last;
    else oldlast.next = last;
  }

  public Item dequeue()
  {
    Item item = first.item;
    first = first.next;
    if (isEmpty()) last = null;
    return item;
  }
}

 

5.  Array implementation of a queue.
  a)  Use array q[] to store items in queue.
  b)  enqueue(): add new item at q[tail].
  c)  dequeue(): remove item from q[head].
  d)  Update head and tail modulo the capacity.
  e)  Add resizing array.

 

6. Bag : Adding items to a collection and iterating (when order doesn't matter).

 

 

7.  Stack Applications :

    a)  Parsing in a compiler.
    b)  Java virtual machine.
    c)  Undo in a word processor.
    d)  Back button in a Web browser.
    e)  PostScript language for printers.

    f)  Implementing function calls in a compiler.

 

8. How a compiler implements a function.
    a)  Function call: push local environment and return address.
    b)  Return: pop return address and local environment.

   Note. We can always use an explicit stack to remove recursion.

 

9. Dijkstra's two-stack algorithm computes the same value if the operator occurs after the two values. And all of the parentheses are redundant! We can use postfix or "reverse Polish" notation:

    1 2 3 + 4 5 * * +