874      技術社區[雲棲]

數據結構之棧與隊列

/** *//**
 * 
 */
package com.sohu.blog.denns_zane.stackqueue;

/** *//**
 * @author dennis
 * 
 */
public abstract class AbstractStack {
    public abstract Object pop();

    public abstract void push(Object obj);

    public abstract Object topEl();

    public abstract boolean isEmpty();

    public abstract void clear();
}


/** *//**
 * 
 */
package com.sohu.blog.denns_zane.stackqueue;

/** *//**
 * @author dennis
 * 
 */
public class Stack extends AbstractStack {
    private java.util.ArrayList pool = new java.util.ArrayList();

    public Stack() {
    }

    public Stack(int n) {
        pool.ensureCapacity(n);
    }

    public void clear() {
        pool.clear();
    }

    public boolean isEmpty() {
        return pool.isEmpty();
    }

    public Object topEl() {
        if (isEmpty())
            throw new java.util.EmptyStackException();
        return pool.get(pool.size() - 1);
    }

    public Object pop() {
        if (isEmpty())
            throw new java.util.EmptyStackException();
        return pool.remove(pool.size() - 1);
    }

    public void push(Object el) {
        pool.add(el);
    }

    public String toString() {
        return pool.toString();
    }
}

/** *//**
 * 
 */
package com.sohu.blog.denns_zane.stackqueue;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/** *//**
 * @author dennis
 * 
 */
public class HuiWen {

    /** *//**
     * @param args
     */
    public static void main(String[] args) {
        BufferedReader buffer = new BufferedReader(new InputStreamReader(
                System.in));
        try {
            String str = buffer.readLine();
            if (str != null)
                isHuiWen(str);

        } catch (IOException e) {
            e.printStackTrace();
        }
        // TODO Auto-generated method stub

    }

    public static void isHuiWen(String str) {
        int length = str.length();
        char[] ch = str.toCharArray();
        Stack stack = new Stack();
        if (length % 2 == 0) {
            for (int i = 0; i < length / 2; i++) {
                stack.push(ch[i]);
            }
            for (int i = length / 2; i < length - 1; i++) {
                if (ch[i] != ((Character) stack.pop()).charValue()) {
                    System.out.println("不是回文字！！");
                    return;
                }

            }

            System.out.println(str + "是回文字！！");
        } else {
            for (int i = 0; i < length / 2; i++) {
                stack.push(ch[i]);
            }
            for (int i = (length / 2 + 1); i < length - 1; i++) {
                if (ch[i] != ((Character) stack.pop()).charValue()) {
                    System.out.println("不是回文字！！");
                    return;
                }
            }
            System.out.println(str + "是回文字！！");
        }

    }

}

/** *//**
 * 
 */
package com.sohu.blog.denns_zane.stackqueue;

/** *//**
 * @author dennis
 * 
 */
// queue implemented as an array
public class ArrayQueue {
    private int first, last, size;

    private Object[] storage;

    public ArrayQueue() {
        this(100);
    }

    public ArrayQueue(int n) {
        size = n;
        storage = new Object[size];
        first = last = -1;
    }

    public boolean isFull() {
        return first == 0 && last == size - 1 || first == last + 1;
    }

    public boolean isEmpty() {
        return first == -1;
    }

    public void enqueue(Object el) {
        if (last == size - 1 || last == -1) {
            storage[0] = el;
            last = 0;
            if (first == -1)
                first = 0;
        } else
            storage[++last] = el;
    }

    public Object dequeue() {
        Object tmp = storage[first];
        if (first == last)
            last = first = -1;
        else if (first == size - 1)
            first = 0;
        else
            first++;
        return tmp;
    }

    public void printAll() {
        for (int i = 0; i < size; i++)
            System.out.print(storage[i] + " ");
    }
}

2）更適合實現隊列的雙向鏈表：
/** *//**
 * 
 */
package com.sohu.blog.denns_zane.stackqueue;

/** *//**
 * @author dennis
 * 
 */
public class Queue {
    private java.util.LinkedList list = new java.util.LinkedList();

    public Queue() {
    }

    public void clear() {
        list.clear();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public Object firstEl() {
        return list.getFirst();
    }

    public Object dequeue() {
        return list.removeFirst();
    }

    public void enqueue(Object el) {
        list.add(el);
    }

    public String toString() {
        return list.toString();
    }


}

文章轉自莊周夢蝶  ，原文發布時間5.17

最後更新：2017-05-17 11:36:28

  上一篇：  算法之簡單排序

  下一篇：  歡迎加入阿裏雲雲HBase技術交流群