Stack และ ArrayStack

นึกภาพก่อน

นึกถึงจานที่ซ้อนกันเป็นตั้ง วางจานใหม่ได้แค่บนสุด และหยิบออกได้แค่ใบบนสุด จานที่วางทีหลังสุดจึงถูกหยิบก่อนเสมอ โครงสร้างข้อมูลที่ทำงานแบบนี้เรียกว่า stack (กองซ้อน) และลำดับแบบนี้เรียกว่า LIFO (Last-In First-Out)

เทียบกับที่เก็บข้อมูลที่เรียนมาแล้ว:

Interface ของ Stack

Stack มีบริการ 5 อย่าง การเพิ่มเรียกว่า push การลบเรียกว่า pop และการดูตัวบนสุดโดยไม่ลบเรียกว่า peek

public interface Stack {
  public boolean isEmpty();
  public int size();
  public void push(Object e);
  public Object peek();
  public Object pop();
}

สังเกตว่าไม่มี get(i) หรือ remove(e) แบบ List เพราะ stack ยอมให้แตะได้แค่ตัวบนสุด

ArrayStack: สร้าง stack ด้วยอาเรย์

แนวคิดเหมือน ArrayCollection คือมีอาเรย์ elementData กับตัวนับ size ต่างกันที่ เพิ่มและลบเฉพาะด้านท้ายของอาเรย์

• ข้อมูลอยู่ในช่อง 0 ถึง size - 1
• ช่อง 0 คือล่างสุดของ stack
• ช่อง size - 1 คือตัวบนสุด (top)
• ช่อง size คือช่องว่างถัดไปที่จะ push ลง

public class ArrayStack implements Stack {
  private Object[] elementData;
  private int size;

  public ArrayStack(int cap) {
    elementData = new Object[cap];
  }
  public boolean isEmpty() { return size == 0; }
  public int size() { return size; }
}

เหตุผลที่เลือกด้านท้าย: การเพิ่มหรือลบที่ท้ายอาเรย์ไม่ต้องเลื่อนข้อมูลตัวอื่นเลย ถ้าเลือกด้านหน้า (ช่อง 0) ทุกครั้งที่ push ต้องเลื่อนข้อมูลทั้งหมดไปหนึ่งช่อง ซึ่งช้ากว่ามาก

push

public void push(Object e) {
  if (size == elementData.length) {
    Object[] a = new Object[2 * size];
    for (int i = 0; i < size; i++) a[i] = elementData[i];
    elementData = a;
  }
  elementData[size++] = e;
}

1. ถ้าอาเรย์เต็ม (size == elementData.length) ให้สร้างอาเรย์ใหม่ขนาด สองเท่า แล้วคัดลอกข้อมูลเดิมมา
2. ใส่ e ลงช่อง size แล้วเพิ่ม size ขึ้นหนึ่ง

เวลาทำงาน: ถ้าไม่ต้องขยาย Θ(1) ถ้าต้องขยาย O(n) เพราะต้องคัดลอกข้อมูลทุกตัว

peek และ pop

public Object peek() {
  if (isEmpty()) throw new NoSuchElementException();
  return elementData[size - 1];
}
public Object pop() {
  Object e = peek();
  elementData[--size] = null;
  return e;
}

• peek คืนตัวบนสุดคือ elementData[size - 1] ถ้า stack ว่างจะโยน NoSuchElementException ใช้เวลา Θ(1)
• pop เรียก peek เก็บค่าไว้ก่อน แล้วลด size และใส่ null ในช่องที่เพิ่งว่าง
• ใส่ null เพื่อไม่ให้อาเรย์ยังอ้างอ็อบเจกต์ที่เอาออกไปแล้ว ไม่อย่างนั้น garbage collector จะเก็บอ็อบเจกต์นั้นไม่ได้
• อาเรย์ ไม่หดขนาด เมื่อ pop

ตัวอย่างไล่ทีละขั้น

จากสไลด์: เริ่มด้วย new ArrayStack(1) แล้ว push A, B, C ตามด้วย pop

กดเล่นด้านล่างเพื่อดูทีละขั้น หรือแก้คำสั่งและความจุเริ่มต้นเอง

public void push(Object e) {
  if (size == elementData.length) {
    Object[] a = new Object[2 * size];
    for (int i = 0; i < size; i++) a[i] = elementData[i];
    elementData = a;
  }
  elementData[size++] = e;
}

จุดที่มักพลาด

1. size++ กับ ++size และ --size กับ size--

สไลด์มี quiz สองข้อเรื่องนี้ จำตามความหมาย ไม่ต้องท่อง:

• push ต้องใส่ลงช่อง size (ช่องว่างถัดไป) แล้วจึง เพิ่ม → elementData[size++] = e;
• pop ต้อง ลดก่อน จึงจะได้ช่องของตัวบนสุด size - 1 → elementData[--size] = null;

ถ้าเขียน push เป็น elementData[++size] = e; ช่อง size เดิมจะถูกข้าม ข้อมูลไปอยู่ผิดช่อง และถ้าอาเรย์เหลือช่องเดียวจะเกิด ArrayIndexOutOfBoundsException

2. คิดว่า push ใช้ Θ(1) เสมอ

ครั้งที่อาเรย์เต็มใช้ O(n) ถ้าโจทย์ถามเวลาของ push ต้องดูว่าถามกรณีไหน

3. คิดว่า ArrayStack มี "stack overflow" เมื่อเต็ม

ArrayStack ในสไลด์ไม่มีวันเต็ม เพราะขยายอาเรย์เองทุกครั้ง คำว่า StackOverflowError ในวิชานี้หมายถึง java stack ของ JVM ซึ่งอยู่ในบทเรียนเรื่องกองซ้อนใน JVM

4. ลืมกรณี stack ว่าง

peek() และ pop() บน stack ว่างไม่คืน null แต่โยน NoSuchElementException และ pop ไม่ต้องตรวจเอง เพราะเรียก peek ซึ่งตรวจให้แล้ว

5. เข้าใจผิดว่า top อยู่ช่อง 0

top อยู่ที่ช่อง size - 1 ส่วนช่อง 0 คือตัวที่ push เข้ามาเป็นตัวแรก ซึ่งจะออกเป็นตัวสุดท้าย

ที่มา: STACK_5 (1).pdf หน้า 4–15 (นิยาม, interface, ArrayStack, quiz หน้า 13–14)