一.棧的概念

一種特殊的線性表，只能從固定的一端插入和刪除元素。

棧中元素遵循先進后出的原則。

二.模擬實現

public class MyStack {public int size;public int[] array;public  MyStack(){array =new int[10];}private void grow(){array = Arrays.copyOf(array,array.length*2);}public int size(){return size;}private boolean isFull(){return size==array.length;}public Boolean empty(){return size==0;}public void push(int data){if (isFull()){grow();}array[size]=data;size++;}public int pop(){if (empty()){return -1;}return array[--size];}public int peek(){if (empty()){return -1;}return array[size-1];}
}

注意：

該模擬實現底層是靠數組，除了數值，還可以用鏈表。

單向鏈表：

采用尾插法時，push和pop時間復雜度為O (n), 原因是壓棧時要遍歷鏈表到尾部壓棧，如果在尾部定義一個尾節點時 時間復雜度為O (1)。出棧時后進先出，尾部最后進，要遍歷到倒數第二個節點，才能刪除尾節點。

采用首插法時，push和pop時間復雜度都為O (1),原因是遍歷鏈表時出棧時，剛好遵循先進后出的原則。

雙向鏈表：

無論是尾插法還是首插法，push和pop時間復雜度為O (1).

三.棧的方法

四.中綴表達式轉后綴表達式

五.棧的使用

1.逆序打印鏈表

 public boolean isValid(String s) {Stack<Character> stack1 =new Stack<>();for(int i=0;i<s.length();i++){char ch =s.charAt(i);if(ch=='('||ch=='{'||ch=='['){stack1.push(ch);}else{//字符串沒遍歷完的情況if(stack1.empty()){return false;}//比較相不相等if(stack1.peek()=='(' && ch==')'||stack1.peek()=='{'&&ch=='}'||stack1.peek()=='['&&ch==']'){stack1.pop();   //相等就彈出一個字符}else{return false; }}}//棧中有剩余的情況if(stack1.empty()){return true;}else{return false;}}

2.逆波蘭表達式求值

    public int evalRPN(String[] tokens) {Stack<Integer> stack =new Stack<>();int sum =0;for(int i=0;i<tokens.length;i++){if(tokens[i].equals("+")||tokens[i].equals("-")||tokens[i].equals("*")||tokens[i].equals("/")){int val2=stack.pop();int val1=stack.pop();switch(tokens[i]){case "+" :sum=val1+val2;break;case "-" :sum=val1-val2;break;     case "*" :sum=val1*val2;break;     case "/" :sum=val1/val2;break;}stack.push(sum);}else{stack.push(Integer.valueOf(tokens[i]));}}return stack.pop();}

3.最小棧

class MinStack {public Stack<Integer> stack1;public Stack<Integer> stack2;public MinStack() {stack1 =new Stack<>();stack2 =new Stack<>();}public void push(int val) {stack1.push(val);if(stack2.empty()||val<=stack2.peek()){stack2.push(val);}}public void pop() {if(stack1.empty()){return;}if(stack1.peek().equals(stack2.peek())){  stack1.pop();stack2.pop();}else{stack1.pop();}}public int top() {if(stack1.empty()){    return -1;}return stack1.peek();}public int getMin() {if(stack1.empty()){return -1;}return stack2.peek();}
}

注意：

其中的pop方法必須用equals來進行比較，因為是Integer類型，范圍較小，超出范圍時會創建新對象存儲值，用 == 去比較時就是比的是地址

六.隊列的模擬實現

采用先進先出的原則。

用數組實現不行，原因如下：

所以采用單向鏈表或雙向鏈表

單向鏈表：

采用頭差法，push時間復雜度為O (1)和pop時間復雜度為為O (n),因為尾部元素為最先進的元素，得遍歷到倒數第二個節點才能刪除

采用尾插法，在定義一個尾節點，push和pop時間復雜度和空間復雜度為O (1)

雙向鏈表：

倆種都可以

模擬實現：

public class MyQueue {class ListNode{public int val;public ListNode next;public ListNode pre;public ListNode(int val) {this.val = val;}}private ListNode head;private ListNode last;private int size;public int size(){return size;}public boolean isEmpty(){return size==0;}public void offer(int value){ListNode node =new ListNode(value);if (head==null){head=last=node;}else {last.next=node;node.pre=last;last=last.next;}size++;}public int poll(){if (isEmpty()){return -1;}int ret=0;if(head.next==null){ret =head.val;head=last=null;}else {ret =head.val;head=head.next;head.pre=null;}size--;return ret;}public int peek(){if (isEmpty()){return -1;}return head.val;}

七.循環隊列

1.保留一個位置

class MyCircularQueue {public int[] array;public int front;public int rear;public MyCircularQueue(int k) {array =new int[k+1];}public boolean enQueue(int value) {if(isFull()){return false;}array[rear] =value;rear=(rear+1)%array.length;return true;}public boolean deQueue() {if(isEmpty()){return false;}front=(front+1)%array.length;return true;}public int Front() {if(isEmpty()){return -1;}return array[front];}public int Rear() {if(isEmpty()){return -1;}return array[(rear-1+array.length)%array.length];}public boolean isEmpty() {return rear==front;}public boolean isFull() {return (rear+1)%array.length==front;}
}

除此之外，還可以通過size記錄元素數量來判斷隊列是否滿了或空的

八.雙端隊列（Deque）

雙端隊列（Deque）是指允許兩端都可以進行入隊和出隊操作的隊列，那就說明元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊。