A Different Kind of Structure

• People like sorted data (by name, grade, zip code)
• Fast look up: Order of FIND for (un)ordered array?

• Restricted access to data
• Underlying data structure hidden
• Abstract Data Type (ADT)
• Implementation may change, perhaps to improve efficiency

Stack

• New data is always added "on top" of stack
• The only accessible item is that which is currently on top
• LIFO: Last-In-First-Out
• Cheating?
  When used as an organizational tool, we sometimes access other elements directly
  If so, not really a stack

• Create or Construct a stack - Allow "user" to specify max size
• void push(item) -- insert or add an item
• item pop() -- delete or remove an item
• boolean isEmpty()
• boolean isFull()
• item peek() -- same as pop followed by push
• int size() -- current number on stack
• int maxSize() -- how many can I put on it
• void grow() -- become a larger structure
To avoid a "broken" data structure, we must check first also

Pre-Conditions / Errors

• push - stack must not be full
• Static or dynamic data structure?
  ...underlying data structure hidden
• pop - stack must not be empty
• peek . stack must not be empty

  if (!isFull())
     push(x);
  if (!isEmpty())
     x = pop();
  

• To avoid runtime error, stack user must check first using isEmpty() and isFull()

Alternative

• push returns true for success, false for fail
• pop returns a special (or null) value
  But, what value?
• peek returns a special (or null) value
• To avoid runtime error, stack user must check after calling method

  if (!push(x))
     // failed
  x = pop();
  if ( x == ERR)...
  

Design (using an array)

• What are the data members (fields) of the ADT?
• Where is the "top" of the stack?
• What if we organized the stack in the opposite direction?
  

  0	1	2	3	4	5	6	7	8	9	10	11
  8	3	10	5	11	12	7	9	1	4	2	6

• Stack Code Page 120
• Critical validation not done in push

  if (isFull()) {
       system.out.println("Attempt to push onto a full stack: " + j);
       // exit? throw exception?
  }
  stackArray[++top] = j;
  

  Or

  if (!isFull())
       stackArray[++top] = j;
  

• Use Stack to reverse an array Reverse Code
• Use Stack for matching brackets Brackets Code
• Java has a Stack class in java.util
  java.util.AbstractCollection
  java.util.AbstractList
  java.util.Vector
  java.util.Stack
  See docs.oracle.com
• Using Java's Stack

                  Stack lifo = new Stack();
  
                  for (int i = 1; i <= 10; i++)
                          lifo.push ( new Integer(i) );
  
                  while ( !lifo.empty() ) {
                          System.out.print ( lifo.pop() );
                          System.out.print ( ',' );
                  }
  
                  System.out.println (" LIFT-OFF!");
  

• Another ordered data structure
• First-In-First-Out
• Stack is LIFO
• Examples of programmer uses
  Print queue
  Window's event queue
• No "cuts" - cheating
• Create or Construct a queue
• Allow "user" to specify max size
  void insert(item) -- insert or add an item
  item remove() -- delete or remove an item
  item peekFront() -- get value w/o removing it
  boolean isEmpty()
  boolean isFull()
  item peekRear() -- get value w/o change
  int size() -- current number on stack
  int maxSize() -- how many can I put on it
  void grow() -- become a larger structure

• insert - queue must not be full
• remove - queue must not be empty
• peekFront - queue must not be empty
• To avoid runtime error, queue user must check first using isEmpty() and isFull()
  Alternative?
  Minimally, you must avoid corrupting the queue
• One Design: Like a stack
  Stationary front

  0	1	2	3	4	5	6	7	8	9	10	11
  8	3

  Stationary rear

  0	1	2	3	4	5	6	7	8	9	10	11
  										8	3

  Both front and rear move

  0	1	2	3	4	5	6	7	8	9	10	11
  				8	3

• 
• 
• 
• 
• Special cases
  1. Wrap around for insert & remove
  2. Empty queue
     • front == (rear + 1) mod max
     • nItems == 0
  3. Full queue
     • front == (rear + 1) mod max
     • nItems == max
  4. Initial conditions (construction) ??

Queue Implementation

• Each type needs
  • public Queue (int s) {
  • void insert (item) {
  • long remove () {
  • long peekFront() {
  • boolean isEmpty() {
  • boolean isFull() {
  • int size() {
• Queue Code
• Java has a queue data structure. See docs.oracle.com
• Is an array the best implementation for a queue?
• Implementation of double-ended queue needs:
  addFirst(item e) // and addLast(item e)
  Item e getLast() // and getFirst()

  0	1	2	3	4	5	6	7	8	9	10	11
  8	3	10	5	11	12	7	9	1	4	2	6

  
  Front: 3
  Rear: 8

  Most ArrayDeque operations run in amortized constant time.

  Amortization applies to our grow() method

  Some ops are O(N) - check description

Priority Queues - permits "cutting" in the line

• Items are ordered by priority, not when they arrive, i.e., not FIFO
• That means we can't use earlier code!
• Could have classes of data ordered by priority
• Within each class, still ordered by arrival
• Restaurant with
  Reservations
  Priority seating (call ahead)
  Walk-ins

  Computer Interrupts

  CPU scheduling

  Implementation change to support a simple priority queue

  Sorted items: ordered array with O(N) insert

  Unsorted items: O(N) remove & peek

Priority Queue Implementation