前言：題圖無關(guān)靴患，只是好看芽偏，接下來就來復(fù)習(xí)一下棧和隊(duì)列的相關(guān)知識
前序文章：
- 數(shù)據(jù)結(jié)構(gòu)與算法(1)——數(shù)組與鏈表（http://www.reibang.com/p/7b93b3570875）
棧
什么是棧
棧是一種用于存儲數(shù)據(jù)的簡單數(shù)據(jù)結(jié)構(gòu)（與鏈表類似）恶座。數(shù)據(jù)入棧的次序是棧的關(guān)鍵〔。可以把一桶桶裝的薯片看作是一個棧的例子，當(dāng)薯片做好之后瑟押，它們會依次被添加到桶里，每一片都會是當(dāng)前的最上面一片星掰，而每次我們?nèi)〉臅r候也是取的最上面的那一片多望，規(guī)定你不能破壞桶也不能把底部捅穿，所以第一個放入桶的薯片只能最后一個從桶里取出氢烘；
定義：棧（Stack）是一個有序線性表怀偷，只能在表的一端（稱為棧頂，top）執(zhí)行插入和刪除操作播玖。最后插入的元素將第一個被刪除椎工，所以棧也稱為后進(jìn)先出（Last In First Out，LIFO）或先進(jìn)后出（First In Last Out）線性表蜀踏；
兩個改變棧的操作都有專用名稱维蒙。一個稱為入棧（push），表示在棧中插入一個元素果覆；另一個稱為出棧（pop）颅痊，表示從棧中刪除一個元素。試圖對一個空棧執(zhí)行棧操作稱為下溢（underflow）局待；試圖對一個滿棧執(zhí)行棧操作稱為溢出（overflow）斑响。通常，溢出和下溢均認(rèn)為是異常钳榨；
棧的應(yīng)用
- 無處不在的Undo操作（撤銷）恋捆；
- 程序調(diào)用的系統(tǒng)棧；
- 括號/符號匹配重绷；
- 等等等等....
棧抽象數(shù)據(jù)類型
下面給出棧抽象數(shù)據(jù)類型中的操作，為了簡單起見膜毁，假設(shè)數(shù)據(jù)類型為整型昭卓；
棧的主要操作
-
void push(int data)：將data（數(shù)據(jù)）插入棧； -
int pop()：刪除并返回最后一個插入棧的元素瘟滨；
棧的輔助操作
-
int top()：返回最后一個插入棧的元素候醒，但不刪除； -
int size()：返回存儲在棧中元素的個數(shù)杂瘸； -
int isEmpty()：判斷棧中是否有元素倒淫； -
int isStackFull()：判斷棧中是否存滿元素；
動態(tài)數(shù)組簡單實(shí)現(xiàn)棧結(jié)構(gòu)
我們結(jié)合之前創(chuàng)建的Array類败玉，我們能夠很好的創(chuàng)建屬于我們自己的動態(tài)數(shù)組實(shí)現(xiàn)的棧結(jié)構(gòu)敌土，對于用戶來說镜硕，我們只需要完成我們的相關(guān)操作，并且知道我能夠不斷地往里添加元素而不出錯就行了返干，所以我們先來定義一個通用的棧接口：
public interface Stack<E> {
int getSize();
boolean isEmepty();
void push(E e);
E pop();
E top();
}
然后我們往之前的動態(tài)數(shù)組中添加兩個用戶友好的方法：
public E getLast() {
return get(size - 1);
}
public E getFirst() {
return get(0);
}
然后實(shí)現(xiàn)自己的動態(tài)數(shù)組為底層的棧結(jié)構(gòu)就輕松多了：
public class ArrayStack<E> implements Stack<E> {
Array<E> array;
public ArrayStack(int capacity) {
array = new Array<>(capacity);
}
public ArrayStack() {
array = new Array<>();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmepty() {
return array.isEmpty();
}
public int getCapacity() {
return array.getCapacity();
}
@Override
public void push(E e) {
array.addLast(e);
}
@Override
public E pop() {
return array.removeLast();
}
@Override
public E top() {
return array.getLast();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack:");
res.append("[");
for (int i = 0; i < array.getSize(); i++) {
res.append(array.get(i));
if (i != array.getSize() - 1) {
res.append(",");
}
}
res.append("]");
return res.toString();
}
}
簡單復(fù)雜度分析
從代碼中可以看出兴枯，幾乎所有的時間復(fù)雜度都為O(1)級別，比較特別的是push()和pop()操作可能涉及到底層數(shù)組的擴(kuò)容或縮容的操作矩欠，所以是均攤下來的復(fù)雜度财剖；
隊(duì)列
什么是隊(duì)列
隊(duì)列是一種用于存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)（與鏈表和棧類似），數(shù)據(jù)到達(dá)的次序是隊(duì)列的關(guān)鍵癌淮；在日常生活中隊(duì)列是指從序列的開始按照順序等待服務(wù)的一隊(duì)人或物躺坟；
定義：隊(duì)列是一種只能在一端插入（隊(duì)尾），在另一端刪除（隊(duì)首）的有序線性表乳蓄。隊(duì)列中第一個插入的元素也是第一個被刪除的元素咪橙，所以隊(duì)列是一種先進(jìn)先出（FIFO,First In First Out）或后進(jìn)后出（LiLO,Last In Last Out）線性表；
與棧類似栓袖，兩個改變隊(duì)列的操作各有專用名稱匣摘；在隊(duì)列中插入一個元素，稱為入隊(duì)（EnQueue）裹刮，從隊(duì)列中刪除一個元素音榜，稱為出隊(duì)（DeQueue）；試圖對一個空隊(duì)列執(zhí)行出隊(duì)操作稱為下溢（underflow）捧弃，試圖對一個滿隊(duì)列執(zhí)行入隊(duì)操作稱為溢出（overflow）赠叼；通常認(rèn)為溢出和下溢是異常。
隊(duì)列的一些應(yīng)用舉例
- 操作系統(tǒng)根據(jù)（具有相同優(yōu)先級的）任務(wù)到達(dá)的順序調(diào)度任務(wù)（例如打印隊(duì)列）违霞；
- 模擬現(xiàn)實(shí)世界中的隊(duì)列嘴办，如售票柜臺前的隊(duì)伍，或者任何需要先來先服務(wù)的場景买鸽；
- 多道程序設(shè)計(jì)涧郊；
- 異步數(shù)據(jù)傳輸（文件輸入輸出、管道眼五、套接字）妆艘；
- 等等等等...
動態(tài)數(shù)組簡單實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)
我們?nèi)匀欢x一個Queue接口來說明我們隊(duì)列中常用的一些方法：
public interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E dequeue();
E getFront();
}
借由我們之前自己實(shí)現(xiàn)的動態(tài)數(shù)組，那么我們的隊(duì)列就很簡單了：
public class ArrayQueue<E> implements Queue<E> {
private Array<E> array;
public ArrayQueue(int capacity){
array = new Array<>(capacity);
}
public ArrayQueue(){
array = new Array<>();
}
@Override
public int getSize(){
return array.getSize();
}
@Override
public boolean isEmpty(){
return array.isEmpty();
}
public int getCapacity(){
return array.getCapacity();
}
@Override
public void enqueue(E e){
array.addLast(e);
}
@Override
public E dequeue(){
return array.removeFirst();
}
@Override
public E getFront(){
return array.getFirst();
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Queue: ");
res.append("front [");
for(int i = 0 ; i < array.getSize() ; i ++){
res.append(array.get(i));
if(i != array.getSize() - 1)
res.append(", ");
}
res.append("] tail");
return res.toString();
}
}
簡單的復(fù)雜度分析
-
void enquque(E)：O(1)（均攤） -
E dequeue()：O(n) -
E front()：O(1) -
int getSize()：O(1) -
boolean isEmpty()：O(1)
實(shí)現(xiàn)自己的循環(huán)隊(duì)列
循環(huán)隊(duì)列的實(shí)現(xiàn)其實(shí)就是維護(hù)了一個front和一個tail分別指向頭和尾看幼，然后需要特別注意的呢是判定隊(duì)滿和隊(duì)空的條件：
- 隊(duì)空：
front == tail批旺，這沒啥好說的； - 隊(duì)滿：
tail + 1 == front诵姜，這里其實(shí)是有意浪費(fèi)了一個空間汽煮，不然就判定不了到底是隊(duì)空還是隊(duì)滿了，因?yàn)闂l件都一樣...
public class LoopQueue<E> implements Queue<E> {
private E[] data;
private int front, tail;
private int size;
public LoopQueue(int capacity){
data = (E[])new Object[capacity + 1];
front = 0;
tail = 0;
size = 0;
}
public LoopQueue(){
this(10);
}
public int getCapacity(){
return data.length - 1;
}
@Override
public boolean isEmpty(){
return front == tail;
}
@Override
public int getSize(){
return size;
}
@Override
public void enqueue(E e){
if((tail + 1) % data.length == front)
resize(getCapacity() * 2);
data[tail] = e;
tail = (tail + 1) % data.length;
size ++;
}
@Override
public E dequeue(){
if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
E ret = data[front];
data[front] = null;
front = (front + 1) % data.length;
size --;
if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
resize(getCapacity() / 2);
return ret;
}
@Override
public E getFront(){
if(isEmpty())
throw new IllegalArgumentException("Queue is empty.");
return data[front];
}
private void resize(int newCapacity){
E[] newData = (E[])new Object[newCapacity + 1];
for(int i = 0 ; i < size ; i ++)
newData[i] = data[(i + front) % data.length];
data = newData;
front = 0;
tail = size;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
res.append("front [");
for(int i = front ; i != tail ; i = (i + 1) % data.length){
res.append(data[i]);
if((i + 1) % data.length != tail)
res.append(", ");
}
res.append("] tail");
return res.toString();
}
}
簡單復(fù)雜度分析
-
void enquque(E)：O(1)（均攤） -
E dequeue()：O(1)（均攤） -
E front()：O(1) -
int getSize()：O(1) -
boolean isEmpty()：O(1)
簡單數(shù)組隊(duì)列和循環(huán)隊(duì)列的簡單比較
我們來簡單對比一下兩個隊(duì)列的性能吧，這里直接上代碼：
// 測試使用q運(yùn)行opCount個enqueueu和dequeue操作所需要的時間暇赤，單位：秒
private static double testQueue(Queue<Integer> q, int opCount){
long startTime = System.nanoTime();
Random random = new Random();
for(int i = 0 ; i < opCount ; i ++)
q.enqueue(random.nextInt(Integer.MAX_VALUE));
for(int i = 0 ; i < opCount ; i ++)
q.dequeue();
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
int opCount = 100000;
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
double time1 = testQueue(arrayQueue, opCount);
System.out.println("ArrayQueue, time: " + time1 + " s");
LoopQueue<Integer> loopQueue = new LoopQueue<>();
double time2 = testQueue(loopQueue, opCount);
System.out.println("LoopQueue, time: " + time2 + " s");
}
我這里的測試結(jié)果是這樣的心例，大家也就可見一斑啦：
其實(shí)ArrayQueue慢主要是因?yàn)槌鰲r每次都需要把整個結(jié)構(gòu)往前挪一下
LeetCode 相關(guān)題目整理
20.有效的括號
我的答案：（10ms）
public boolean isValid(String s) {
// 正確性判斷
if (null == s || s.length() == 1) {
return false;
}
Stack<Character> stack = new Stack<>();
// 遍歷輸入的字符
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 如果為左括號則push進(jìn)棧
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char topChar = stack.pop();
if (c == ')' && topChar != '(') {
return false;
}
if (c == ']' && topChar != '[') {
return false;
}
if (c == '}' && topChar != '{') {
return false;
}
}
}
// 最后棧為空才能返回true
return stack.isEmpty();
}
參考答案：（8ms）
public boolean isValid(String s) {
// 正確性判斷
if (0 == s.length()) {
return true;
}
if (s.length() % 2 == 1) {
return false;
}
Stack<Character> stack = new Stack();
char[] cs = s.toCharArray();
for (int i = 0; i < cs.length; i++) {
if (cs[i] == '(' || cs[i] == '[' || cs[i] == '{') {
stack.push(cs[i]);
} else {
if (stack.isEmpty()) {
return false;
}
char c = stack.pop();
if ((cs[i] == ')' && c == '(') || (cs[i] == '}' && c == '{') || (cs[i] == ']' && c == '[')) {
} else {
return false;
}
}
}
return stack.isEmpty();
}
155. 最小棧（劍指Offer面試題30）
參考答案（107ms）
class MinStack {
// 數(shù)據(jù)棧，用于存放插入的數(shù)據(jù)
private Stack<Integer> dataStack;
// 最小數(shù)位置棧翎卓，存放數(shù)據(jù)棧中最小的數(shù)的位置
private Stack<Integer> minStack;
/**
* initialize your data structure here.
*/
public MinStack() {
this.dataStack = new Stack<>();
this.minStack = new Stack<>();
}
/**
* 元素入棧
*
* @param x 入棧的元素
*/
public void push(int x) {
dataStack.push(x);
// 如果最小棧是空的契邀，只要將元素入棧
if (minStack.isEmpty()) {
minStack.push(x);
}
// 如果最小棧中有數(shù)據(jù)
else {
minStack.push(Math.min(x, minStack.peek()));
}
}
/**
* 出棧方法
*/
public void pop() {
// 如果棧已經(jīng)為空，則返回（LeetCode不能拋異常...）
if (dataStack.isEmpty()) {
return;
}
// 如果有數(shù)據(jù)失暴，最小數(shù)位置棧和數(shù)據(jù)棧必定是有相同的元素個數(shù)坯门，
// 兩個棧同時出棧
minStack.pop();
dataStack.pop();
}
/**
* 返回棧頂元素
*
* @return 棧頂元素
*/
public int top() {
return dataStack.peek();
}
/**
* 獲取棧中的最小元素
*
* @return 棧中的最小元素
*/
public int getMin() {
// 如果最小數(shù)公位置棧已經(jīng)為空（數(shù)據(jù)棧中已經(jīng)沒有數(shù)據(jù)了），則拋出異常
if (minStack.isEmpty()) {
return 0;
}
// 獲取數(shù)據(jù)占中的最小元素逗扒，并且返回結(jié)果
return minStack.peek();
}
}
改進(jìn)答案：
上面求解方法的主要問題在于古戴，每次push操作時，minStack也執(zhí)行了一次push操作（新元素或當(dāng)前的最小元素）矩肩，也就是說现恼，重復(fù)執(zhí)行了最小值的入棧操作，所以現(xiàn)在我們來修改算法降低空間復(fù)雜度黍檩。仍然需要設(shè)置一個minStack叉袍，但是只有當(dāng)從dataStack中出棧的元素等于minStack棧頂元素時，才對minStack執(zhí)行出棧的操作刽酱；也只有當(dāng)dataStack入棧的元素小于或等于當(dāng)前最小值時喳逛，才對minStack執(zhí)行入棧操作，下面就簡單寫一下了主要看一下出棧和入棧實(shí)現(xiàn)的邏輯就好了：
class MinStack {
private Stack<Integer> dataStack;
private Stack<Integer> minStack;
public MinStack() {
this.dataStack = new Stack<>();
this.minStack = new Stack<>();
}
public void push(int x) {
dataStack.push(x);
if (minStack.isEmpty() || minStack.peek() >= (Integer) x) {
minStack.push(x);
}
}
public void pop() {
if (dataStack.isEmpty()) {
return;
}
Integer minTop = minStack.peek();
Integer dataTop = dataStack.peek();
if (minTop.intValue() == dataTop.intValue()) {
minStack.pop();
}
dataStack.pop();
}
public int top() {
return dataStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
225. 用隊(duì)列實(shí)現(xiàn)棧
我的答案：（118ms）
class MyStack {
private Queue<Integer> queue1;
private Queue<Integer> queue2;
/**
* Initialize your data structure here.
*/
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
/**
* Push element x onto stack.
*/
public void push(int x) {
if (queue1.isEmpty()) {
queue2.offer(x);
} else {
queue1.offer(x);
}
}
/**
* Removes the element on top of the stack and returns that element.
*/
public int pop() {
int size;
if (!queue1.isEmpty()) {
size = queue1.size();
for (int i = 0; i < size - 1; i++) {
queue2.offer(queue1.poll());
}
return queue1.poll();
} else {
size = queue2.size();
for (int i = 0; i < size - 1; i++) {
queue1.offer(queue2.poll());
}
return queue2.poll();
}
}
/**
* Get the top element.
*/
public int top() {
int size;
if (!queue1.isEmpty()) {
size = queue1.size();
for (int i = 0; i < size - 1; i++) {
queue2.offer(queue1.poll());
}
int result = queue1.peek();
queue2.offer(queue1.poll());
return result;
} else {
size = queue2.size();
for (int i = 0; i < size - 1; i++) {
queue1.offer(queue2.poll());
}
int result = queue2.peek();
queue1.offer(queue2.poll());
return result;
}
}
/**
* Returns whether the stack is empty.
*/
public boolean empty() {
return queue1.isEmpty() && queue2.isEmpty();
}
}
參考答案：（121ms）
class MyStack {
Queue<Integer> q;
/**
* Initialize your data structure here.
*/
public MyStack() {
this.q = new LinkedList<Integer>();
}
/**
* Push element x onto stack.
*/
public void push(int x) {
q.add(x);
}
/**
* Removes the element on top of the stack and returns that element.
*/
public int pop() {
int size = q.size();
for (int i = 0; i < size - 1; i++) {
q.add(q.remove());
}
return q.remove();
}
/**
* Get the top element.
*/
public int top() {
int size = q.size();
for (int i = 0; i < size - 1; i++) {
q.add(q.remove());
}
int ret = q.remove();
q.add(ret);
return ret;
}
/**
* Returns whether the stack is empty.
*/
public boolean empty() {
return q.isEmpty();
}
}
確實(shí)寫得簡潔啊棵里，這樣一來我就使用一個隊(duì)列和兩個隊(duì)列都掌握啦润文，開心~
232.用棧實(shí)現(xiàn)隊(duì)列（劍指Offer面試題9）
參考答案：（72ms）
class MyQueue {
Stack<Integer> pushstack;
Stack<Integer> popstack;
/**
* Initialize your data structure here.
*/
public MyQueue() {
this.pushstack = new Stack();
this.popstack = new Stack();
}
/**
* Push element x to the back of queue.
*/
public void push(int x) {
pushstack.push(x);
}
/**
* Removes the element from in front of queue and returns that element.
*/
public int pop() {
if (popstack.isEmpty()) {
while (!pushstack.isEmpty()) {
popstack.push(pushstack.pop());
}
}
return popstack.pop();
}
/**
* Get the front element.
*/
public int peek() {
if (popstack.isEmpty()) {
while (!pushstack.isEmpty()) {
popstack.push(pushstack.pop());
}
}
return popstack.peek();
}
/**
* Returns whether the queue is empty.
*/
public boolean empty() {
return pushstack.isEmpty() && popstack.isEmpty();
}
}
其他題目整理
劍指Offer面試題31：棧的壓入、彈出序列
題目：輸入兩個整數(shù)序列殿怜，第一個序列表示棧的壓入順序典蝌，請判斷第二個序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等头谜。例如骏掀，序列{1,2,3,4,5}是某棧的壓棧序列，序列{4,5,3,2,1}是該壓棧序列對應(yīng)的一個彈出序列柱告，但{4,3,5,1,2}就不可能是該壓棧序列的彈出序列砖织。
參考答案：（原文鏈接：https://blog.csdn.net/derrantcm/article/details/46691083）
public class Test22 {
/**
* 輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序末荐，請判斷二個序列是否為該棧的彈出順序。
* 假設(shè)壓入棧的所有數(shù)字均不相等新锈。例如序列1 甲脏、2、3 、4块请、5 是某棧壓棧序列娜氏，
* 序列4、5墩新、3贸弥、2、1是該壓棧序列對應(yīng)的一個彈出序列海渊，
* 但4绵疲、3、5臣疑、1盔憨、2就不可能是該壓棋序列的彈出序列。
* 【與書本的的方法不同】
*
* @param push 入棧序列
* @param pop 出棧序列
* @return true：出棧序列是入棧序列的一個彈出順序
*/
public static boolean isPopOrder(int[] push, int[] pop) {
// 輸入校驗(yàn)讯沈，參數(shù)不能為空郁岩，并且兩個數(shù)組中必須有數(shù)字，并且兩個數(shù)組中的數(shù)字個數(shù)相同
// 否則返回false
if (push == null || pop == null || pop.length == 0 || push.length == 0 || push.length != pop.length) {
return false;
}
// 經(jīng)過上面的參數(shù)校驗(yàn)缺狠，兩個數(shù)組中一定有數(shù)據(jù)问慎，且數(shù)據(jù)數(shù)目相等
// 用于存放入棧時的數(shù)據(jù)
Stack<Integer> stack = new Stack<>();
// 用于記錄入棧數(shù)組元素的處理位置
int pushIndex = 0;
// 用于記錄出棧數(shù)組元素的處理位置
int popIndex = 0;
// 如果還有出棧元素要處理
while (popIndex < pop.length) {
// 入棧元素還未全部入棧的條件下，如果棧為空挤茄，或者棧頂?shù)脑夭慌c當(dāng)前處理的相等如叼，則一直進(jìn)行棧操作，
// 直到入棧元素全部入椡苑或者找到了一個與當(dāng)出棧元素相等的元素
while (pushIndex < push.length && (stack.isEmpty() || stack.peek() != pop[popIndex])) {
// 入棧數(shù)組中的元素入棧
stack.push(push[pushIndex]);
// 指向下一個要處理的入棧元素
pushIndex++;
}
// 如果在上一步的入棧過程中找到了與出棧的元素相等的元素
if (stack.peek() == pop[popIndex]) {
// 將元素出棧
stack.pop();
// 處理下一個出棧元素
popIndex++;
}
// 如果沒有找到與出棧元素相等的元素薇正，說明這個出棧順序是不合法的
// 就返回false
else {
return false;
}
}
// 下面的語句總是成立的
// return stack.isEmpty();
// 為什么可以直接返回true：對上面的外層while進(jìn)行分析可知道，對每一個入棧的元素囚衔，
// 在stack棧中挖腰，通過一些入棧操作，總可以在棧頂上找到與入棧元素值相同的元素练湿，
// 這就說明了這個出棧的順序是入棧順序的一個彈出隊(duì)列猴仑，這也可以解釋為什么stack.isEmpty()
// 總是返回true，所有的入棧元素都可以進(jìn)棧肥哎，并且可以被匹配到辽俗，之后就彈出，最后棧中就無元素篡诽。
return true;
}
/**
* 輸入兩個整數(shù)序列崖飘，第一個序列表示棧的壓入順序，請判斷二個序列是否為該棧的彈出順序杈女。
* 【按書本上的思路進(jìn)行求解朱浴，兩者相差不大】
*
* @param push 入棧序列
* @param pop 出棧序列
* @return true：出棧序列是入棧序列的一個彈出順序
*/
public static boolean isPopOrder2(int[] push, int[] pop) {
// 用于記錄判斷出棧順序是不是入棧順的一個出棧序列吊圾，默認(rèn)false
boolean isPossible = false;
// 當(dāng)入棧和出棧數(shù)組者都不為空，并且都有數(shù)據(jù)翰蠢，并且數(shù)據(jù)個數(shù)都相等
if (push != null && pop != null && push.length > 0 && push.length == pop.length) {
// 用于存放入棧時的數(shù)據(jù)
Stack<Integer> stack = new Stack<>();
// 記錄下一個要處理的入棧元素的位置
int nextPush = 0;
// 記錄下一個要處理的出棧元素的位置
int nextPop = 0;
// 如果出棧元素沒有處理完就繼續(xù)進(jìn)行處理
while (nextPop < pop.length) {
// 如果棧為空或者棧頂?shù)脑嘏c當(dāng)前處理的出棧元素不相同项乒，一直進(jìn)行操作
while (stack.isEmpty() || stack.peek() != pop[nextPop]) {
// 如果入棧的元素已經(jīng)全部入棧了，就退出內(nèi)層循環(huán)
if (nextPush >= push.length) {
break;
}
// 執(zhí)行到此處說明還有入棧元素可以入棧
// 即將元素入棧
stack.push(push[nextPush]);
// 指向下一個要處理的入棧元素的位置
nextPush++;
}
// 執(zhí)行到此處有兩種情況：
// 第一種：在棧頂上找到了一個與入棧元素相等的元素
// 第二種：在棧頂上沒有找到一個與入棧元素相等的元素梁沧，而且輸入棧的元素已經(jīng)全部入棧了
// 對于第二種情況就說彈出棧的順序是不符合要求的檀何，退出外層循環(huán)
if (stack.peek() != pop[nextPop]) {
break;
}
// 對應(yīng)到第一種情況：需要要棧的棧頂元素彈出
stack.pop();
// 指向下一個要處理的出棧元素的位置
nextPop++;
}
// 執(zhí)行到此處有兩種情況
// 第一種：外層while循環(huán)的在第一種情況下退出，
// 第二種：所有的出棧元素都被正確匹配
// 對于出現(xiàn)的第一種情況其stack.isEmpty()必不為空廷支，原因?yàn)榉治鋈缦拢? // 所有的入棧元素一定會入棧频鉴，但是只有匹配的情況下才會出棧，
// 匹配的次數(shù)最多與入棧元素個數(shù)元素相同（兩個數(shù)組的長度相等）酥泞，如果有不匹配的元素砚殿，
// 必然會使出棧的次數(shù)比入棧的次數(shù)少，這樣棧中至少會有一個元素
// 對于第二種情況其stack.isEmpty()一定為空
// 所以書本上的nextPop == pop.length（pNextPop-pPop==nLength）是多余的
if (stack.isEmpty()) {
isPossible = true;
}
}
return isPossible;
}
public static void main(String[] args) {
int[] push = {1, 2, 3, 4, 5};
int[] pop1 = {4, 5, 3, 2, 1};
int[] pop2 = {3, 5, 4, 2, 1};
int[] pop3 = {4, 3, 5, 1, 2};
int[] pop4 = {3, 5, 4, 1, 2};
System.out.println("true: " + isPopOrder(push, pop1));
System.out.println("true: " + isPopOrder(push, pop2));
System.out.println("false: " + isPopOrder(push, pop3));
System.out.println("false: " + isPopOrder(push, pop4));
int[] push5 = {1};
int[] pop5 = {2};
System.out.println("false: " + isPopOrder(push5, pop5));
int[] push6 = {1};
int[] pop6 = {1};
System.out.println("true: " + isPopOrder(push6, pop6));
System.out.println("false: " + isPopOrder(null, null));
// 測試方法2
System.out.println();
System.out.println("true: " + isPopOrder2(push, pop1));
System.out.println("true: " + isPopOrder2(push, pop2));
System.out.println("false: " + isPopOrder2(push, pop3));
System.out.println("false: " + isPopOrder2(push, pop4));
System.out.println("false: " + isPopOrder2(push5, pop5));
System.out.println("true: " + isPopOrder2(push6, pop6));
System.out.println("false: " + isPopOrder2(null, null));
}
}
簡單總結(jié)
棧和隊(duì)列的應(yīng)用遠(yuǎn)不止上面學(xué)習(xí)到的那些芝囤，實(shí)現(xiàn)方式也有很多種似炎，現(xiàn)在也只是暫時學(xué)到這里，通過刷LeetCode也加深了我對于這兩種數(shù)據(jù)結(jié)構(gòu)的認(rèn)識悯姊，不過自己還需要去熟悉了解一下計(jì)算機(jī)系統(tǒng)關(guān)于棧的應(yīng)用這方面的知識羡藐，因?yàn)闂＿@種結(jié)構(gòu)本身就很適合用來保存CPU現(xiàn)場之類的工作，還是抓緊時間吧悯许，過兩天還考試仆嗦，這兩天就先復(fù)習(xí)啦...
歡迎轉(zhuǎn)載，轉(zhuǎn)載請注明出處先壕！
簡書ID：@我沒有三顆心臟
github：wmyskxz
歡迎關(guān)注公眾微信號：wmyskxz_javaweb
分享自己的Java Web學(xué)習(xí)之路以及各種Java學(xué)習(xí)資料
