基礎(chǔ)知識
棧
棧（stack）又名堆棧晒奕，它是一種運算受限的線性表匾效。其限制是僅允許在表的一端進行插入和刪除運算。
棧是一種后進先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)翠储。
隊列
隊列是一種特殊的線性表爆哑，特殊之處在于它只允許在表的前端（front）進行刪除操作洞难，而在表的后端（rear）進行插入操作，和棧一樣揭朝，隊列是一種操作受限制的線性表队贱。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭萝勤。
隊列是一種先進先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)露筒。
制定手寫方案
如果我們要手寫一個椖派。或者隊列敌卓，先要確定用什么數(shù)據(jù)結(jié)構(gòu)保存數(shù)據(jù)，需要實現(xiàn)哪些功能伶氢？
選取數(shù)據(jù)結(jié)構(gòu)
為了更好的理解棧和隊列的原理趟径，盡量采用簡單的數(shù)據(jù)結(jié)構(gòu)來保存數(shù)據(jù)，這樣實現(xiàn)的邏輯會變得簡單易懂癣防，所以本次采用的是數(shù)組蜗巧。
實現(xiàn)哪些功能
對于棧：
- 入棧和出棧
- 獲取棧頂元素但不刪除此元素
- 獲取棧是否為空的方法
- 獲取棧大小的方法
對于隊列：
- 進隊列和出隊列
- 獲取隊列頭元素但不刪除此元素
- 獲取隊列是否為空的方法
- 獲取隊列大小的方法
使用數(shù)組實現(xiàn)棧：
import java.util.Arrays;
import java.util.EmptyStackException;
class Stack<E> {
private E[] _data; // 數(shù)據(jù)
private int _size; // 數(shù)組長度
private int _realLength; // 數(shù)組已用長度
@SuppressWarnings("unchecked")
public Stack(int initSize) {
this._size = initSize;
this._data = (E[]) new Object[initSize];
this._realLength = 0;
}
/**
* 默認數(shù)組長度為20
*/
public Stack() {
this(20);
}
/**
* 入棧
*
* @param element 添加的元素
*/
public void push(E element) {
if (size() >= _size) {
grow();
}
_data[_realLength++] = element;
}
/**
* 出棧
*
* @return 返回棧頂?shù)脑? */
public E pop() {
if (size() < 1) {
throw new EmptyStackException();
}
E top = _data[_realLength - 1];
_data[--_realLength] = null;
return top;
}
/**
* 獲取棧頂元素
*
* @return 返回的是棧頂元素
*/
public E peek() {
if (size() < 1) {
throw new EmptyStackException();
}
return _data[_realLength - 1];
}
/**
* 判斷棧是否為空棧
*
* @return true代表空棧
*/
public boolean isEmpty() {
return _realLength == 0;
}
/**
* 棧的大小
*
* @return 大小值
*/
public int size() {
return _realLength;
}
/**
* 數(shù)組的擴容，擴容大小為原先的2倍
*/
private void grow() {
// 擴容后size也要變化
_size = _size * 2;
_data = Arrays.copyOf(_data, _size);
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>(1);
stack.push(0);
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("stack is empty: " + stack.isEmpty());
System.out.println("stack size is: " + stack.size());
System.out.println("stack pop is: " + stack.pop());
System.out.println("stack top is: " + stack.peek());
// stack is empty: false
// stack size is: 4
// stack pop is: 3
// stack top is: 2
}
}
需要注意的幾個點：
- 數(shù)組的擴容蕾盯，做法是每次擴容原先長度的2倍
- 出棧后數(shù)組的變更幕屹，元素出棧后需要將之前的元素置空，便于
GC - 對數(shù)組越界問題的把握，只要涉及到獲取元素的操作望拖，都需要對下標(biāo)進行是否越界判斷渺尘，可以返回
null，也可以直接拋出異常说敏，具體看個人
使用數(shù)組實現(xiàn)隊列：
import java.util.Arrays;
import java.util.NoSuchElementException;
/**
* FIFO
*/
class Queue<E> {
private E[] _data;
private int _realLength;
private int _size;
@SuppressWarnings("unchecked")
public Queue(int initSize) {
this._data = (E[]) new Object[initSize];
this._size = initSize;
this._realLength = 0;
}
/**
* 默認數(shù)組長度為20
*/
public Queue() {
this(20);
}
/**
* 向隊列尾端添加元素
*
* @param element 元素
*/
public void offer(E element) {
if (size() >= _size) {
grow();
}
_data[_realLength++] = element;
}
/**
* 取出隊列頭元素鸥跟，并且從隊列中刪除它
*
* @return 頭元素
*/
public E poll() {
if (isEmpty()) {
throw new NoSuchElementException("queue is empty");
}
E first = _data[0];
_data = Arrays.copyOfRange(_data, 1, _size);
_realLength--;
return first;
}
/**
* 取出隊列頭元素，但是不刪除它
*
* @return 頭元素
*/
public E element() {
if (isEmpty()) {
throw new NoSuchElementException("queue is empty");
}
return _data[0];
}
/**
* 判斷隊列是否為空
*
* @return true代表空隊列
*/
public boolean isEmpty() {
return _realLength == 0;
}
/**
* 隊列的大小
*
* @return 大小值
*/
public int size() {
return _realLength;
}
/**
* 數(shù)組的擴容盔沫，擴容大小為原先的2倍
*/
private void grow() {
// 擴容后size也要變化
_size = _size * 2;
_data = Arrays.copyOf(_data, _size);
}
public static void main(String[] args) {
Queue<Integer> queue = new Queue<Integer>();
queue.offer(0);
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println("queue is empty: " + queue.isEmpty());
System.out.println("queue size is: " + queue.size());
System.out.println("queue poll: " + queue.poll());
System.out.println("queue poll: " + queue.poll());
System.out.println("queue poll: " + queue.poll());
System.out.println("queue poll: " + queue.poll());
// queue is empty: false
// queue size is: 4
// queue poll: 0
// queue poll: 1
// queue poll: 2
// queue poll: 3
}
}
使用數(shù)組來實現(xiàn)隊列相比較棧更加的容易医咨，添加元素、判空和 size() 兩者都相似架诞，只是在出隊列的時候做法與出棧不相同而已拟淮，出隊列出的是頭部元素，也就是最先添加的元素侈贷，出隊列之后需要重新調(diào)整數(shù)組惩歉，使用系統(tǒng)提供的 Arrays.copyOfRange(_data, 1, _size) 可輕松的復(fù)制數(shù)組一段元素。
手寫棧和隊列不僅可以用數(shù)組來實現(xiàn)俏蛮，也可以用鏈表來實現(xiàn)撑蚌，用鏈表可以可以更好的控制添加和刪除操作，畢竟鏈表采用的是指針方案搏屑。有興趣的可以自行實現(xiàn)一波争涌。
如果本文章你發(fā)現(xiàn)有不正確或者不足之處，歡迎你在下方留言或者掃描下方的二維碼留言也可辣恋！
