详解栈和队列

1.栈

2.队列

一、栈（Stack）

1.1 概念：

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

1.2 栈的内在方法：

Stack()：

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

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

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

push(E)：

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

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

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

pop()：

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

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

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

peek()：

仅返回栈顶元素的值。

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

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

empty()：

返回该栈是否为空。

java">        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)，所以采用首插。

java">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)，所以采用尾插。

java">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 模拟实现队列：

java">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。

java">
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 用队列实现栈：

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

java">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。

java">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();}
}