用java实现常用数据结构栈和队列.

Question

如题.
要求:
1.使用继承.先构造线性链表.将其扩展为队列和栈.
2.要求结点能存放任意类对象.
3.使用抽象类或接口,使得使用方通过接口访问栈和队列,体现接口的多态性意义.首先声明,这个是老师布置的大作业,发到这里是因为讲数据结构的时候没有听课,数据结构懂的很少.希望各位能够就栈,队列,线性链表做些解释,另外就是给一个做这个作业的思路,不胜感激.
再声明一下,我不是要来抄作业的.因为数据结构的问题,以及没有真正做过这类大作业的经验,所以,请各位能讲下数据结构方面的问题,另外是思路.

Answer 1

有一个电子版的书：java数据结构与算法，你看看就知道了

Answer 2

CSDN解决作业问题：很好，很强大！

Answer 3

到rt.jar看java.util.Stack和java.util.Queue的源代码，里面都写了实现方法，用vector实现的。

Answer 4

你安装的jdk目录下的rt.jar。晕，你什么教材啊，不可能没说吧。

Answer 5

package datastructure;public abstract class MyList<E> {
protected int size = 0;

protected MyList() {
}

abstract public boolean add(E o);
abstract public E get(int index);
abstract public boolean contains(E o);
abstract int indexOf(E o);
abstract public boolean remove(E o);
abstract public void clear();

public final int size() {
return this.size;
    }

public final boolean isEmpty() {
return this.size == 0;
}
}

Answer 6

package datastructure;public interface MyQueue<E> {
void enqueue(E o);
E dequeue();
boolean isEmpty();
}

Answer 7

package datastructure;public interface MyStack<E> {
void push(E o);
E pop();
boolean isEmpty();
}

Answer 8

