数据结构上机实验1.doc

数据结构上机一目的： Stack and Queue 是最为简单的数据结构，然而它在一些重要的应用中是极为基本的。本次实验将练习Stack and Queue的一些操作，通过本次实验熟悉Stack and Queue。步骤：1 仅使用Stack类中的构造函数、push()、peek（）、pop()、以及empty()等方法编写以下方法： Public Stack reversed (Stack stack，int maxSize);/返回一个新栈，该栈中包含了原指定栈中的内容，但内容的次序与原栈正好相反。2仅使用Stack类中的构造函数、push()、peek（）、pop()、以及empty()等方法编写以下方法：Public int popbottom(Stack stack，int maxSize)；/返回栈底的元素，并将该元素从栈中移出3仅使用ArrayQueue类中的构造函数、enqueue()、dequeue（）、以及empty()等方法编写以下方法： Puplic static ArrayQueue merge (ArrayQueue q1, ArrayQueue q2，int num);/将两个队列合并到一起，合并的方式为交替使用两队列中的元素，并把剩余的队列中的元素添加到最后，并将合并产生的新队列返回答案：/Stack.javaclass Stack private int maxSize; / size of stack array private long stackArray; private int top; / top of stack/- public Stack(int s) / constructor maxSize = s; / set array size stackArray = new longmaxSize; / create array top = -1; / no items yet /- public void push(long j) / put item on top of stack stackArray+top = j; / increment top, insert item /- public long pop() / take item from top of stack return stackArraytop-; / access item, decrement top /- public long peek() / peek at top of stack return stackArraytop; /- public boolean isEmpty() / true if stack is empty return (top = -1); /- public boolean isFull() / true if stack is full return (top = maxSize-1); /- public Stack reversed(Stack stack,int maxSize) Stack a=new Stack(maxSize); while(!stack.isEmpty() a.push(stack.pop(); return a; /- public long popbottom(Stack stack ,int maxSize) Stack a=new Stack(maxSize); while(!stack.isEmpty() a.push(stack.pop(); long temp=a.pop(); while(!a.isEmpty() stack.push(a.pop(); return temp; / end class StackX/class StackApp public static void main(String args) Stack theStack = new Stack(10); / make new stack theStack.push(20); / push items onto stack theStack.push(40); theStack.push(60); theStack.push(80); System.out.println(theStack.popbottom(theStack, 10); while( !theStack.isEmpty() ) / until its empty, / delete item from stack long value = theStack.pop(); System.out.print(value); / display it System.out.print( ); / end while System.out.println(); /Stack newStack=(Stack)theStack.reversed(theStack, 10); / end while / end main() / end class StackApp/class ArrayQueue private int maxSize; private long queArray; private int front; private int rear; private int nItems;/- public ArrayQueue(int s) / constructor maxSize = s; queArray = new longmaxSize; front = 0; rear = -1; nItems = 0; /- public void enqueue(long j) / put item at rear of queue if(rear = maxSize-1) / deal with wraparound rear = -1; queArray+rear = j; / increment rear and insert nItems+; / one more item /- public long dequeue() / take item from front of queue long temp = queArrayfront+; / get value and incr front if(front = maxSize) / deal with wraparound front = 0; nItems-; / one less item return temp; /- public long peekFront() / peek at front of queue return queArrayfront; /- public boolean isEmpty() / true if queue is empty return (nItems=0); /- public boolean isFull() / true if queue is full return (nItems=maxSize); /- public int size() / number of items in queue return nItems; /- static ArrayQueue c; public static ArrayQueue merge (ArrayQueue q1, ArrayQueue q2 ,int num) ArrayQueue c=new ArrayQueue(num); while(!q1.isEmpty()&!q2.isEmpty() c.enqueue(q1.dequeue();c.enqueue(q2.dequeue(); if(q1.isEmpty() while(!q2.isEmpty()c.enqueue(q2.dequeue(); else while(!q1.isEmpty()c.enqueue(q1.dequeue(); return c; / class QueueApp public static void main(String args) ArrayQueue theQueue1 = new ArrayQueue(5); / queue holds 5 items ArrayQueue theQueue2 = new ArrayQueue(5); theQueue1.enqueue(10); / insert 4 items theQueue1.enqueue(20); theQueue1.enqueue(30); theQueue1.enqueue(40); theQueue1.dequeue(); / remove 3 items theQueue1.dequeue(); / (10, 20, 30) theQueue1.dequeue(); theQueue1.enqueue(50); / insert 4 more items theQueue1.enqueue(60); / (wraps around) theQueue1.enqueue(70); theQueue1.enqueue(80); theQueue2.enqueue(11); / insert 4 items theQueue2.enqueue(23); theQueue2.enqueue(36); theQueue2.enqueue(90); ArrayQueue newQueue = new ArrayQueue(10); newQueue=(ArrayQueue)newQueue.merge(theQ