一。栈
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(); }}
文章转自庄周梦蝶 ，原文发布时间5.17
4。队列的应用：线性规划方面
