【面试题】链表、栈和队列

1.顺序存储结构

顺序存储结构,即数组。优点：节省存储空间，随机存取表中元素；缺点 ：插入和删除操作需要移动元素

顺序存储结构的插入与删除操作代码实现

/** * 顺序链表的插入 * @param data */ public void insert(int data){ if (length >= size){ return; } if (0 == length){ datas[length++] = data; return; } int location = length; for (int i=0;i<length;i++){ if (datas[i] > data){ location = i; break; } } for (int i=length-1;i>=location;i--){ datas[i+1] = datas[i]; } datas[location] = data; length++; } /** * 顺序链表的删除 * @param data */ public void remove(int data){ if (0 == length){ return; } int location = -1; for(int i=0;i<length;i++){ if (datas[i] == data){ location = i; break; } } if (location == -1){ return; } for (int i=location;i<length-1;i++){ datas[i] = datas[i+1]; } length--; }

2.链式存储结构

链式存储结构：用一组任意的存储单元存储线性表的数据元素，分为单链表、双链表、循环链表。逻辑上相邻的节点物理上不必相邻，每个结点是由数据域和指针域组成。

链式存储结构的优点： 插入、删除开销小(不必移动节点，只要改变节点中的指针)。缺点 ：查找结点时链式存储要比顺序存储慢。

2.1 单链表的插入删除、链表逆置、判断有环

