数据结构之栈与队列

一。栈
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) {