重温数据结构和算法 Stack & Queue 2019-03-07 FILO & FIFO StackBasedLinkedList123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354package stack;/** * @Author: Leooel * @Date: 2019/3/7 8:52 */public class StackBasedLinkedList { private Node top = null; public void push(int value) { Node newNode = new Node(value); if (top == null) { top = newNode; } else { newNode.next = top; top = newNode; } } // 返回 -1 代表栈中无元素 public int pop() { if (top == null) { return -1; } int value = top.data; top = top.next; return value; } public void printAll() { Node p = top; while (p != null) { System.out.print(p.data + " "); p = p.next; } System.out.println(); } public static class Node { private int data; private Node next; public Node(int data) { this.data = data; } }} QueueBasedDynamicArray12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364package queue;/** * @Author: Leooel * @Date: 2019/3/7 20:29 */public class QueueBasedDynamicArray { // 数组 items,大小为 n private String[] items; private int n = 0; private int head = 0; private int tail = 0; public QueueBasedDynamicArray(int capacity) { this.items = new String[capacity]; this.n = capacity; } public boolean enqueue(String item) { // 队列末尾没有空间 if (tail == n) { if (head == 0) return false; // 数据搬移 for (int i = head; i < tail; ++i) { items[i - head] = items[i]; } // 更新 head、tail,注意语句顺序 tail -= head; head = 0; } items[tail] = item; tail++; return true; } public String dequeue() { if (head == tail) return null; String ret = items[head]; head++; return ret; } public void printAll() { for (int i = head; i < tail; ++i) { System.out.print(items[i] + " "); } System.out.println(); } public static void main(String[] args) { QueueBasedDynamicArray object = new QueueBasedDynamicArray(4); object.enqueue("1"); object.enqueue("2"); object.enqueue("3"); object.enqueue("4"); object.dequeue(); object.enqueue("5"); object.printAll(); }} CircularQueueBasedArray123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354package queue;/** * @Author: Leooel * @Date: 2019/3/7 9:49 */public class CircularQueueBasedArray { // 数组 items, 大小为 n private String items[]; private int n = 0; private int head = 0; private int tail = 0; public CircularQueueBasedArray(int capacity) { this.items = new String[capacity]; this.n = capacity; } public boolean enqueue(String item) { // 队满 if ((tail + 1) % n == head) return false; items[tail] = item; tail = (tail + 1) % n; return true; } public String dequeue() { // 队空 if (head == tail) return null; String ret = items[head]; head = (head + 1) % n; return ret; } public void printAll() { if (n == 0) return; for (int i = head; i % n != tail; ++i) { System.out.print(items[i] + " "); } System.out.println(); } public static void main(String[] args) { CircularQueueBasedArray object = new CircularQueueBasedArray(15); object.enqueue("Leo"); object.enqueue("oel"); object.dequeue(); object.printAll(); }} QueueBasedLinkedList1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162package queue;/** * @Author: Leooel * @Date: 2019/3/7 20:55 */public class QueueBasedLinkedList { private Node head = null; private Node tail = null; public void enqueue(String value) { Node res = new Node(value); if (tail == null) { head = res; tail = res; } else { tail.next = res; tail = tail.next; } } public String dequeue() { if (head == null) return null; String ret = head.data; head = head.next; if (head == null) { tail = null; } return ret; } public void printAll() { Node p = head; while (p != null) { System.out.print(p.data + " "); p = p.next; } System.out.println(); } public static class Node { private String data; private Node next; public Node(String value) { this.data = value; } } public static void main(String[] args) { QueueBasedLinkedList object = new QueueBasedLinkedList(); object.enqueue("1"); object.enqueue("2"); object.enqueue("3"); object.dequeue(); object.printAll(); }} 赏 谢谢你请Leo吃糖果哦 支付宝 微信 数据结构与算法 扫一扫,分享到微信