怎么分析Java数据结构中的栈与队列(java,开发技术)

一，栈

1，概念

在我们软件应用 ，栈这种后进先出数据结构的应用是非常普遍的。比如你用浏 览器上网时不管什么浏览器都有 个"后退"键，你点击后可以接访问顺序的逆序加载浏览过的网页。

很多类似的软件，比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的操作，也是用栈这种方式来实现的，当然不同的软件具体实现会有很大差异，不过原理其实都是一样的。

栈( stack )是限定仅在表尾进行插入和删除的线性表

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

2，栈的操作

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

3，栈的实现

①入栈

publicstaticvoidmain(String[]args){Stack<Integer>stack=newStack<>();stack.push(1);stack.push(2);stack.push(3);stack.push(4);intret=stack.push(4);System.out.println(ret);}

②出栈

publicstaticvoidmain(String[]args){Stack<Integer>stack=newStack<>();stack.push(1);stack.push(2);stack.push(3);intret1=stack.pop();intret2=stack.pop();System.out.println(ret1);System.out.println(ret2);}

③获取栈顶元素

publicstaticvoidmain(String[]args){Stack<Integer>stack=newStack<>();stack.push(1);stack.push(2);stack.push(3);intret1=stack.pop();intret2=stack.pop();intret3=stack.peek();System.out.println(ret1);System.out.println(ret2);System.out.println(ret3);}

④判断栈是否为空

publicstaticvoidmain(String[]args){Stack<Integer>stack=newStack<>();stack.push(1);stack.push(2);stack.push(3);intret1=stack.pop();intret2=stack.pop();intret3=stack.peek();System.out.println(ret1);System.out.println(ret2);System.out.println(ret3);stack.pop();booleanflag=stack.empty();System.out.println(flag);}

4，实现mystack

publicclassMyStack<T>{privateT[]elem;//数组privateinttop;//当前可以存放数据元素的下标-》栈顶指针publicMyStack(){this.elem=(T[])newObject[10];}/***入栈操作*@paramitem入栈的元素*/publicvoidpush(Titem){//1、判断当前栈是否是满的if(isFull()){this.elem=Arrays.copyOf(this.elem,2*this.elem.length);}//2、elem[top]=itemtop++;this.elem[this.top++]=item;}publicbooleanisFull(){returnthis.elem.length==this.top;}/***出栈*@return出栈的元素*/publicTpop(){if(empty()){thrownewUnsupportedOperationException("栈为空！");}Tret=this.elem[this.top-1];this.top--;//真正的改变了top的值returnret;}/***得到栈顶元素，但是不删除*@return*/publicTpeek(){if(empty()){thrownewUnsupportedOperationException("栈为空！");}//this.top--;//真正的改变了top的值returnthis.elem[this.top-1];}publicbooleanempty(){returnthis.top==0;}}

publicstaticvoidmain(String[]args){MyStack<Integer>myStack=newMyStack<>();myStack.push(1);myStack.push(2);myStack.push(3);System.out.println(myStack.peek());System.out.println(myStack.pop());System.out.println(myStack.pop());System.out.println(myStack.pop());System.out.println(myStack.empty());System.out.println("============================");MyStack<String>myStack2=newMyStack<>();myStack2.push("hello");myStack2.push("word");myStack2.push("thank");System.out.println(myStack2.peek());System.out.println(myStack2.pop());System.out.println(myStack2.pop());System.out.println(myStack2.pop());System.out.println(myStack2.empty());}

二，队列

1，概念

像移动、联通、电信等客服电话，客服人员与客户相比总是少数，在所有的客服人员都占线的情况下，客户会被要求等待，直到有某个客服人员空下来，才能让最先等待的客户接通电话。这里也是将所有当前拨打客服电话的客户进行了排队处理。

操作系统和客服系统中，都是应用了种数据结构来实现刚才提到的先进先出的排队功能，这就是队列。

队列(queue) 是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头 （Head/Front）

2，队列的实现

①入队

publicstaticvoidmain(String[]args){Deque<Integer>queue=newLinkedList<>();queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);}

②出队

publicstaticvoidmain(String[]args){Deque<Integer>queue=newLinkedList<>();queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);System.out.println(queue.poll());System.out.println(queue.poll());}

③获取队首元素

publicstaticvoidmain(String[]args){Deque<Integer>queue=newLinkedList<>();queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);System.out.println(queue.poll());System.out.println(queue.poll());System.out.println("-----------------");System.out.println(queue.peek());}

3，实现myqueue

classNode{privateintval;privateNodenext;publicintgetVal(){returnval;}publicvoidsetVal(intval){this.val=val;}publicNodegetNext(){returnnext;}publicvoidsetNext(Nodenext){this.next=next;}publicNode(intval){this.val=val;}}publicclassMyQueue{privateNodefirst;privateNodelast;//入队publicvoidoffer(intval){//尾插法需要判断是不是第一次插入Nodenode=newNode(val);if(this.first==null){this.first=node;this.last=node;}else{this.last.setNext(node);//last.next=node;this.last=node;}}//出队publicintpoll(){//1判断是否为空的if(isEmpty()){thrownewUnsupportedOperationException("队列为空！");}//this.first=this.first.next;intret=this.first.getVal();this.first=this.first.getNext();returnret;}//得到队头元素但是不删除publicintpeek(){//不要移动firstif(isEmpty()){thrownewUnsupportedOperationException("队列为空！");}returnthis.first.getVal();}//队列是否为空publicbooleanisEmpty(){returnthis.first==null;}}

publicstaticvoidmain(String[]args){MyQueuemyQueue=newMyQueue();myQueue.offer(1);myQueue.offer(2);myQueue.offer(3);System.out.println(myQueue.peek());System.out.println(myQueue.poll());System.out.println(myQueue.poll());System.out.println(myQueue.poll());System.out.println(myQueue.isEmpty());}