/** * 1.插入节点 * @param data 插入值 */ public void insert (int data){ Node node = new Node(data); if (null == this.head){ this.head = node; return; } Node tmp = head; while(tmp.next != null){ tmp = tmp.next; } // 添加新的节点到链表末尾 tmp.next = node; } /** * 2.删除节点 * @param data 删除节点的值 */ public void remove(int data){ if (null == this.head ){ return; } if (this.head.getData() == data){ this.head = this.head.getNext(); return; } Node p = this.head; while(null != p.getNext()){ if (p.getNext().getData() == data){ break; } p = p.getNext(); } if (null != p.getNext()){ p.setNext(p.getNext().getNext()); print(); } } /** * 输出链表元素 */ public void print(){ Node p = this.head; while(null != p){ System.out.print(p.getData()+"->"); p = p.getNext(); } } /** * 3.链表逆序 */ public void reverseLinkList() { if (head == null || head.getNext() == null) { return ; } else { Node temp = null; Node p = head; while (head != null) { p = head.getNext(); head.setNext(temp); temp = head; head = p; } head = temp; } } /** * 4.判断是否为循环链表 * @return 结果 */ public boolean isCircle(){ Node fast = head; Node slow = head; if (head == null || head.getNext() == null){ return false; } while(null != head){ fast = fast.getNext().getNext(); slow = slow.getNext(); if (fast == slow){ break; }else if (fast == null || fast.getNext() == null){ return false; } } return true; }

2.2 双向链表的插入与删除操作

双向链表：每个数据结点中都有两个指针，分别指向直接后继和直接前驱 private Node head; //头插法 public void headinsert (int data){ Node node = new Node(data,null,null); if (null == this.head){ this.head = node; return; } node.setNext(this.head); this.head.setPrior(node); this.head = node; } //尾插法 public void tailinsert(int data){ Node node = new Node(data,null,null); if (null == this.head){ this.head = node; return; } Node p = this.head; while (null != p.getNext()){ p = p.getNext(); } node.setPrior(p); p.setNext(node); } //中间插入法 public void midinsert(int data){ Node node = new Node(data,null,null); if (null == this.head){ this.head = node; return; } if (this.head.getData() > data){ node.setNext(this.head); this.head.setPrior(node); this.head = node; return; } Node p = this.head; while (null != p.getNext()){ if (p.getNext().getData() > data ){ break; } p = p.getNext(); } if (null == p.getNext()) { node.setPrior(p); p.setNext(node); return; } node.setPrior(p); node.setNext(p.getNext()); p.getNext().setPrior(node); p.setNext(node); } //删除操作 public void remove(int data) { if (null == this.head) { System.out.println("链表为空！"); return; } if (this.head.getData() == data) { this.head = this.head.getNext(); print(); return; } Node p = this.head; while (null != p.getNext()) { if (p.getNext().getData() == data) { break; } p = p.getNext(); } if (null == p.getNext()) { System.out.println(data + " 不存在！"); } else { p.setNext(p.getNext().getNext()); if (null != p.getNext()) { p.getNext().setPrior(p); } print(); } }

2.3 循环链表的插入与删除

循环链表：将单链表中终端结点的指针端自空指针改为指向头结点，就使整个单链表形成一个环。 Node head ; Node tail ; //头插法（可变参数） public void headInsert(int... data){ if (null == data || 0 == data.length) { return; } for (int d : data) { Node node = new Node(d,null,null); if (head == null){ head = node; tail = node; continue; } node.setNext(head); head = node; tail.setNext(head); } } //尾插法（可变参数） public void tailInsert(int... data) { if (null == data || 0 == data.length) { return; } for (int d : data) { Node node = new Node(d, null, null); if (head == null) { head = node; this.head.setNext(this.head); tail = node; continue; } Node p = this.head; while (head != p.getNext()) { p = p.getNext(); } node.setPrior(p); p.setNext(node); tail.setNext(head); } } //判断是否为循环链表 public boolean isCircle(){ Node fast = head; Node slow = head; if (head == null || head.getNext() == null){ return false; } while(null != head){ fast = fast.getNext().getNext(); slow = slow.getNext(); if (fast == slow){ break; }else if (fast == null || fast.getNext() == null){ return false; } } return true; } //删除节点 public void remove(int data){ if (null == this.head ){ System.out.println("链表为空！"); return; } if (this.head.getData() == data){ this.head = this.head.getNext(); this.tail.setNext(head); return; } Node p = this.head; while(head != p.getNext()){ if (p.getNext().getData() == data){ break; } p = p.getNext(); } if (head != p.getNext()){ p.setNext(p.getNext().getNext()); }else{ System.out.println(data + " 不存在！"); } }

3.栈

栈是后进先出的线性表（LIFO表），仅在表的一端进行插入和删除运算的线性表。通常称插入、删除的这一端为栈顶，另一端称为栈底。

用栈实现链表

private Node head; private int size = 0; //入栈 public void push (int data) { Node node = new Node(data, null); if (null == this.head) { this.head = node; size++; return; } else { node.setNext(head); head = node; } size++; } //出栈 public void pop(){ if (size == 0) { System.out.println("队列为空！"); return; } Node temp = head; head = head.getNext(); size--; System.out.println(temp.getData()); } //判断栈是否为空 public boolean isEmpty(){ if (head == null) { return true; } return false; }

4.队列

Queue是只允许在一端进行插入操作，而在另-端进行删除操作的先进先出线性表（FIFO）。允许插入的一端称为队尾，允许删除的一端称为队头。

循环队列

public class LoopQueue<T> { private int DEFAULT_SIZE = 10; private int capacity;//保存数组的长度 private Object[] elementData;//定义一个数组用于保存循环队列的元素 private int front = 0;//队头 private int rear = 0;//队尾 //以默认数组长度创建空循环队列 public LoopQueue() { capacity = DEFAULT_SIZE; elementData = new Object[capacity]; } //以一个初始化元素来创建循环队列 public LoopQueue(T element) { this(); elementData[0] = element; rear++; } //以指定循环队列中第一个元素和指定长度的数组来创建循环队列 public LoopQueue(T element, int initSize) { this.capacity = initSize; elementData = new Object[capacity]; elementData[0] = element; rear++; } //获取循环队列的大小 public int size() { if (isEmpty()) { return 0; } return rear > front ? rear - front : capacity - (front - rear); } //插入队列 public void add(T element) { if (rear == front && elementData[front] != null) { throw new IndexOutOfBoundsException("队列已满的异常"); } elementData[rear++] = element; //如果rear已经到头，那就转头 rear = rear == capacity ? 0 : rear; } //移除队列 public T remove() { if (isEmpty()) { throw new IndexOutOfBoundsException("空队列异常"); } //保留队列的rear端的元素的值 T oldValue = (T) elementData[front]; //释放队列的front端的元素 elementData[front++] = null; //如果front已经到头，那就转头 front = front == capacity ? 0 : front; return oldValue; } //返回队列顶元素，但不删除队列顶元素 public T element() { if (isEmpty()) { throw new IndexOutOfBoundsException("空队列异常"); } return (T) elementData[front]; } //判断循环队列是否为空队列 public boolean isEmpty() { //rear==front且rear处的元素为null return rear == front && elementData[rear] == null; } //清空循环队列 public void clear() { //将底层数组所有元素赋为null Arrays.fill(elementData, null); front = 0; rear = 0; } public String toString() { if (isEmpty()) { return "[]"; } else { //如果front < rear，有效元素就是front到rear之间的元素 if (front < rear) { StringBuilder sb = new StringBuilder("["); for (int i = front; i < rear; i++) { sb.append(elementData[i].toString() + ", "); } int len = sb.length(); return sb.delete(len - 2, len).append("]").toString(); } //如果front >= rear，有效元素为front->capacity之间、0->rear之间的 else { StringBuilder sb = new StringBuilder("["); for (int i = front; i < capacity; i++) { sb.append(elementData[i].toString() + ", "); } for (int i = 0; i < rear; i++) { sb.append(elementData[i].toString() + ", "); } int len = sb.length(); return sb.delete(len - 2, len).append("]").toString(); } } } public static void main(String[] args) { LoopQueue<String> queue = new LoopQueue<String>("aaaa", 3); //添加两个元素 queue.add("bbbb"); queue.add("cccc"); //此时队列已满 System.out.println(queue); //删除一个元素后，队列可以再多加一个元素 queue.remove(); System.out.println("删除一个元素后的队列：" + queue); //再次添加一个元素，此时队列又满 queue.add("dddd"); System.out.println(queue); System.out.println("队列满时的长度：" + queue.size()); } }

本人才疏学浅，若有错，请指出，谢谢！ 如果你有更好的建议，可以留言我们一起讨论，共同进步！ 衷心的感谢您能耐心的读完本篇博文！