庄周梦蝶

生活、程序、未来
   :: 首页 ::  ::  :: 聚合  :: 管理

数据结构之栈与队列

Posted on 2007-02-20 12:51 dennis 阅读(677) 评论(0)  编辑  收藏 所属分类: 数据结构与算法
一。栈
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;
    }

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


}

4。队列的应用：线性规划方面

只有注册用户登录后才能发表评论。
网站导航: