数据结构基础_栈和队列
来聊聊栈和队列，和数组比较栈和队列有插入数据迅速的优势，但是在查找数据时就没有数组来的快了。下面的代码实现了用数组实现栈，用链表实现队列以及用链表实现栈。
用数组实现栈
package StackAndQueue;/** * 使用数组实现栈 * @author wly * @author 2013-10-23 */public class ArrayStack {Object[] array;int init_capcity = 12;int INCREATE_STEP = 12; //数组放满数据时的扩展步长int top = -1;public ArrayStack() {array = new Object[init_capcity];}public void push(Object obj) {if(top >= array.length) { //如果数组对象已经没有空位,扩展数组对象Object[] array2 = new Object[array.length + INCREATE_STEP];for(int i=0;i<array.length;i++) {array2[i] = array[i];}array = array2;}//不管数组是否已经满了，都需要进行压栈动作top ++;array[top] = obj;}/** * 弹出栈顶元素 * @return */public Object pop() {if(top >= 0) { //判断栈中是否还有未弹出元素Object topElement = array[top];top --;return topElement;} else {return null;}}/** * 得到栈顶元素，不弹出 * @return */public Object peek() {Object topElement = array[top];return topElement;}}用链表实现栈
package StackAndQueue;/** * 使用链表实现栈，相对于数组实现，链表无需关心数组是否已经被装满的问题 * @author wly * @date 2013-10-23 */public class ChainStack {Chain chain;public void push(Node node) {if(chain == null) {chain = new Chain();}chain.add(node);}public Node pop() { return chain.remove();}public Node peek() {return chain.tail;}}/** * 链表类 * @author wly * */class Chain {Node tail;public void add(Node node) {if(tail == null) {tail = node;} else {tail.setNext(node);tail = node;}}/** * 移除队尾元素，注意判断链表是否为空 * @return true 移除成功,false 移除失败 */public Node remove() {Node result = tail;if(tail.prev != null) { tail = tail.prev;tail.next = null;} else { //只剩一个元素tail = null;}return result;}}/** * 节点类 * @author wly * */class Node {public Node next; //持有下一个节点的引用public Node prev; //持有上一节点的引用public Object data;public Node(Object data) {this.data = data;}public void setNext(Node node) {node.prev = this;this.next = node;}}用链表实现队列
package StackAndQueue;/** * 使用链表实现队列 * @author wly * */public class ChainQueue {private QueueNode head; //指向队列头节点private QueueNode tail; //指向队列尾节点private int size = 0;public ChainQueue() {}/** * 插入新节点到队列尾 */public void insert(QueueNode node) {//#######下面是一种错误的写法######//错误的原在于head.prev为null，导致了在remove或peek时引用head.prev时包空指针异常//if(head == null) {//head = node;//tail = head;//} else {//node.next = tail;//tail = node;//}//if(isEmpty()){//tail = node;//head = tail;////if(tail == head) {//System.out.println("--same--");//}//} else {//tail.prev = node;//tail = node;//}//当然也可以这么写,添加tail.prev = nodeif(head == null) {head = node;tail = head;} else {node.next = tail;tail.prev = node; //双向连接，确保head.prev不为空tail = node;}size ++;}/** * 移除队列首节点 */public QueueNode remove() {if(!isEmpty()) {QueueNode temp = head;head = head.prev;size --;return temp;} else {System.out.println("异常操作，当前队列为空!");return null;}}/** * 队列是否为空 * @return */public boolean isEmpty() {if(size > 0) {return false;} else {return true;}}/** * 返回队列首节点，但不移除 */public QueueNode peek() {if(!isEmpty()) {return head;} else {System.out.println();System.out.println("异常操作，当前队列为空!");return null;}}/** * 返回队列大小 * @return */public int size() {return size;}}/** * 节点类 * @author wly * */class QueueNode {QueueNode prev;QueueNode next;int data;public QueueNode(int data) {this.data = data;}public int getData() {return data;}public void setData(int data) {this.data = data;}}测试一下
package StackAndQueue;public class Test {public static void main(String[] args) {//-----测试用数组实现的栈-------System.out.println("-----测试用数组实现的栈");ArrayStack arrayStack = new ArrayStack();arrayStack.push("苹果");arrayStack.push("梨子");System.out.println(arrayStack.pop().toString()); //超人System.out.println(arrayStack.peek().toString()); //咸蛋System.out.println(arrayStack.pop().toString()); //咸蛋System.out.println("--------------\n");//-----测试用链表实现的栈--------System.out.println("-----测试用链表实现的栈");ChainStack chainStack = new ChainStack();Node n1 = new Node("舒克");Node n2 = new Node("贝塔");chainStack.push(n1);chainStack.push(n2);System.out.println(chainStack.pop().data.toString());System.out.println(chainStack.peek().data.toString());System.out.println(chainStack.pop().data.toString());System.out.println("--------------\n");//-----测试用链表实现的队列--------System.out.println("-----测试用链表实现的队列");QueueNode qnode1 = new QueueNode(123);QueueNode qnode2 = new QueueNode(666);ChainQueue chainQueue = new ChainQueue();chainQueue.insert(qnode1);chainQueue.insert(qnode2);System.out.println(chainQueue.remove().getData());System.out.println(chainQueue.peek().getData());System.out.println(chainQueue.remove().getData());System.out.println("--------------\n");//最后，容本菜鸟伤感一下~~~//本菜鸟亲身经历的一个面试题，惭愧的当时根本没有看过数据结构(本人电信专业)，后来用ArrayList做出来的，惭愧~~~//现在看了数据结构，再用正确的方法解一下。//题目是这样的：输入一个正整数n，生成一个1 2 3 4 ... n的数列，要求弹出第一个，再将第二个移动到数列尾//如此循环直到数列只剩一个数，并求这个数在队列中的原来位置是多少？ChainQueue chainQueue2 = new ChainQueue();for(int i=1;i<=5;i++) {QueueNode qn = new QueueNode(i);chainQueue2.insert(qn);}while(chainQueue2.size() > 1) {chainQueue2.remove();if(chainQueue2.size() > 1) {chainQueue2.insert(chainQueue2.remove());} else {//得到结果System.out.println("悲伤的分割线------:");System.out.print(chainQueue2.peek().getData());}}}}最后再扯一下那次面试，本人还是很重视的，面试前做了很多准备(主要是被什么外资公司，全英文工作环境给搞的有点紧张了，什么英语口语介绍，英语常见面试题一通背)。到了现场感觉还好，因为有读英语文档的习惯，所以面试官用英语问的问题基本都听懂了，但是自己用英语表述时还是有不顺畅的(之后回来意识到英语真的很重要，于是现在在努力学英语)。后来的机试题，就是前文代码中的那个用队列实现的题目。因为根本没有看过数据结构这本书(之后，发现自己基础很薄弱，所以现在除了工作之外，就安排时间在看数据结构和算法)。后来用ArrayList花了20分钟左右的时间做好了，可能面试官考的就是数据结构吧，因为我没有自己写队列，于是他就问了我一些程序调试和代码规范的问题。都一一回答了，但是感觉还算不错(因为之前已经有一个hr的电话面试，和一个技术的电话面试，都还不错)。然后又来一个项目经理，于是我终于知道这是一家外包公司啊，然后他问我是不是只做过Android，又强调因为是外包所以以后可能有什么做什么，需要什么学什么，这时我犹豫了一下，，，还是不扯了，总之，后来没面上。可能是觉得我基础不好，要求的薪资又不低吧。不过我觉得我尽力了(那天5点一下班就赶火车从宁波到杭州，然后再转车，再转车，晚上9点半到的宾馆，洗完澡后又看了会英语，哎。。。)
不过还是有所收获的啊，下面总结几点给要找工作的新人一点参考哈。
一、除非你自己确实牛(做了很牛的开源项目，ACM一等奖之类的，已经名声在外了)，否则主动打电话过来找你的一般都不是什么好公司。
二、如果你刚毕业，什么都不会的话，去小公司也可以，做的多，学的快。如果你已经有一定的水平了(写了10万行左右的代码了)，那么就去大公司吧，大公司有很多规范的东西值得学习。
三、不要想着公司主动给你加工资，如果你真的很在意工资的话，就努力提高自己吧。到你觉得你的水平应该得到更高的报酬时，一般公司都会给你加的，如若不然。你大可以跳槽，掌握主动权。
O啦~~~
转载请保留出处：http://blog.csdn.net/u011638883/article/details/14107863
谢谢!!