详解栈和队列

目录：

1.栈

2.队列

一、 栈（Stack）

1.1 概念：

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作。进行插入元素的一端叫做栈顶，另一端叫做栈底。从数据结构的角度出发，栈中的元素遵循先进后出的原则。

1.2 栈的内在方法：

Stack()：

Stack的构造方法，用来创建一个栈类型的对象。

由于栈是一个泛型类，所以在创建对象时可以传入类型实参以规定栈中存储的数据类型。

Stack stack1 = new Stack();Stack<Integer> stack2 = new Stack<>();

push(E)：

入栈，并且返回该元素的值。

public static void main(String[] args) {Stack<Integer> stack = new Stack<>();System.out.println(stack.push(1));}//运行结果：1

如果使用了<>,就必须放规定类型的数据；如果没有用<>，可以往栈中存入任意类型的数据。 

pop()：

出栈，并返回该元素的值。

public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(1);System.out.println(stack.pop());}//运行结果：1

如果空栈进行出栈，则会抛出异常。

peek()：

仅返回栈顶元素的值。

public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(1);System.out.println(stack.peek());}//运行结果：1

如果对空栈进行peek，就会抛出异常。

empty()：

返回该栈是否为空。

        Stack<Integer> stack = new Stack<>();stack.push(1);System.out.println(stack.empty());//运行结果：falseStack<Integer> stack = new Stack<>();System.out.println(stack.empty());//运行结果：true

 1.3 模拟实现栈：

链栈：

用链表实现栈。

如果链表采用尾插的话，push的时间复杂度为O(1),pop的时间复杂度为O(N);

如果链表采用首插的话，push的时间复杂度为O(1),pop的时间复杂度为O(1)，所以采用首插。

public class List_stack {ListNode head;static class ListNode{ListNode next;int a;}public void push(ListNode l) {if (l == null) {return;}l.next = head;head = l;}public ListNode pop(){ListNode k = head;try {if (head == null) {throw new EmptyException();}head = head.next;}catch (EmptyException o){o.printStackTrace();}return k;}public ListNode peek() {return head;}public boolean isEmpty() {return head == null;}
}

顺序栈：

用顺序表实现栈。

如果顺序表采用尾插的话，push的时间复杂度为O(1),pop的时间复杂度为O(1);

如果顺序表采用首插的话，push的时间复杂度为O(N),pop的时间复杂度为O(N)，所以采用尾插。

public class MyStack {public int[] elem;public int usedSize;public MyStack(int[] elem) {this.elem = new int[10];}public void push(int date) {if (isFull()) {elem = Arrays.copyOf(elem, 2 * usedSize);}elem[usedSize++] = date;}public boolean isFull() {return usedSize == elem.length;}public int pop() {try {if (isEmpty()){throw new EmptyException("栈为空");}}catch (EmptyException e) {e.printStackTrace();}return elem[--usedSize];}public int peek() {try {if (isEmpty()){throw new EmptyException("栈为空");}}catch (EmptyException e) {e.printStackTrace();}return elem[usedSize - 1];}public boolean isEmpty() {return usedSize == 0;}
}

二、 队列（Queue）

1.1 概念：

队列是只允许在一端进行插入数据，在另一端删除数据的特殊线性表，具有先进先出（FIFO）的特点。

与栈有所不同，队列在Java中是一个接口，以链表为底层实现的。

1.2 队列的内在方法：

add(E)：

将指定元素添加到队列中

• 如果元素成功添加，始终返回 true（对于没有容量限制的队列）。如果无法添加元素，该方法会抛出异常。

offer(E)：

尝试立即将指定元素添加到队列中，前提是不违反容量限制。

• 成功添加元素则返回 true。
• 由于容量限制无法添加元素则返回 false。

remove()：

检索并移除队列的头部元素，返回队列的头部元素。

poll()：

检索并移除队列的头部元素。

• 返回队列的头部元素，若队列为空则返回 null。

element()：

检索但不移除队列的头部元素，返回队列的头部元素。

peek()：

检索但不移除队列的头部元素。

• 返回队列的头部元素，若队列为空则返回 null。

总结

• 添加元素：使用 offer() 处理容量受限的队列，使用 add() 处理没有容量限制的队列。
• 移除元素：使用 poll() 安全地移除元素，若队列为空则返回 null，使用 remove() 在队列为空时抛出异常。
• 查看元素：使用 peek() 安全地查看队列头部元素，若队列为空则返回 null，使用 element() 在队列为空时抛出异常。

1.3 模拟实现队列：

public class MyQueue {static class ListNode{ListNode prev;ListNode next;int val;public ListNode(int val) {this.val = val;}}ListNode first;ListNode last;public void offer(int val) {ListNode cur = new ListNode(val);if (first == null) {last = cur;first = cur;}else {last.next = cur;cur.prev = last;last = last.next;}}public int poll() {if (isEmpty()) {return -1;}int k = first.val;first = first.next;if (first != null) {first.prev = null;}return k;}public int peek() {if (isEmpty()) {return -1;}return first.val;}public boolean isEmpty() {return first == null;}
}

1.4 循环队列：

循环队列一般是数组实现的，有两个难点：

1. 怎么使下标循环；

（index + 1）% elem.length就是走一步。

2. 怎么判断元素放满了。

有三种方法：1. 使用一个变量进行标记；

                      2. 使用size来储存数据的个数与数组长度进行对比；

                      3. 浪费一个空间，当pos2走一步之后判断是否等于pos1。 

public class CirQueue {int first;int last;int[] elem;public CirQueue() {elem = new int[8];}public void push(int val) {if (isFull()) {return;}elem[last % 8] = val;last++;}public int pop() {if (isEmpty()) {return -1;}int k = elem[first];first = (first + 1) % 8;return k;}public int peek() {if (isEmpty()) {return -1;}return elem[first];}public boolean isEmpty() {return last == first;}public boolean isFull() {return (last + 1) % 8 == first;}
}

 1.5 双端队列（Deque）：

1.6 用队列实现栈：

一个队列是不能实现的，所以我们需要两个，如果我们要删除最后进入的数据，我们需要先将上面的元素出队并且存入另一个队列中，最后才能将队尾元素删除或检索。

public class Q_stack {Queue<Integer> queue1;Queue<Integer> queue2;public Q_stack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {if (empty()) {queue1.offer(x);}else if (!queue2.isEmpty()) {queue2.offer(x);}else {queue1.offer(x);}}public int pop() {if (empty()) {return -1;}else if (!queue2.isEmpty()) {for (int i = 0; i < queue2.size() + queue1.size() - 1; i++) {queue1.offer(queue2.poll());}return queue2.remove();}else {for (int i = 0; i < queue1.size() + queue2.size() - 1; i++) {queue2.offer(queue1.poll());}return queue1.remove();}}public int top() {int k = 0;if (empty()) {return -1;}else if (!queue2.isEmpty()) {for (int i = 0; i < queue2.size() + queue1.size(); i++) {k = queue2.element();queue1.offer(queue2.poll());}return k;}else {for (int i = 0; i < queue1.size() + queue2.size(); i++) {k = queue1.element();queue2.offer(queue1.poll());}return k;}}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}
}

1.7 用栈实现队列：

把stack1作为存放数据的栈，把stack2作为操作数据的栈，当stack2为空时将stack1中的数据转移到stack2。

public class S_queue {Stack<Integer> stack1;Stack<Integer> stack2;public S_queue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int val) {stack1.push(val);}public int pop() {if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean isEmpty() {return stack1.isEmpty() && stack2.isEmpty();}
}