• 数据结构与算法之-队列和栈
  • 阿汤哥 发表于 2014/11/19 9:44:00 | 分类标签: 数据结构 队列 栈的原理
  • 队列是一个常用的数据结构,是一种先进先出(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. }    

  • 请您注意

    ·自觉遵守:爱国、守法、自律、真实、文明的原则

    ·尊重网上道德,遵守《全国人大常委会关于维护互联网安全的决定》及中华人民共和国其他各项有关法律法规

    ·严禁发表危害国家安全,破坏民族团结、国家宗教政策和社会稳定,含侮辱、诽谤、教唆、淫秽等内容的作品

    ·承担一切因您的行为而直接或间接导致的民事或刑事法律责任

    ·您在编程中国社区新闻评论发表的作品,本网站有权在网站内保留、转载、引用或者删除

    ·参与本评论即表明您已经阅读并接受上述条款

  • 感谢本文作者
  • 作者头像
  • 昵称:阿汤哥
  • 加入时间:2013/5/15 0:00:00
  • TA的签名
  • 这家伙很懒,虾米都没写
  • +进入TA的空间
  • 以下内容也很赞哦
分享按钮