1. Implementation stack and queue of double-endian linked list

public static class Node<T> { public T value; public Node<T> last; public Node<T> next; public Node(T data) { value = data; }} public static class DoubleEndsQueue<T> {public Node<T> head; public Node<T> tail; public void addFromHead(T value) { Node<T> cur = new Node<>(value); if (head == null) { head = cur; tail = cur; } else { cur.next = head; head.last = cur; head = cur; } } public void addFromBottom(T value) { Node<T> cur = new Node<>(value); if (head == null) { head = cur; tail = cur; } else { cur.next = tail; tail.last = cur; tail = cur; } } public T popFromHead() { if (head == null) { return null; } Node<T> cur = head; if (head == tail) { head = null; tail = null; } else { head = cur.next; cur.next = null; head.last = null; } return cur.value; } public T popFromBottom() { if (head == null) { return null; } Node<T> cur = tail; if (head == tail) { head = null; tail = null; } else { tail = cur.last; cur.last = null; tail.next = null; } return cur.value; Public static class MyStack<T> {private DoubleEndsQueue<T> queue; public MyStack() { queue = new DoubleEndsQueue<>(); } public void push(T value) {queue.addFromhead (value); } public T pop() {return queue.popfromhead (); Public static class MyQueue<T> {private DoubleEndsQueue<T> queue; public MyQueue() { queue = new DoubleEndsQueue<>(); } public void push(T value) {queue.addFromhead (value); } public T pop() {return queue.popfrombottom (); }}Copy the code

2. Array implementation stack

Public class ArrayStack {private int limit; private int index = 0; private int[] arr = null; public ArrayStack(int limit) { this.limit = limit; arr = new int[limit]; } / / index: Public void push(int value) throws Exception {if (limit == index) {throw new Exception(" Stack is full, No new elements can be added "); } arr[index++] = value; } public int pop() throws Exception {if (index == 0) {throw new Exception(" void "); } return arr[--index]; } public boolean isFull() { return index == limit; } public boolean isEmpty() { return index == 0; } public static void main(String[] args) throws Exception { Random random = new Random(); ArrayStack as = new ArrayStack(7); while (! as.isFull()) { int v = random.nextInt(10); as.push(v); System.out.print(v + "\t"); } System.out.println(); while (! as.isEmpty()) { System.out.print(as.pop() + "\t"); }}}Copy the code

3. Array implementation queue

public static class MyQueue { private int[] arr; private int pushi; private int polli; Private int size; private int size; private int limit; public MyQueue(int limit) { arr = new int[limit]; pushi = 0; polli = 0; size = 0; this.limit = limit; } public void push(int value) throws Exception {if (size == limit) {throw new Exception(" queue is full, cannot be added "); } size++; arr[pushi] = value; pushi = nextIndex(pushi); } public int pop() throws Exception {if (size == 0) {throw new Exception(" the queue is empty, the element cannot be retrieved "); } size--; int ans = arr[polli]; polli = nextIndex(polli); return ans; } private int nextIndex(int index) {return index < limit-1? index + 1 : 0; } public boolean isEmpty() { return size == 0; } public boolean isFull() { return size == limit; } } public static void main(String[] args) throws Exception { Random random = new Random(); MyQueue as = new MyQueue(7); while (! as.isFull()) { int v = random.nextInt(10); as.push(v); System.out.print(v + "\t"); } System.out.println(); while (! as.isEmpty()) { System.out.print(as.pop() + "\t"); }}Copy the code

4. Realize a special stack, on the basis of basic functions, and then realize the function of returning the smallest element in the stack 1) pop, push, getMin operation time complexity is O(1) 2) designed stack type can use the existing stack structure

public class MyStack2 { private Stack<Integer> stackData; private Stack<Integer> stackMin; public MyStack2() { this.stackData = new Stack<>(); this.stackMin = new Stack<>(); } public void push(int newNum) throws Exception { if (stackMin.isEmpty()) { stackMin.push(newNum); } else if (newNum < getMin()) { stackMin.push(newNum); } else { Integer newMin = stackMin.peek(); stackMin.push(newMin); } stackData.push(newNum); } public int pop() throws Exception { if (stackData.isEmpty()) { throw new Exception("stack is empty!" ); } stackMin.pop(); return stackData.pop(); } private int getMin() throws Exception { if (stackMin.isEmpty()) { throw new Exception("stack is empty!" ); } return stackMin.peek(); }}Copy the code