• 数据结构与算法之-队列和栈
  • 发布于 2个月前
  • 344 热度
    0 评论
  • Rock
  • 2 粉丝 32 篇博客
  •   
队列是一个常用的数据结构,是一种先进先出(First In First Out, FIFO)的结构,也就是说只能在表头进行删除,在表尾进行添加,下面我们实现一个简单的队列。

  1. package com.xtfggef.algo.queue;    
  2.     
  3. import java.util.Arrays;    
  4.     
  5. public class Queue<T> {    
  6.     
  7.     private int DEFAULT_SIZE = 10;    
  8.         
  9.     private int capacity;    
  10.         
  11.     private Object[] elementData;    
  12.         
  13.     private int front = 0;    
  14.     private int rear = 0;    
  15.         
  16.     public Queue()    
  17.     {    
  18.         capacity = DEFAULT_SIZE;    
  19.         elementData = new Object[capacity];    
  20.     }    
  21.         
  22.     public Queue(T element)    
  23.     {    
  24.         this();    
  25.         elementData[0] = element;    
  26.         rear++;    
  27.     }    
  28.     
  29.     public Queue(T element , int initSize)    
  30.     {    
  31.         this.capacity = initSize;    
  32.         elementData = new Object[capacity];    
  33.         elementData[0] = element;    
  34.         rear++;    
  35.     }    
  36.         
  37.     public int size()    
  38.     {    
  39.         return rear - front;    
  40.     }    
  41.         
  42.     public void add(T element)    
  43.     {    
  44.         if (rear > capacity - 1)    
  45.         {    
  46.             throw new IndexOutOfBoundsException("the queue is full!");    
  47.         }    
  48.         elementData[rear++] = element;    
  49.     }    
  50.     
  51.     public T remove()    
  52.     {    
  53.         if (empty())    
  54.         {    
  55.             throw new IndexOutOfBoundsException("queue is empty");    
  56.         }    
  57.             
  58.         @SuppressWarnings("unchecked")    
  59.         T oldValue = (T)elementData[front];    
  60.             
  61.         elementData[front++] = null;     
  62.         return oldValue;    
  63.     }    
  64.         
  65.     @SuppressWarnings("unchecked")    
  66.     public T element()      
  67.     {      
  68.         if (empty())      
  69.         {      
  70.             throw new IndexOutOfBoundsException("queue is empty");      
  71.         }      
  72.         return (T)elementData[front];      
  73.     }      
  74.         
  75.     public boolean empty()    
  76.     {    
  77.         return rear == front;    
  78.     }    
  79.         
  80.     public void clear()    
  81.     {    
  82.             
  83.         Arrays.fill(elementData , null);    
  84.         front = 0;    
  85.         rear = 0;    
  86.     }    
  87.     public String toString()    
  88.     {    
  89.         if (empty())    
  90.         {    
  91.             return "[]";    
  92.         }    
  93.         else    
  94.         {    
  95.             StringBuilder sb = new StringBuilder("[");    
  96.             for (int i = front  ; i < rear ; i++ )    
  97.             {    
  98.                 sb.append(elementData[i].toString() + ", ");    
  99.             }    
  100.             int len = sb.length();    
  101.             return sb.delete(len - 2 , len).append("]").toString();    
  102.         }    
  103.     }    
  104.     public static void main(String[] args){    
  105.         Queue<String> queue = new Queue<String>("ABC"20);    
  106.         queue.add("DEF");    
  107.         queue.add("egg");    
  108.         System.out.println(queue.empty());    
  109.         System.out.println(queue.size());    
  110.         System.out.println(queue.element());    
  111.         queue.clear();    
  112.         System.out.println(queue.empty());    
  113.         System.out.println(queue.size());    
  114.     }    
  115. }  
队列只能在表头进行删除,在表尾进行增加,这种结构的特点,适用于排队系统。

栈是一种后进先出(Last In First Out,LIFO)的数据结构,我们采用单链表实现一个栈。
[java] view plaincopy
  1. package com.xtfggef.algo.stack;    
  2.     
  3. import com.xtfggef.algo.linkedlist.LinkedList;    
  4.     
  5. public class Stack<T> {    
  6.     
  7.     static class Node<T> {    
  8.         T data;    
  9.         Node<T> next;    
  10.     
  11.         Node(T data, Node<T> next) {    
  12.             this.data = data;    
  13.             this.next = next;    
  14.         }    
  15.     
  16.         Node(T data) {    
  17.             this(data, null);    
  18.         }    
  19.     }    
  20.     
  21.     @SuppressWarnings("rawtypes")    
  22.     static LinkedList list = new LinkedList();    
  23.     
  24.     @SuppressWarnings("unchecked")    
  25.     public T push(T item) {    
  26.         list.addFromHead(item);    
  27.         return item;    
  28.     }    
  29.     
  30.     public void pop() {    
  31.         list.removeFromHead();    
  32.     }    
  33.     
  34.     public boolean empty() {    
  35.         return list.isEmpty();    
  36.     }    
  37.     
  38.     public int search(T t) {    
  39.         return list.indexOf(t);    
  40.     }    
  41.     
  42.     public static void main(String[] args) {    
  43.         Stack<String> stack = new Stack<String>();    
  44.         System.out.println(stack.empty());    
  45.         stack.push("abc");    
  46.         stack.push("def");    
  47.         stack.push("egg");    
  48.         stack.pop();    
  49.         System.out.println(stack.search("def"));    
  50.     }    
  51. }    

用户评论