用数组实现动态变化的堆栈

  1. package com.algorithms.base;
  3. public class Stack<Item> {
  4.     private int n; // 元素个数
  5.     private Item[] a;
  7.     public Stack() {
  8.         n = 0;
  9.         a = (Item[]) new Object[1];
  10.     }
  12.     private void reSize(int length) {
  13.         Item[] temp = (Item[]) new Object[length];
  14.         for (int i = 0; i < n; i++) {
  15.             temp[i] = a[i];
  16.         }
  17.         a = temp;
  18.     }
  20.     public boolean isEmpty() {
  21.         return n == 0;
  22.     }
  24.     public boolean isFull() {
  25.         return n == a.length;
  26.     }
  28.     public int size() {
  29.         return a.length;
  30.     }
  32.     public void push(Item t) {
  33.         if (n == a.length) {
  34.             reSize(2 * a.length);
  35.         }
  36.         a[n] = t;
  37.         n++;
  38.     }
  40.     public Item pop() {
  41.         n--;
  42.         Item temp = a[n];
  43.         a[n] = null;
  44.         if (n == a.length / 4 && n > 0)
  45.             reSize(a.length / 2);
  46.         return temp;
  47.     }
  48. }

链表实现

  1. package com.algorithms.base;
  3. public class LinkStack<Item> {
  4.     private Node first;
  5.     private int n;
  6.     private class Node {
  7.         Node next;
  8.         Item item;
  9.     }
  11.     public boolean isEmpty() {
  12.         return n == 0;
  13.     }
  15.     public Item pop() {
  16.         Item temp = first.item;
  17.         first = first.next;
  18.         n--;
  19.         return temp;
  20.     }
  22.     public void push(Item item) {
  23.         Node oldfirst = first;
  24.         first = new Node();
  25.         first.next = oldfirst;
  26.         first.item = item;
  27.         n++;
  28.     }
  29. }