package datastructure;public class MyLinkedList<E> extends MyList<E> implements MyQueue<E>, MyStack<E> { private static class MyEntry<E> {
E element;
MyEntry<E> next;
MyEntry<E> previous; MyEntry(E element, MyEntry<E> next, MyEntry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
} private MyEntry<E> header = new MyEntry<E>(null, null, null); public MyLinkedList() {
this.header.next = this.header.previous = this.header;
} public boolean add(E o) {
this.addBefore(o, header);
return true;
} public void clear() {
MyEntry<E> e = this.header.next;
while (e != this.header) {
MyEntry<E> next = e.next;
e.next = e.previous = null;
e.element = null;
e = next;
}
this.header.next = this.header.previous = this.header;
this.size = 0;
} public boolean contains(E o) {
return this.indexOf(o) != -1;
} public E get(int index) {
MyEntry<E> myEntry = this.entry(index);
if (myEntry == null)
return null;
return myEntry.element;
} int indexOf(E o) {
int index = 0;
if (o == null) {
for (MyEntry e = this.header.next; e != this.header; e = e.next) {
if (e.element == null)
return index;
index++;
}
} else {
for (MyEntry e = this.header.next; e != this.header; e = e.next) {
if (o.equals(e.element))
return index;
index++;
}
}
return -1;
} public boolean remove(E o) {
if (o == null) {
for (MyEntry<E> e = header.next; e != header; e = e.next) {
if (e.element == null) {
return this.remove(e);
}
}
} else {
for (MyEntry<E> e = header.next; e != header; e = e.next) {
if (o.equals(e.element)) {
return this.remove(e);
}
}
}
return false;
} public E dequeue() {
E result = this.header.next.element;
this.remove(this.header.next);
return result;
} public void enqueue(E o) {
this.addBefore(o, header);
} public E pop() {
E result = this.header.previous.element;
this.remove(this.header.previous);
return result;
} public void push(E o) {
this.addBefore(o, header);
} private MyEntry<E> addBefore(E o, MyEntry<E> e) {
MyEntry<E> newEntry = new MyEntry<E>(o, e, e.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
this.size++;
return newEntry;
} private boolean remove(MyEntry<E> e) {
if (e == header) {
return false;
}
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = null;
e.element = null;
this.size--;
return true;
} private MyEntry<E> entry(int index) {
if (index < 0 || index >= this.size) {
return null;
}
MyEntry<E> e = header;
if (index < (this.size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = this.size; i > index; i--)
e = e.previous;
}
return e;
}
}

Answer 9

package datastructure;public final class MyTester {
public static void main(String[] args) {
MyQueue<String> myQueue = new MyLinkedList<String>();
myQueue.enqueue("Hello1");
myQueue.enqueue("Hello2");
while(!myQueue.isEmpty()) {
System.out.println(myQueue.dequeue());
}
MyStack<String> myStack = new MyLinkedList<String>();
myStack.push("1234567890");
myStack.push("0987654321");
while(!myStack.isEmpty()) {
System.out.println(myStack.pop());
}
}
}

Answer 10

不负责任的copy上jdk 5.0栈的实现。
队列只是一个接口，实现类很多，包括LinkedList。甚至还有子接口。
/*
 * @(#)Stack.java 1.28 03/12/19
 *
 * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */package java.util;/**
 * The <code>Stack</code> class represents a last-in-first-out 
 * (LIFO) stack of objects. It extends class <tt>Vector</tt> with five 
 * operations that allow a vector to be treated as a stack. The usual 
 * <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a
 * method to <tt>peek</tt> at the top item on the stack, a method to test 
 * for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt> 
 * the stack for an item and discover how far it is from the top.
 * <p>
 * When a stack is first created, it contains no items. 
 *
 * @author  Jonathan Payne
 * @version 1.28, 12/19/03
 * @since   JDK1.0
 */
public
class Stack<E> extends Vector<E> {
    /**
     * Creates an empty Stack.
     */
    public Stack() {
    }    /**
     * Pushes an item onto the top of this stack. This has exactly 
     * the same effect as:
     * <blockquote><pre>
     * addElement(item)</pre></blockquote>
     *
     * @param   item   the item to be pushed onto this stack.
     * @return  the <code>item</code> argument.
     * @see     java.util.Vector#addElement
     */
    public E push(E item) {
addElement(item); return item;
    }    /**
     * Removes the object at the top of this stack and returns that 
     * object as the value of this function. 
     *
     * @return     The object at the top of this stack (the last item 
     *             of the <tt>Vector</tt> object).
     * @exception  EmptyStackException  if this stack is empty.
     */
    public synchronized E pop() {
E obj;
int len = size(); obj = peek();
removeElementAt(len - 1); return obj;
    }    /**
     * Looks at the object at the top of this stack without removing it 
     * from the stack. 
     *
     * @return     the object at the top of this stack (the last item 
     *             of the <tt>Vector</tt> object). 
     * @exception  EmptyStackException  if this stack is empty.
     */
    public synchronized E peek() {
int len = size(); if (len == 0)
    throw new EmptyStackException();
return elementAt(len - 1);
    }    /**
     * Tests if this stack is empty.
     *
     * @return  <code>true</code> if and only if this stack contains 
     *          no items; <code>false</code> otherwise.
     */
    public boolean empty() {
return size() == 0;
    }    /**
     * Returns the 1-based position where an object is on this stack. 
     * If the object <tt>o</tt> occurs as an item in this stack, this 
     * method returns the distance from the top of the stack of the 
     * occurrence nearest the top of the stack; the topmost item on the 
     * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt> 
     * method is used to compare <tt>o</tt> to the 
     * items in this stack.
     *
     * @param   o   the desired object.
     * @return  the 1-based position from the top of the stack where 
     *          the object is located; the return value <code>-1</code>
     *          indicates that the object is not on the stack.
     */
    public synchronized int search(Object o) {
int i = lastIndexOf(o); if (i >= 0) {
    return size() - i;
}
return -1;
    }    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}

Answer 11

class LinkedList {    //定义双向链表类
char data;
LinkedList forward;
LinkedList back;
}
interface Access {    //定义从队列和栈存钱操作的接口
void put(char c);
char get();
}
class Queue implements Access {  //定义队列类
private LinkedList QHead=new LinkedList();
private LinkedList QRear=QHead;  //初始化队头和队尾
public void put(char c){   //定义向队列寸数的方法
QRear.forward=new LinkedList();
QRear.forward.data=c;
QRear.forward.back=QRear;
QRear=QRear.forward;
}
public char get(){   //实现从队列取数的方法
if(QHead!=QRear){   //如果队列不为空则取数
QHead.forward.back=null;
QHead=QHead.forward;
return QHead.data;
}
else{
System.out.println("The queue is empty!");
return '\0';
}
}
}
class Stack implements Access {   //定义栈类
private LinkedList bottom=new LinkedList();
private LinkedList top=bottom;   //初始化栈顶和栈底
public void put(char c){   //定义向栈中存数的方法
top.forward=new LinkedList();
top.forward.data=c;
top.forward.back=top;
top=top.forward;
}
public char get(){   //实现从栈中取数的方法
if(top!=bottom){   //如果栈不为空则取数
char ch=top.data;
top.back.forward=null;
top=top.back;
return ch;
}
else{
System.out.println("The stack is empty!");
return '\0';
}
}
}
public class StackQueue { /**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
         char ch;
         Access q=new Queue(); //创建队列的实例
         Access s=new Stack(); //创建栈的实例
         q.put('a');
         q.put('b');
         q.put('c');
         q.put('d');
         s.put('a');
         s.put('b');
         s.put('c');
         s.put('d');
         System.out.println("The queue is:");
         if((ch=q.get())!='\0')
          System.out.print(ch);
         if((ch=q.get())!='\0')
          System.out.print(ch);
         if((ch=q.get())!='\0')
          System.out.print(ch);
         if((ch=q.get())!='\0')
          System.out.println(ch);
         if((ch=q.get())!='\0')
          System.out.println(ch);
         System.out.println();
         System.out.println("The stack is:");
         if((ch=s.get())!='\0')
          System.out.print(ch);
         if((ch=s.get())!='\0')
          System.out.print(ch);
         if((ch=s.get())!='\0')
          System.out.print(ch);
         if((ch=s.get())!='\0')
          System.out.println(ch);
         if((ch=s.get())!='\0')
          System.out.println(ch);
}}

Answer 12

找本java 数据结构的书看看基本差不多，你们老师出题挺好的