栈的理论描述
栈是一个有序线性表，只能在表的一端（成为栈顶，top）执行插入和删除操作。最后插入的元素将第一个被删除。所以栈也称为后进先出（Last In First Out）或先进后出（First In Last Out）线性表。栈主要有两个操作，一个入栈（push），表示在栈中插入一个元素，一个出栈（pop），表示将栈顶元素删除。试图对空栈执行出栈操作称为UnderFlow，对满栈执行入栈操作称为OverFlow。
栈的抽象数据结构
栈的主要操作：
- void push(int data):将data插入栈
- int pop():删除并返回最后一个插入栈的元素
栈的辅助操作
- int top():返回最后一个插入栈的元素
- int size():返回存储在栈中元素的个数
- int isEmpty():判断栈中是否有元素
- int StackFull():判断栈中是否存满元素
异常
pop和top操作在栈空的时候是不能操作的。试图对空栈执行pop和top会抛出异常。试图对满栈执行push操作也会抛出异常。
代码实现
栈抽象数据结构有多种实现方式：
- 基于简单数组的实现方法
- 基于动态数组的实现方法
- 基于链表的实现方法
简单数组：
public class DynArrayStack {
private int top;
private int capacity;
private int[] array;
public DynArrayStack(){
capacity = 1;
array = new int[capacity];
top = -1;
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isStackFull() {
return (top == capacity -1);
}
public void push(int data) {
if (isStackFull()) {
System.out.println("Stack overflow!");
}else {
array[++top] = data;
}
}
public int pop() {
if (isEmpty()) {
System.out.println("Stack is empty!");
return 0;
}else {
return array[top--];
}
}
}
动态数组的实现方法大致一样，只是比上面的多了当到达数组最大容量的时候将容量扩大到现有的一倍。
private void doubleSize(){
int newArray[] = new int[capacity << 1];
System.arraycopy(array, 0, newArray, 0, capacity);
capacity = capacity << 1;
array = newArray;
}
public void push(int data) {
if (isStackFull()) {
doubleSize();
}else {
array[++top] = data;
}
}
链表的栈实现方式：
public class LLStack {
private LinkedNode headNode;
public LLStack(){}
public void push(int data) {
if (headNode == null) {
headNode = new LinkedNode(data);
}else if (headNode.getData() == null) {
headNode.setData(data);
}else {
LinkedNode node = new LinkedNode(data);
node.setNext(headNode);
headNode = node;
}
}
public int pop(){
if (headNode == null) {
throw new EmptyStackException("Stack Empty");
}
int data = headNode.getData();
headNode = headNode.getNext();
return data;
}
public int top(){
return headNode == null ? null : headNode.getData();
}
public boolean isEmpty(){
return headNode == null || headNode.getData() == null;
}
}
各种实现方式的比较：
基于数组实现的栈：
- 各个操作都是常数时间开销
- 每隔一段时间倍增的开销教大
- n个操作的任意序列的平摊时间开销为O(n)
基于链表实现的栈：
- 栈规模增加减少都很简洁
- 各个操作都是常数时间开销
- 每个操作都要使用额外的时间和空间开销来处理指针
应用
- IDE和编译器中符号匹配
- 中缀表达式转换为后缀表达式
- 实现函数调用（包括递归）
栈的相关问题
eg：计算跨度：给定数组A，A[i]的跨度S[i]定义为：满足A[j]<=
A[j+1]而且在A[i]前的连续元素A[j]的最大个数。如图
/* time:O(n), space:(n) */
public int[] findingSpans(int[] inputArray) {
int[] spans = new int[inputArray.length];
Stack<Integer> stack = new Stack();
int p;
for (int i = 0; i < inputArray.length; i++) {
while (!stack.isEmpty() && inputArray[i] > inputArray[stack.pop()]) {
stack.pop();
}
if (stack.isEmpty()) {
p = -1;
}else {
p = stack.top();
}
spans[i] = i - p;
stack.push(i);
}
return spans;
}
eg:设计一个可以把栈中元素按照升序排列的排序算法，并且不能限定栈的实现方法。
/* time:O(n^2) , space:O(n) */
public Stack<Integer> sort(Stack<Integer> s) {
Stack<Integer> r = new Stack<>();
while (!s.isEmpty()) {
int temp = s.pop();
while (!r.isEmpty() && r.peek() > temp) {
s.push(r.pop());
}
r.push(temp);
}
return r;
}
eg：删除所有相邻的重复元素：给定一个数字数组，删除相邻的重复数字，结果数组中不能有任何相邻的重复数字。
| input | 1, 5, 6, 8, 8, 0, 1, 1, 0, 6, 5 |
|---|---|
| optput | 1 |
/* space:O(n) , time:O(n) */
public int removeAdjacentDuplicates(int[] a){
int stkptr = -1;
int i = 0;
while (i < a.length) {
if (stkptr == -1 || a[stkptr] != a[i]) {
stkptr++;
a[stkptr] = a[i];
}else {
while (i < a.length && a[stkptr] == a[i]) {
i++;
}
stkptr--;
}
}
return stkptr;
}
队列的理论描述
定义：队列是一种只能在一端插入（队尾），在另一端（队首）的有序线性表。队列中第一个插入就是第一个被删除的元素。所以队列是一种先进先出（FIFO,first in first out）或者后进后出（LILO,last in last out）线性表。
队列的抽象数据结构
队列的主要操作：
- void enQueue(int data):将data插入队列
- int deQueue():删除并返回队首的元素
栈的辅助操作
- int front():返回队首元素
- int size():返回存储在队列中元素的个数
- int isEmpty():判断队列中是否存储了元素
异常
- 队空时异常（执行deQueue操作）
- 队满时异常（执行enQueue操作）
代码实现
基于循环数组
为什么需要循环数组？由队列定义，在一端插入，一端删除。 当执行多次插入和删除操作后，就可以容易地发现数组靠前位置的空间被浪费了，所以基于简单数组实现队列不是一个靠谱的方法。循环数组刚好可以用来解决这个问题
public class DynArrayQueue {
private int front;
private int rear;
private int capacity;
private int[] array;
public DynArrayQueue(){
capacity = 1;
front = rear = -1;
array = new int[capacity];
}
public boolean isEmpty() {
return front == -1;
}
public boolean isFull() {
return (rear + 1) % capacity == front;
}
public int getSize() {
if (front == -1) {
return 0;
}
int size = (capacity + rear + 1 - front);
if (size == 0) {
return capacity;
}else {
return size;
}
}
public void resizeQueue() {
int initCapacity = capacity;
capacity *= 2;
int[] old = array;
array = new intp[capacity];
for (int i = 0; i < old.length; i++) {
array[i] = old[i];
}
if (front > rear) {
for (int i = 0; i < front; i++) {
array[i + capacity] = array[i];
array[i] = null;
}
rear += initCapacity;
}
}
public void enQueue(int data) {
if (isFull()) {
resizeQueue();
}
rear = (rear + 1) % capacity;
array[rear] = data;
if (front == -1) {
front = rear;
}
}
public int deQueue(){
int data = null;
if (isEmpty()) {
throw new EmptyQueueException("Queue is empty");
}else {
data = array[front];
if (front == rear) {
front = rear = -1;
}else {
front = (front + 1) % capacity;
}
}
return data;
}
}
基于动态循环数组
基于上面的理解，循环数组其实还是有个问题，就是当分配给数组的个数到达最大值的时候，再插入元素就会溢出，所以有了动态循环数组。
public class DynArrayQueue {
private int front;
private int rear;
private int capacity;
private int[] array;
public DynArrayQueue(){
capacity = 1;
front = rear = -1;
array = new int[capacity];
}
public boolean isEmpty() {
return front == -1;
}
public boolean isFull() {
return (rear + 1) % capacity == front;
}
public int getSize() {
return ((capacity - front + rear + 1)%capacity);
}
public void enQueue(int data) {
if (isFull()) {
throw new QueueOverFlowException("queue overflow");
}
rear = (rear + 1) % capacity;
array[rear] = data;
if (front == -1) {
front = rear;
}
}
public int deQueue(){
int data = null;
if (isEmpty()) {
throw new EmptyQueueException("Queue is empty");
}else {
data = array[front];
if (front == rear) {
front = rear = -1;
}else {
front = (front + 1) % capacity;
}
}
return data;
}
}
基于链表
public class LLQueue {
private LinkedListNode<Integer> frontNode;
private LinkedListNode<Integer> rearNode;
public boolean isEmpty() {
return frontNode == null;
}
public void enQueue(int data){
LinkedListNode newNode = new LinkedListNode(data);
if (rearNode != null) {
rearNode.setNext(newNode);
}else {
frontNode = rearNode = newNode;
}
}
public int deQueue() {
int data;
if (isEmpty()) {
throw new EmptyQueueEmptyException("Queue Empty");
}
data = frontNode.getData();
frontNode = frontNode.getNext();
return data;
}
}
链表和数组的对比和栈是一样的区别：链表需要花费指针这些额外的空间，但是操作和思路都很简便。
应用
- 操作系统根据任务到达的顺序调度任务（如打印队列）
- 模拟现实世界中的队列
- 多道程序设计
- 异步数据传输
队列的相关问题
eg：如果需要反向输出队列中元素，应该用什么数据结构？
答：
public Queue<Integer> reverseQueue(Queue<Integer> queue){
Stack stack = new Stack<Integer>();
while(!queue.isEmpty(){
stack.push(queue.deQueue());
}
while(!stack.isEmpty()){
queue.enQueue(stack.poll());
}
return queue;
}
eg：用两个队列实现一个栈的数据结构接口。
解答：
public class StackWithTwoQueues {
LLQueue queue1;
LLQueue queue2;
public StackWithTwoQueues(){
queue1 = new LLQueue();
queue2 = new LLQueue();
}
public void push(int data) {
if (queue1.isEmpty()) {
queue2.enQueue(data);
}else {
queue1.enQueue(data);
}
}
public int pop(){
int i, size, value;
i = 0;
if (queue1.isEmpty()) {
size = queue2.getSize();
while (i < size -1) {
queue1.enQueue(queue2.deQueue());
i++;
}
value = queue2.deQueue();
}else {
size = queue1.getSize();
while (i < size -1) {
queue2.enQueue(queue1.deQueue());
i++;
}
value = queue1.deQueue();
}
return 0;
}
}
eg：给定一个整数栈，如何检查栈中每队相邻数字是否是连续的。每对数字的值可以是递增或递减的。如果栈中元素的个数是奇数，那么组队时忽略栈顶元素。例如，假设栈中元素为[4,5,-2,-3,11,10,5,6,20]，那算法应该输出真，因为每对二元组(4,5),(-2,-3),(11,10)和(5,6)都是连续数字。
解答：
public boolean checkStackPairwiseOrder(Stack<Integer> s) {
boolean pairwiseOrder = true;
LLQueue queue = new LLQueue();
while (!s.isEmpty()) {
queue.enQueue(s.pop());
}
while (!queue.isEmpty()) {
s.push(queue.enQueue());
}
while (!s.isEmpty()) {
int n = s.pop();
if (!s.isEmpty()) {
int m = s.pop();
queue.add(m);
if (Math.abs(n - m) != 1) {
pairwiseOrder = false;
break;
}
}
}
return pairwiseOrder;
}
eg：给定一个整数k和一个整数队列，如何把队列中前k个元素逆置，其余的元素保持不变？例如，如果k等于4，队列中元素序列为[10,20,30,40,50,60,70,80,90]，那么应该输出[40,30,20,10,50,60,70,80,90]。
解答:
public void reverseQueueFirstKElements(int k, Queue<Integer> q) {
if (q == null || k > q.getSize()) {
throw new IllegalArgumentException();
}
if (k > 0) {
Stack<Integer> stack = new Stack<Integer>();
for(int i=0;i<k;i++){
stack.push(q.remove());
}
while(!stack.isEmpty()){
q.add(stack.pop());
}
for (int i = 0; i < q.size() - k; i++) {
q.add(q.remove());
}
}
}
