浏览 2086 次
|
锁定老帖子 主题：基本数据结构的说明（二）
该帖已经被评为新手帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-11-05
最后修改：2010-03-15
2.栈和队列
所谓的栈，是一个含有至少两个基本操作的抽象数据类型：插入新的元素；删除最近时间插入的元素。遵循FILO（First in，last out，先进后出）的原则。 所谓的队列，也是一个含有至少两个基本操作的抽象数据类型：插入新的元素；删除最久时间插入的元素。遵循FIFO（First in，first out，先进先出）的原则。 关于栈和队列的具体实现，我们即可以借助于数组，也可以采用链表来实现。 1） 栈的数组实现方式 public class MyStack<E> {
public int count;
public Object [] items;
public boolean isEmpty(){
return count==0;
}
public MyStack (){
items=new Object[20];
count=0;
}
public MyStack (int len){
items=new Object[len];
count=0;
}
/**
重新调整数组的大小
**/
private void resize(int size){
Object [] newItems=new Object[size];
for(int i=0;i<count;i++){
newItems[i]=items[i];
}
items=newItems;
}
public void push(E e){
if(count==items.length) resize(2*items.length);
items[count++]=e;
}
public E pop(){
if(count==0) return null;
E item=(E)items[count-1];
items[count-1]=null;
count--;
if(count>0&&count<=items.length/4) resize(items.length/2);
return item;
}
public E peek(){
if(count==0) return null;
E item=(E)items[count-1];
return item;
}
}
2） 栈的链式实现方式 public class MyStack<E> {
private class Node{
E item;
Node next;
}
Node head;
public boolean isEmpty(){
return head==null;
}
public void push(E t){
Node node=new Node();
node.item=t;
node.next=head;
head=node;
}
public E pop(){
if(head==null)
return null;
E t=head.item;
head=head.next;
return t;
}
public E peek(){
if(head==null)
return null;
else
return head.item;
}
}
3） 队列的数组实现 public class ArrayQueue<E> {
private int front;
private int rear;
private int count;
private int capacity;
private int capacityIncrement;
private Object[] itemArray;
public ArrayQueue(){
front=0;
rear=0;
count=0;
capacity=10;
capacityIncrement=5;
itemArray=new Object[capacity];
}
public boolean empty(){
return count==0;
}
public void insert(E e){
if(count==capacity){
capacity+=capacityIncrement;
Object [] newArray=new Object[capacity];
// for(int i=0;i<count;i++){
// newArray[i]=itemArray[i];
// }
if(front<rear){
//如果元素位于itemArray[front:rear-1]中
for(int i=front;i<rear;i++){
newArray[i]=itemArray[i];
}
}else{
//否则，将元素分成两个区间
//区间1：itemArray[0:rear-1]
for(int i=0;i<rear;i++){
newArray[i]=itemArray[i];
}
//区间2：itemArray[front:count-1]
for(int i=front;i<count;i++){
newArray[i]=itemArray[i];
}
front+=capacityIncrement;//然后，将front改为指向其新位置
}
itemArray=newArray;
}
itemArray[rear]=e;
rear=(rear+1)%capacity;
count++;
}
public E remove(){
if(count==0){
return null;
}
else{
E temp=(E) itemArray[front];
itemArray[front]=null;
front=(front+1)%capacity;
count--;
return temp;
}
}
}
数组的另一种更简单的实现方式： import java.util.NoSuchElementException;
public class ArrayQueue {
protected Object [] data;
protected int size,
head,
tail;
public ArrayQueue(){
final int INITIAL_LENGTH=100;
data=new Object[INITIAL_LENGTH];
size=0;
head=0;
tail=-1;
}
public int size(){
return size;
}
public boolean isEmpty(){
return size==0;
}
public Object front(){
if(size==0)
throw new NoSuchElementException();
return data[head];
}
public void enqueue(Object element){
if(size==data.length){
//double the length of data
Object [] oldData=data;
data=new Object[data.length*2];
//copy oldData[head...OldData.length-1]
//to data[0... OldData.length-1-head]
System.arraycopy(oldData, head,data , 0, oldData.length-head);
if(head>0)
//copy oldData[0...tail] to data [head+1 .. oldlenght-1]
System.arraycopy(oldData, 0, data, head+1, tail+1);
head=0;
tail=oldData.length-1;
}
tail=(tail+1)%data.length;
size++;
data[tail]=element;
}
public Object dequeue(){
if(size--==0){
throw new NoSuchElementException();
}
Object element=data[head];
head=(head+1)%data.length;
return element;
}
}
4） 队列的链式实现方式 public class ListQueue<E> {
private class Node<E>{
E item;
Node<E> link;
}
private Node<E> front,rear;
private int count;
public boolean empty(){
return count==0;
}
public void insert(E e){
//如果队列为空
Node<E> newNode=new Node<E>();
newNode.item=e;
if(rear==null){
front=rear=newNode;
}else{
rear.link=newNode;
rear=newNode;
}
count++;
}
public E remove(){
if(count==0){
return null;
}else{
E e=front.item;
front=front.link;
if(front==null){
rear=null;
}
count--;
return e;
}
}
public ListQueue<E> clone(){
ListQueue<E> Q=new ListQueue<E>();
for(Node<E> t=front;t!=null;t=t.link)
Q.insert(t.item);
return Q;
}
}
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2009-11-05
符号美
|
| 返回顶楼 | |
|
发表时间：2009-11-07
这种内容有必要发到首页上来吗？
|
| 返回顶楼 | |
