每篇笔记都会附上随书的Applet演示程序,有算法看不明白的,可以下载Applet运行起来(直接打开html文件即可),可以很容易地看清楚算法的每一步。
栈
栈是一种先进后出(FILO)的线性数据结构,先进后出的意思就是……举个例子吧,我先把1放进一个栈里,再把2放进去,最后把3放进去,取出来的时候只能先得到3,再取能得到2,最后是1。栈一次只允许访问一个数据项(最顶端的那个),常用操作有入栈(push,把数据压入栈里)和出栈(pop,把顶端的数据从栈里弹出),peek用于查看栈顶数据。
下面是一个简单的栈的实现
package dsaa.array;
import java.util.EmptyStackException;
/**
* @(#)Stack.java 2008-12-26 下午03:41:57
*
* @author Qiu Maoyuan
* Stack
*/
public class Stack<E> {
private Object[] stackArray;
private int topIndex = -1;
private int size = 0;
public Stack(){
stackArray = new Object[10];
}
public Stack(int size){
stackArray = new Object[size];
}
public void push(E value){
ensureCapacity();
stackArray[++topIndex] = value;
size++;
}
@SuppressWarnings("unchecked")
public E peek(){
if(topIndex==-1)
throw new EmptyStackException();
return (E)stackArray[topIndex];
}
public E pop(){
E value = peek();
topIndex--;
size--;
return value;
}
public boolean isEmpty(){
return size==0;
}
private void ensureCapacity() {
if(size==stackArray.length){
Object[] newArray = new Object[size * 3 / 2 + 1];
System.arraycopy(stackArray, 0, newArray, 0, size);
stackArray = newArray;
}
}
}
在给一个数组或者字符串进行反向排序的时候,栈是一个不错的工具:
Stack<Character> stack = new Stack<Character>();
String input = "hello stack!";
for(int i=0; i<input.length(); i++)
stack.push(input.charAt(i));
StringBuilder buffer = new StringBuilder();
while(!stack.isEmpty()){
buffer.append(stack.pop().charValue());
}
String output = buffer.toString();
System.out.println(output);
利用栈还可以实现回文判断、词法分析等功能。
显而易见,栈的push和pop操作的时间复杂度为O(1)。
队列
队列是一种先进先出(FIFO)的线性数据结构,常用操作有插入(insert)和删除(remove)。
一个简单的队列实现如下:
package dsaa.array;
/**
* @(#)Queue.java 2008-12-27 上午01:21:46
*
* @author Qiu Maoyuan
* Queue
*/
public class Queue<E> {
private Object[] queueArray;
private int head = 0;
private int tail = -1;
public Queue(int size){
queueArray = new Object[size];
}
@SuppressWarnings("unchecked")
public E peek(){
if(isEmpty())
throw new IllegalStateException("Queue is empty");
return (E)queueArray[head];
}
public void insert(E value){
if(isFull())
throw new IllegalStateException("Queue is full");
queueArray[++tail] = value;
}
public E remove(){
E value = peek();
head++;
return value;
}
public boolean isEmpty(){
return tail - head == -1;
}
public boolean isFull(){
return tail == queueArray.length-1;
}
}
以上队列存在一个问题,队列满了以后,无论删除掉多少个数据项,甚至清空这个队列,仍然不能插入新的数据。其实有一种解决方法就是,在删除数据项的时候,后面的所有数据项都往前移动,但这样效率很低。
为了避免队列不满却不能插入新数据项的问题,可以让队头队尾指针绕回到数组开始的位置,这样的队列叫
循环队列。
改进后的代码如下:
package dsaa.array;
/**
* @(#)Queue.java 2008-12-27 上午01:21:46
*
* @author Qiu Maoyuan
* Queue
*/
public class Queue<E> {
private Object[] queueArray;
private int head = 0;
private int tail = -1;
private int elementsCount = 0;
public Queue(int size){
queueArray = new Object[size];
}
@SuppressWarnings("unchecked")
public E peek(){
if(isEmpty())
throw new IllegalStateException("Queue is empty");
return (E)queueArray[head];
}
public void insert(E value){
if(isFull())
throw new IllegalStateException("Queue is full");
if(tail == queueArray.length - 1){
tail = 0;
queueArray[tail] = value;
}else{
queueArray[++tail] = value;
}
elementsCount++;
}
public E remove(){
E value = peek();
if(head == queueArray.length - 1){
head = 0;
}else{
head++;
}
elementsCount--;
return value;
}
public boolean isEmpty(){
return elementsCount == 0;
}
public boolean isFull(){
return elementsCount == queueArray.length;
}
}
队列的效率和栈一样,插入和删除数据项的时间复杂度均为O(1)。
还有一种队列叫做
双端队列,顾名思义就是对两端都可以进行插入、删除操作的队列。如果封闭了其中一端,它就变成了一个栈;如果只允许一端插入,另一端删除,那它就成了一个普通队列。
优先级队列和普通队列的不同之处是:它在插入数据时是有序的。所以优先级队列的插入效率会比较低,时间复杂度为O(N),删除操作则为O(1)。
package dsaa.array;
/**
* @(#)PriorityQueue.java 2008-12-27 下午01:03:01
*
* @author Qiu Maoyuan
* Priority Queue
*/
public class PriorityQueue {
private int[] queueArray;
private int head = -1;
public PriorityQueue(int initialCapacity){
queueArray = new int[initialCapacity];
}
public void insert(int value){
if(isFull())
throw new IllegalStateException("Queue is full");
if (isEmpty()){
queueArray[++head] = value;
} else {
int i=head;
while (i>-1){
if (queueArray[i]>value){
queueArray[i + 1] = queueArray[i];
} else {
break;
}
i--;
}
queueArray[i + 1] = value;
head++;
}
}
public boolean isFull(){
return head == queueArray.length - 1;
}
public boolean isEmpty(){
return head == -1;
}
public int remove(){
int value = peek();
head--;
return value;
}
public int peek(){
if(isEmpty())
throw new IllegalStateException("Queue is empty");
return queueArray[head];
}
}
分享到:
相关推荐
中软国际培训的学习笔记,很值得参考。学习java数据结构很有必要看看
Java数据结构和算法学习笔记,对于爱好Java人员来说,再好不过了
这是我从B站上看韩老师讲的数据结构与算法后整理的笔记 代码经过运行,欢迎批评指正 有些地方我感觉还是挺难的 大都经过我自己的语言进行描述,韩老师中期的表达可能或多或少也影响可阅读性,望先生们见谅
Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
适用于计算机类专业学生,试验报告
sgg数据结构和算法笔记
Java数据结构与算法学习笔记之排序 冒泡排序,选择排序,插入排序,希尔排序, 归并排序, 快速排序.
Java数据结构和算法 第0讲 综述 参考教材:Java数据结构和算法(第二版),[美] Robert lafore 1. 数据结构的特性 "数据结构"优点 "缺点 " "数组 "插入快;如果知道下标,可以非常快"查找慢,删除慢,大小固定" " ...
数据结构、算法与应用——C++语言描述.rar
包含了各种数据结构和算法(java)的实现方式和详解(图解),包括单双链表、环形链表(约瑟夫问题)、栈、后缀表达式、中缀表达式转后缀表达式、迷宫问题、八大排序算法、多种查找算法、哈希表、二叉树实现以及操作...
JAVA数据结构与算法课程第05课双端链表和双向链表.mp4JAVA数据结构与算法课程第06课递归的应用.mp4JAVA数据结构与算法课程第07课递归的高级应用.mp4JAVA数据结构与算法课程第08课希尔排序.mp4JAVA数据结构与算法课程...
《数据结构与算法》以基本数据结构和算法设计策略为知识单元,系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法,主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。《数据结构...
内含 笔记+课件+代码+资料 ,资源齐全,想学java数据结构与算法的推荐下载,课程很不错,对于初学者或者需要后补数据结构算法的很合适
数据结构与算法 Python语言描述-裘宗燕 高清带目录 详细讲述线性表 、字符串、栈和队列、二叉树和树、图、字典和集合、排序等
Java数据结构和算法介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、...
NULL 博文链接:https://yuan.iteye.com/blog/304808