数据结构之栈与队列

一。栈
1。概念：栈（stack）是一种线性数据结构，只能访问它的一端来存储或者读取数据。栈是一种后进先出的结构（LIFO)
2。栈的主要操作：
.clear()——清栈
.isEmpty()——检查栈是否为空
.push(e)——压栈
.pop()——出栈
.topEl()——返回栈顶元素

3。栈的java实现：使用数组链表实现

/** *//**
 * 
 */
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();
    }
}

4。栈的应用：
1）程序中的匹配分割符，如(,[,{等符号
2）大数的运算，比如大数相加，转化为字符串，利用栈处理
3）回文字，例子：

/** *//**
 * 
 */
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 + "是回文字！！");
        }

    }

}

4）java虚拟机中的本地方法栈


二。队列（queue）
1。概念：队列也是线性结构，从尾部添加元素，从头部删除元素。与栈相反，队列是先入先出结构（FIFO）
2。队列主要操作：
.clear() ——清空队列
.isEmpty()——判断队列是否为空
.enqueue(el)——从尾部插入元素el
.dequeue()——从队列中起出第一个元素，并删除
.firstEl()——返回队列第一个元素，不删除。

3。队列的实现：
1）环形数组：需要考虑队列已满的两种情况，1，第一个元素在最后一个元素之后；2，第一个元素在第一单元，最后一个元素在最后单元。给出一个java实现：

/** *//**
 * 
 */
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