发布于 2016-07-31 08:03:45 | 159 次阅读 | 评论: 0 | 来源: 网友投递
Java程序设计语言
java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台（即JavaEE(j2ee), JavaME(j2me), JavaSE(j2se)）的总称。
栈和队列：
一般是作为程序员的工具，用于辅助构思算法，生命周期较短，运行时才被创建；
访问受限，在特定时刻，只有一个数据可被读取或删除；
是一种抽象的结构，内部的实现机制，对用户不可见，比如用数组、链表来实现栈。
模拟栈结构
同时，只允许一个数据被访问，后进先出
对于入栈和出栈的时间复杂度都为O(1),即不依赖栈内数据项的个数，操作比较快
例，使用数组作为栈的存储结构
public class StackS<T> {
private int max;
private T[] ary;
private int top; //指针，指向栈顶元素的下标
public StackS(int size) {
this.max = size;
ary = (T[]) new Object[max];
top = -1;
}
// 入栈
public void push(T data) {
if (!isFull())
ary[++top] = data;
}
// 出栈
public T pop() {
if (isEmpty()) {
return null;
}
return ary[top--];
}
// 查看栈顶
public T peek() {
return ary[top];
}
//栈是否为空
public boolean isEmpty() {
return top == -1;
}
//栈是否满
public boolean isFull() {
return top == max - 1;
}
//size
public int size() {
return top + 1;
}
public static void main(String[] args) {
StackS<Integer> stack = new StackS<Integer>(3);
for (int i = 0; i < 5; i++) {
stack.push(i);
System.out.println("size:" + stack.size());
}
for (int i = 0; i < 5; i++) {
Integer peek = stack.peek();
System.out.println("peek:" + peek);
System.out.println("size:" + stack.size());
}
for (int i = 0; i < 5; i++) {
Integer pop = stack.pop();
System.out.println("pop:" + pop);
System.out.println("size:" + stack.size());
}
System.out.println("----");
for (int i = 5; i > 0; i--) {
stack.push(i);
System.out.println("size:" + stack.size());
}
for (int i = 5; i > 0; i--) {
Integer peek = stack.peek();
System.out.println("peek:" + peek);
System.out.println("size:" + stack.size());
}
for (int i = 5; i > 0; i--) {
Integer pop = stack.pop();
System.out.println("pop:" + pop);
System.out.println("size:" + stack.size());
}
}
}
上面的例子，有一个maxSize的规定，因为数组是要规定大小的，若想无限制，可以使用其他结构来做存储，当然也可以new一个新的长度的数组。
例，使用LinkedList存储来实现栈
public class StackSS<T> {
private LinkedList<T> datas;
public StackSS() {
datas = new LinkedList<T>();
}
// 入栈
public void push(T data) {
datas.addLast(data);
}
// 出栈
public T pop() {
return datas.removeLast();
}
// 查看栈顶
public T peek() {
return datas.getLast();
}
//栈是否为空
public boolean isEmpty() {
return datas.isEmpty();
}
//size
public int size() {
return datas.size();
}
public static void main(String[] args) {
StackS<Integer> stack = new StackS<Integer>(3);
for (int i = 0; i < 5; i++) {
stack.push(i);
System.out.println("size:" + stack.size());
}
for (int i = 0; i < 5; i++) {
Integer peek = stack.peek();
System.out.println("peek:" + peek);
System.out.println("size:" + stack.size());
}
for (int i = 0; i < 5; i++) {
Integer pop = stack.pop();
System.out.println("pop:" + pop);
System.out.println("size:" + stack.size());
}
System.out.println("----");
for (int i = 5; i > 0; i--) {
stack.push(i);
System.out.println("size:" + stack.size());
}
for (int i = 5; i > 0; i--) {
Integer peek = stack.peek();
System.out.println("peek:" + peek);
System.out.println("size:" + stack.size());
}
for (int i = 5; i > 0; i--) {
Integer pop = stack.pop();
System.out.println("pop:" + pop);
System.out.println("size:" + stack.size());
}
}
}
例，单词逆序，使用Statck结构
public class WordReverse {
public static void main(String[] args) {
reverse("株式会社");
}
static void reverse(String word) {
if (word == null) return;
StackSS<Character> stack = new StackSS<Character>();
char[] charArray = word.toCharArray();
int len = charArray.length;
for (int i = 0; i <len; i++ ) {
stack.push(charArray[i]);
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
System.out.println("反转后：" + sb.toString());
}
}
打印：
反转后：社会式株
模拟队列(一般队列、双端队列、优先级队列)
队列：
先进先出，处理类似排队的问题，先排的，先处理，后排的等前面的处理完了，再处理
对于插入和移除操作的时间复杂度都为O(1)，从后面插入，从前面移除
双端队列：
即在队列两端都可以insert和remove：insertLeft、insertRight，removeLeft、removeRight
含有栈和队列的功能，如去掉insertLeft、removeLeft，那就跟栈一样了；如去掉insertLeft、removeRight，那就跟队列一样了
一般使用频率较低，时间复杂度 O(1)
优先级队列：
内部维护一个按优先级排序的序列。插入时需要比较查找插入的位置，时间复杂度O(N)， 删除O(1)
/*
* 队列 先进先出，一个指针指示插入的位置，一个指针指示取出数据项的位置
*/
public class QueueQ<T> {
private int max;
private T[] ary;
private int front; //队头指针 指示取出数据项的位置
private int rear; //队尾指针 指示插入的位置
private int nItems; //实际数据项个数
public QueueQ(int size) {
this.max = size;
ary = (T[]) new Object[max];
front = 0;
rear = -1;
nItems = 0;
}
//插入队尾
public void insert(T t) {
if (rear == max - 1) {//已到实际队尾，从头开始
rear = -1;
}
ary[++rear] = t;
nItems++;
}
//移除队头
public T remove() {
T temp = ary[front++];
if (front == max) {//列队到尾了，从头开始
front = 0;
}
nItems--;
return temp;
}
//查看队头
public T peek() {
return ary[front];
}
public boolean isEmpty() {
return nItems == 0;
}
public boolean isFull() {
return nItems == max;
}
public int size() {
return nItems;
}
public static void main(String[] args) {
QueueQ<Integer> queue = new QueueQ<Integer>(3);
for (int i = 0; i < 5; i++) {
queue.insert(i);
System.out.println("size:" + queue.size());
}
for (int i = 0; i < 5; i++) {
Integer peek = queue.peek();
System.out.println("peek:" + peek);
System.out.println("size:" + queue.size());
}
for (int i = 0; i < 5; i++) {
Integer remove = queue.remove();
System.out.println("remove:" + remove);
System.out.println("size:" + queue.size());
}
System.out.println("----");
for (int i = 5; i > 0; i--) {
queue.insert(i);
System.out.println("size:" + queue.size());
}
for (int i = 5; i > 0; i--) {
Integer peek = queue.peek();
System.out.println("peek:" + peek);
System.out.println("size:" + queue.size());
}
for (int i = 5; i > 0; i--) {
Integer remove = queue.remove();
System.out.println("remove:" + remove);
System.out.println("size:" + queue.size());
}
}
}
/*
* 双端队列<span style="white-space:pre"> </span>两端插入、删除
*/
public class QueueQT<T> {
private LinkedList<T> list;
public QueueQT() {
list = new LinkedList<T>();
}
// 插入队头
public void insertLeft(T t) {
list.addFirst(t);
}
// 插入队尾
public void insertRight(T t) {
list.addLast(t);
}
// 移除队头
public T removeLeft() {
return list.removeFirst();
}
// 移除队尾
public T removeRight() {
return list.removeLast();
}
// 查看队头
public T peekLeft() {
return list.getFirst();
}
// 查看队尾
public T peekRight() {
return list.getLast();
}
public boolean isEmpty() {
return list.isEmpty();
}
public int size() {
return list.size();
}
}
/*
* 优先级队列 队列中按优先级排序，是一个有序的队列
*/
public class QueueQP {
private int max;
private int[] ary;
private int nItems; //实际数据项个数
public QueueQP(int size) {
this.max = size;
ary = new int[max];
nItems = 0;
}
//插入队尾
public void insert(int t) {
int j;
if (nItems == 0) {
ary[nItems++] = t;
} else {
for (j = nItems - 1; j >= 0; j--) {
if (t > ary[j]) {
ary[j + 1] = ary[j]; //前一个赋给后一个 小的在后 相当于用了插入排序，给定序列本来就是有序的，所以效率O(N)
} else {
break;
}
}
ary[j + 1] = t;
nItems++;
}
System.out.println(Arrays.toString(ary));
}
//移除队头
public int remove() {
return ary[--nItems]; //移除优先级小的
}
//查看队尾 优先级最低的
public int peekMin() {
return ary[nItems - 1];
}
public boolean isEmpty() {
return nItems == 0;
}
public boolean isFull() {
return nItems == max;
}
public int size() {
return nItems;
}
public static void main(String[] args) {
QueueQP queue = new QueueQP(3);
queue.insert(1);
queue.insert(2);
queue.insert(3);
int remove = queue.remove();
System.out.println("remove:" + remove);
}
}