抽象數(shù)據(jù)類型（ADT见擦，abstract data type）
- 抽象數(shù)據(jù)類型是帶有一組操作的一些對(duì)象的集合摘完。
- 抽象數(shù)據(jù)類型可以用以下的三元組來(lái)表示：
ADT抽象數(shù)據(jù)類型名{
數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>
數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>
基本操作：<基本操作的定義>
} ADT抽象數(shù)據(jù)類型名 - 抽象數(shù)據(jù)類型的主要作用是數(shù)據(jù)封裝和信息隱藏姥饰，讓實(shí)現(xiàn)與使用相分離。數(shù)據(jù)及其相關(guān)操作的結(jié)合稱為數(shù)據(jù)封裝孝治。對(duì)象可以對(duì)其他對(duì)象隱藏某些操作細(xì)節(jié)媳否，從而使這些操作不會(huì)受到其他對(duì)象的影響，這就是信息隱藏荆秦。
- 參考：http://c.biancheng.net/view/7526.html
表ADT
- 表的定義
形如的一組元素集合篱竭，我們稱之為表，大小為N步绸。N為0的表掺逼，我們稱之為空表。
我們說(shuō)的后繼為
瓤介，前驅(qū)為
吕喘。
- 表的一般操作
printList赘那，makeEmpty，find（返回某一項(xiàng)首次出現(xiàn)的位置）氯质，insert/remove（從表的某個(gè)位置插入和刪除某個(gè)元素）募舟，findKth（返回某個(gè)位置上的元素） - 表的簡(jiǎn)單數(shù)組實(shí)現(xiàn)
雖然數(shù)組由固定容量創(chuàng)建，但在需要的時(shí)候可以用雙倍容量擴(kuò)展闻察。
1）printList操作：線性時(shí)間拱礁，即O(N)時(shí)間復(fù)雜度
2）findKth操作：常數(shù)時(shí)間，由下標(biāo)直接索引辕漂，即O(1)時(shí)間復(fù)雜度呢灶；
3）插入和刪除操作：和發(fā)生的位置有關(guān)，最壞情況下钉嘹，如在位置0插入元素或者刪除元素鸯乃，花費(fèi)O(N)時(shí)間復(fù)雜度。但在末尾刪除或者添加跋涣，花費(fèi)O(1)時(shí)間缨睡。 - 簡(jiǎn)單鏈表
為了避免插入和刪除操作的線性開(kāi)銷，我們需要保證表可以不連續(xù)存儲(chǔ)陈辱，否則表的每個(gè)部分都可能需要整體移動(dòng)奖年。
鏈表由一系列節(jié)點(diǎn)組成，這些節(jié)點(diǎn)不必再內(nèi)存中相連性置。每一個(gè)節(jié)點(diǎn)均含有表元素和后繼節(jié)點(diǎn)的鏈（link）拾并。我們稱之為next鏈，最后一個(gè)單元的next鏈引用為null鹏浅。
1）printList操作：線性時(shí)間嗅义，需要從第一個(gè)節(jié)點(diǎn)遍歷到最后一個(gè)節(jié)點(diǎn)
2）find(x)操作：線性時(shí)間，需要從第一個(gè)節(jié)點(diǎn)遍歷到最后一個(gè)節(jié)點(diǎn)
3）findKth操作：O(K)隐砸，也是線性時(shí)間之碗，但可以通過(guò)一次遍歷可獲取findKth(1)，findKth(2)季希，findKth(n)所有答案褪那。
4）插入和刪除操作：?jiǎn)捂湵碇痪S持了頭部節(jié)點(diǎn)的引用，對(duì)于頭部插入的操作式塌，花費(fèi)O(1)時(shí)間博敬，對(duì)于其他位置的插入，花費(fèi)線性時(shí)間定位到該位置峰尝，插入操作或刪除操作本身只涉及常數(shù)個(gè)節(jié)點(diǎn)鏈的改變偏窝，總體時(shí)間還是為線性時(shí)間；雙鏈表維持頭部和尾部?jī)蓚€(gè)節(jié)點(diǎn)的引用，所于頭部和尾部的插入刪除操作祭往，只花費(fèi)O(1)的常數(shù)時(shí)間伦意。
Java Collections API中的表
Collection接口
Collection接口擴(kuò)展了Iterable接口，實(shí)現(xiàn)了Iterable接口的那些類可以使用增強(qiáng)for循環(huán)：
Iterator接口
實(shí)現(xiàn)Iterator接口的集合必須提供一個(gè)iterator()方法硼补，返回一個(gè)Iterator類型的對(duì)象驮肉。
使用Iterator的remove方法，相比使用Collection的remove方法的優(yōu)點(diǎn)：
1）Collection的remove方法必須首先找到要被刪除的項(xiàng)已骇。在實(shí)現(xiàn)諸如在集合中每隔一項(xiàng)刪除一項(xiàng)的功能离钝，Iterator很容易實(shí)現(xiàn)，并且效率更高疾捍。
2）如果對(duì)正在被迭代的集合進(jìn)行結(jié)構(gòu)上的改變（add奈辰，remove栏妖，clear等）跌前，我們更愿意使用迭代器的remvoe方法聊替，如果使用Collection的remove方法會(huì)拋出ConcurrentModificationException。
List接口、ArrayList類和LinkedList類
List接口繼承了Collection接口陪腌，并且增加了額外的一些方法。
List接口中的add和remvoe支持指定位置的增加和刪除骇钦，和Collection接口中指定元素的增加和刪除不一樣所禀。get和set可以訪問(wèn)或者改變由位置索引idx給定的表中指定位置上的項(xiàng)。
List ADT有兩種流行的實(shí)現(xiàn)方式：
- ArrayList類
1）實(shí)現(xiàn)：可增長(zhǎng)數(shù)組
2）優(yōu)點(diǎn)：對(duì)get和set的調(diào)用花費(fèi)常數(shù)時(shí)間屁奏，因?yàn)橥ㄟ^(guò)數(shù)組的下標(biāo)直接定位岩榆。
3）缺點(diǎn)：對(duì)新項(xiàng)的插入和現(xiàn)有項(xiàng)的刪除代價(jià)昂貴，花費(fèi)線性時(shí)間坟瓢，除非插入和刪除在ArrayList的末端進(jìn)行勇边。 - LinkedList類
1）實(shí)現(xiàn)：雙鏈表
2）優(yōu)點(diǎn)：新項(xiàng)的插入和現(xiàn)有項(xiàng)的刪除開(kāi)銷都很小，這里假設(shè)變動(dòng)項(xiàng)的位置已知折联。如果變動(dòng)項(xiàng)的位置不知粒褒，那么仍然花費(fèi)線性時(shí)間定位到變動(dòng)項(xiàng)位置，然后花費(fèi)常數(shù)時(shí)間進(jìn)行插入操作诚镰；但是對(duì)于開(kāi)頭和結(jié)尾位置的刪除和插入只花費(fèi)常數(shù)時(shí)間奕坟。所以LinkedList額外提供了addFirst和removeFirst，addLast和removeLast
3）缺點(diǎn)：不容易操作索引清笨，因此對(duì)get的調(diào)用是昂貴的 - 共通點(diǎn)
對(duì)搜索而言月杉，ArrayList和LinkedList都是低效的，對(duì)Collection的contains和remove（以AnyType為參數(shù)）的調(diào)用都花費(fèi)線性時(shí)間抠艾。
例子：remove方法對(duì)LinkedList類的使用
例子：將表中所有的值為偶數(shù)的項(xiàng)刪除苛萎。
辦法：使用LinkedList，并且使用迭代器進(jìn)行遍歷。
ArrayList的類實(shí)現(xiàn)
package com.corp.qiyun.datastruct;
public class MyArrayList<AnyType> implements Iterable<AnyType> {
private static final int DEFAULT_CAPACITY = 10;
private AnyType[] theItems;
private int theSize; // 元素個(gè)數(shù), 保持最后元素的位置
/**
* Construct an empty ArrayList.
*/
public MyArrayList() {
doClear();
}
/**
* Returns the number of items in this collection.
*
* @return the number of items in this collection.
*/
public int size() {
return theSize;
}
/**
* Returns true if this collection is empty.
*
* @return true if this collection is empty.
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* Returns the item at position idx.
*
* @param idx the index to search in.
* @throws ArrayIndexOutOfBoundsException if index is out of range.
*/
public AnyType get(int idx) {
if (idx < 0 || idx >= size())
throw new ArrayIndexOutOfBoundsException("Index " + idx + "; size " + size());
return theItems[idx];
}
/**
* Changes the item at position idx.
*
* @param idx the index to change.
* @param newVal the new value.
* @return the old value.
* @throws ArrayIndexOutOfBoundsException if index is out of range.
*/
public AnyType set(int idx, AnyType newVal) {
if (idx < 0 || idx >= size())
throw new ArrayIndexOutOfBoundsException("Index " + idx + "; size " + size());
AnyType old = theItems[idx];
theItems[idx] = newVal;
return old;
}
@SuppressWarnings("unchecked")
public void ensureCapacity(int newCapacity) {
if (newCapacity < theSize)
return;
AnyType[] old = theItems;
theItems = (AnyType[]) new Object[newCapacity];
for (int i = 0; i < size(); i++)
theItems[i] = old[i];
}
/**
* Adds an item to this collection, at the end.
*
* @param x any object.
* @return true.
*/
public boolean add(AnyType x) {
add(size(), x);
return true;
}
/**
* Adds an item to this collection, at the specified index.
*
* @param x any object.
* @return true.
*/
public void add(int idx, AnyType x) {
if (theItems.length == size())
ensureCapacity(size() * 2 + 1);
for (int i = theSize; i > idx; i--)
theItems[i] = theItems[i - 1];
theItems[idx] = x;
theSize++;
}
/**
* Removes an item from this collection.
*
* @param idx the index of the object.
* @return the item was removed from the collection.
*/
public AnyType remove(int idx) {
AnyType removedItem = theItems[idx];
for (int i = idx; i < size() - 1; i++)
theItems[i] = theItems[i + 1];
theSize--;
return removedItem;
}
/**
* Change the size of this collection to zero.
*/
public void clear() {
doClear();
}
private void doClear() {
theSize = 0;
ensureCapacity(DEFAULT_CAPACITY);
}
/**
* Obtains an Iterator object used to traverse the collection.
*
* @return an iterator positioned prior to the first element.
*/
public java.util.Iterator<AnyType> iterator() {
return new ArrayListIterator();
}
/**
* Returns a String representation of this collection.
*/
public String toString() {
StringBuilder sb = new StringBuilder("[ ");
for (AnyType x : this)
sb.append(x + " ");
sb.append("]");
return new String(sb);
}
/**
* This is the implementation of the ArrayListIterator.
* It maintains a notion of a current position and of
* course the implicit reference to the MyArrayList.
*/
private class ArrayListIterator implements java.util.Iterator<AnyType> {
private int current = 0;
private boolean okToRemove = false;
public boolean hasNext() {
return current < size(); // 這里相當(dāng)于MyArrayList.this.size()首懈，前面外部類引用可省略
}
public AnyType next() {
if (!hasNext())
throw new java.util.NoSuchElementException();
okToRemove = true;
return theItems[current++]; // 即MyArrayList.this.theItems[current++]
}
public void remove() {
if (!okToRemove)
throw new IllegalStateException();
// 編譯器自動(dòng)為非靜態(tài)內(nèi)部類添加一個(gè)成員變量绊率， 這個(gè)成員變量就是指向外部類對(duì)象的引用；這里沒(méi)有省略MyArrayList.this是因?yàn)閖ava.util.Iterator聲明了remove方法究履，為了防止歧義滤否，這里必須加上
MyArrayList.this.remove(--current);
okToRemove = false;
}
}
}
class TestArrayList {
public static void main(String[] args) {
MyArrayList<Integer> lst = new MyArrayList<>();
for (int i = 0; i < 10; i++)
lst.add(i);
for (int i = 20; i < 30; i++)
lst.add(0, i);
lst.remove(0);
lst.remove(lst.size() - 1);
System.out.println(lst);
}
}
如果將ArrayListIterator類聲明為static，那么調(diào)用方式就不一樣了最仑。
public class MyArrayList<AnyType> implements Iterable<AnyType> {
private static final int DEFAULT_CAPACITY = 10;
private AnyType[] theItems;
...
public java.util.Iterator<AnyType> iterator() {
return new ArrayListIterator(this); // 傳入外部類對(duì)象引用
}
// 靜態(tài)內(nèi)部類
private static class ArrayListIterator implements java.util.Iterator<AnyType> {
private int current = 0;
private boolean okToRemove = false;
private MyArrayList<Anytype> theList; // 定義一個(gè)外部類成員變量
public ArrayListIterator (MyArrayList<Anytype> list){
theList = list; // 接受外部類對(duì)象初始化成員變量
}
public boolean hasNext() {
return current < theList.size(); // 用外部類對(duì)象調(diào)用外部類的方法
}
public AnyType next() {
if (!hasNext())
throw new java.util.NoSuchElementException();
okToRemove = true;
return theList.theItems[current++]; // 用外部類對(duì)象調(diào)用外部類的成員變量
}
public void remove() {
if (!okToRemove)
throw new IllegalStateException();
theList.remove(--current);
okToRemove = false;
}
}
LinkedList類的實(shí)現(xiàn)
- 維持一個(gè)頭結(jié)點(diǎn)和一個(gè)尾結(jié)點(diǎn)
- 表的大小
- modCount：代表自從構(gòu)造以來(lái)對(duì)鏈表所改變的次數(shù)藐俺。每次對(duì)add或者remove的調(diào)用都將更新modCount。其用處是泥彤，當(dāng)一個(gè)迭代器對(duì)象被建立時(shí)欲芹，它將存儲(chǔ)集合的modCount，對(duì)迭代器調(diào)用remove操作吟吝，將更新modCount菱父，同時(shí)鏈表的modCount也會(huì)同時(shí)被更新。這樣每次對(duì)迭代器方法next或者remove的調(diào)用都將驗(yàn)證該鏈表內(nèi)的當(dāng)前modCount和迭代器內(nèi)存儲(chǔ)的modCount是否一致剑逃，如果不一致浙宜，那么將拋出ConcurrentModificationException。
package com.corp.qiyun.datastruct;
/**
* LinkedList class implements a doubly-linked list.
*/
public class MyLinkedList<AnyType> implements Iterable<AnyType>
{
private int theSize;
private int modCount = 0;
private Node<AnyType> beginMarker;
private Node<AnyType> endMarker;
/**
* Construct an empty LinkedList.
*/
public MyLinkedList( )
{
doClear( );
}
private void clear( )
{
doClear( );
}
/**
* Change the size of this collection to zero.
*/
public void doClear( )
{
beginMarker = new Node<>( null, null, null );
endMarker = new Node<>( null, beginMarker, null );
beginMarker.next = endMarker;
theSize = 0;
modCount++;
}
/**
* Returns the number of items in this collection.
* @return the number of items in this collection.
*/
public int size()
{
return theSize;
}
public boolean isEmpty( )
{
return size() == 0;
}
/**
* Adds an item to this collection, at the end.
* @param x any object.
* @return true.
*/
public boolean add( AnyType x )
{
add( size(), x );
return true;
}
/**
* Adds an item to this collection, at specified position.
* Items at or after that position are slid one position higher.
* @param x any object.
* @param idx position to add at.
* @throws IndexOutOfBoundsException if idx is not between 0 and size(), inclusive.
*/
public void add( int idx, AnyType x )
{
addBefore( getNode( idx, 0, size() ), x );
}
/**
* Adds an item to this collection, at specified position p.
* Items at or after that position are slid one position higher.
* @param p Node to add before.
* @param x any object.
* @throws IndexOutOfBoundsException if idx is not between 0 and size(), inclusive.
*/
private void addBefore( Node<AnyType> p, AnyType x )
{
Node<AnyType> newNode = new Node<>( x, p.prev, p );
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;
modCount++;
}
/**
* Returns the item at position idx.
* @param idx the index to search in.
* @throws IndexOutOfBoundsException if index is out of range.
*/
public AnyType get( int idx )
{
return getNode( idx ).data;
}
/**
* Changes the item at position idx.
* @param idx the index to change.
* @param newVal the new value.
* @return the old value.
* @throws IndexOutOfBoundsException if index is out of range.
*/
public AnyType set( int idx, AnyType newVal )
{
Node<AnyType> p = getNode( idx );
AnyType oldVal = p.data;
p.data = newVal;
return oldVal;
}
/**
* Gets the Node at position idx, which must range from 0 to size() - 1.
* @param idx index to search at.
* @return internal node corresponding to idx.
* @throws IndexOutOfBoundsException if idx is not between 0 and size() - 1, inclusive.
*/
private Node<AnyType> getNode( int idx )
{
return getNode( idx, 0, size() - 1 );
}
/**
* Gets the Node at position idx, which must range from lower to upper.
* @param idx index to search at.
* @param lower lowest valid index.
* @param upper highest valid index.
* @return internal node corresponding to idx.
* @throws IndexOutOfBoundsException if idx is not between lower and upper, inclusive.
*/
private Node<AnyType> getNode( int idx, int lower, int upper )
{
Node<AnyType> p;
if( idx < lower || idx > upper )
throw new IndexOutOfBoundsException( "getNode index: " + idx + "; size: " + size() );
if( idx < size() / 2 )
{
p = beginMarker.next;
for( int i = 0; i < idx; i++ )
p = p.next;
}
else
{
p = endMarker;
for( int i = size(); i > idx; i-- )
p = p.prev;
}
return p;
}
/**
* Removes an item from this collection.
* @param idx the index of the object.
* @return the item was removed from the collection.
*/
public AnyType remove( int idx )
{
return remove( getNode( idx ) );
}
/**
* Removes the object contained in Node p.
* @param p the Node containing the object.
* @return the item was removed from the collection.
*/
private AnyType remove( Node<AnyType> p )
{
p.next.prev = p.prev;
p.prev.next = p.next;
theSize--;
modCount++;
return p.data;
}
/**
* Returns a String representation of this collection.
*/
public String toString( )
{
StringBuilder sb = new StringBuilder( "[ " );
for( AnyType x : this )
sb.append( x + " " );
sb.append( "]" );
return new String( sb );
}
/**
* Obtains an Iterator object used to traverse the collection.
* @return an iterator positioned prior to the first element.
*/
public java.util.Iterator<AnyType> iterator( )
{
return new LinkedListIterator( );
}
/**
* This is the implementation of the LinkedListIterator.
* It maintains a notion of a current position and of
* course the implicit reference to the MyLinkedList.
*/
private class LinkedListIterator implements java.util.Iterator<AnyType>
{
private Node<AnyType> current = beginMarker.next;
private int expectedModCount = modCount;
private boolean okToRemove = false;
public boolean hasNext( )
{
return current != endMarker;
}
public AnyType next( )
{
if( modCount != expectedModCount )
throw new java.util.ConcurrentModificationException( );
if( !hasNext( ) )
throw new java.util.NoSuchElementException( );
AnyType nextItem = current.data;
current = current.next;
okToRemove = true;
return nextItem;
}
public void remove( )
{
if( modCount != expectedModCount )
throw new java.util.ConcurrentModificationException( );
if( !okToRemove )
throw new IllegalStateException( );
MyLinkedList.this.remove( current.prev );
expectedModCount++;
okToRemove = false;
}
}
/**
* This is the doubly-linked list node.
*/
private static class Node<AnyType>
{
public Node( AnyType d, Node<AnyType> p, Node<AnyType> n )
{
data = d; prev = p; next = n;
}
public AnyType data;
public Node<AnyType> prev;
public Node<AnyType> next;
}
}
class TestLinkedList
{
public static void main( String [ ] args )
{
MyLinkedList<Integer> lst = new MyLinkedList<>( );
for( int i = 0; i < 10; i++ )
lst.add( i );
for( int i = 20; i < 30; i++ )
lst.add( 0, i );
lst.remove( 0 );
lst.remove( lst.size() - 1 );
System.out.println( lst );
java.util.Iterator<Integer> itr = lst.iterator( );
while( itr.hasNext( ) )
{
itr.next( );
itr.remove( );
System.out.println( lst );
}
}
}
棧ADT
棧模型
棧（stack）是限制插入和刪除只能在一個(gè)位置上進(jìn)行的表蛹磺，該位置是表的末端粟瞬，叫做棧頂。對(duì)棧的基本操作有進(jìn)棧（push）和出棧（pop）萤捆。棧的特性是后進(jìn)先出裙品。
棧的單鏈表實(shí)現(xiàn)
棧的第一種實(shí)現(xiàn)是使用單鏈表。通過(guò)在鏈表的頂端插入來(lái)實(shí)現(xiàn)push俗或，通過(guò)刪除表頂端元素來(lái)實(shí)現(xiàn)pop市怎。top操作只是考察表頂端元素并返回它的值。
public class MyStack<T> {
private LinkNode<T> top; // 棧頂指針
private Integer size;// 棧的當(dāng)前大小
public MyStack() {
size = 0;
}
public boolean isEmpty() {
return top == null;
}
public int getSize() {
return this.size;
}
public void push(T data) {
if(top == null){
top = new LinkNode<>(data);
size++;
return;
}
LinkNode<T> newNode = new LinkNode<T>(data);
newNode.setNext(top);
top = newNode;
size++;
}
public T peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return (T) top.getDate();
}
public T pop() {
T data = peek();
size--;
top = top.next;
return data;
}
public static class LinkNode<T> {
private T date;
private LinkNode next;
public LinkNode(T data){
date = data;
}
public T getDate() {
return date;
}
public void setDate(T date) {
this.date = date;
}
public LinkNode getNext() {
return next;
}
public void setNext(LinkNode next) {
this.next = next;
}
}
}
棧的數(shù)組實(shí)現(xiàn)
棧的數(shù)組實(shí)現(xiàn)是更流行的解決方案蕴侣。由于模仿ArrayList的add操作焰轻，因此相應(yīng)的實(shí)現(xiàn)方法非常簡(jiǎn)單。
public class MyStack<T> {
private static final int DEFAULT_CAPACITY = 10;
private T[] array;
private int size;
public MyStack(Class<T> type) {
// 泛型數(shù)組的實(shí)例化方法
array = (T[]) Array.newInstance(type, DEFAULT_CAPACITY); // 由于泛型擦除, 不能使用 new T[];
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public void enlarge() {
array = Arrays.copyOf(array, array.length * 2);
}
public T peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return array[size - 1];
}
public T pop() {
T top = peek();
size--;
return top;
}
public void push(T element) {
if (size == array.length) {
enlarge();
}
array[size++] = element;
}
public static void main(String[] args) {
MyStack stack = new MyStack(Integer.class);
System.out.println(stack.isEmpty());
for(int i=0; i<10; i++){
stack.push(i);
}
stack.push(10);
System.out.println(stack.pop());
System.out.println(stack.pop());
stack.push(22);
System.out.println(stack.pop());
}
應(yīng)用
- 平衡符號(hào)
舉例說(shuō)明："[()]"是合法的昆雀，"[(])"是非法的辱志。
算法：做一個(gè)空棧。讀入字符直到文件結(jié)尾狞膘。如果字符是一個(gè)開(kāi)放符號(hào)揩懒，則將其推入棧中。如果字符是一個(gè)封閉符號(hào)挽封，則當(dāng)棧是空時(shí)報(bào)錯(cuò)已球，否則將棧頂元素出棧，如果彈出的棧頂元素不是對(duì)應(yīng)的開(kāi)放符號(hào)，則報(bào)錯(cuò)智亮。在文件結(jié)尾忆某，如果棧非空則報(bào)錯(cuò)。 - 中綴到后綴的轉(zhuǎn)換
中綴表達(dá)式：a + b * c + (d * e + f) * g
后綴表達(dá)式：a b c * + d e * f + g * +
轉(zhuǎn)換算法：1）遍歷中綴表達(dá)式阔蛉，遇到操作數(shù)直接輸出弃舒；2）遇到操作符，入棧状原，入棧前將依次彈出棧中所有優(yōu)先級(jí)比即將入棧的操作符的優(yōu)先級(jí)高或者相等的操作符聋呢；3）特例：左括號(hào)優(yōu)先級(jí)最高，但左括號(hào)只有在遍歷到右括號(hào)時(shí)才會(huì)出棧颠区；當(dāng)遍歷到右括號(hào)時(shí)削锰，彈出棧頂至左括號(hào)之間的所有操作符；4）左毕莱、右括號(hào)出棧時(shí)器贩，不輸出；所以遍歷到右括號(hào)央串，只需按規(guī)則出棧元素即可磨澡，右括號(hào)本身不需入棧碗啄。
后綴表達(dá)式的作用：通過(guò)后綴表達(dá)式质和，利用棧，可以很容易計(jì)算出對(duì)應(yīng)中綴表達(dá)式的值稚字。 - 后綴表達(dá)式
利用后綴表達(dá)式計(jì)算值的算法：使用棧饲宿；遇到一個(gè)操作數(shù)，將其入棧胆描；遇到一個(gè)運(yùn)算符瘫想，從棧頂彈出兩個(gè)操作數(shù)，計(jì)算之后昌讲，將結(jié)果入棧国夜；遍歷完成之后，棧中只剩一個(gè)數(shù)短绸，即最后的結(jié)果车吹。
優(yōu)點(diǎn)：計(jì)算一個(gè)后綴表達(dá)式花費(fèi)的時(shí)間是O(N)，并且在計(jì)算時(shí)醋闭，只需遵循上面的算法窄驹，沒(méi)有必要知道任何優(yōu)先的規(guī)則，計(jì)算非常簡(jiǎn)單证逻。 - 方法調(diào)用
方法調(diào)用的過(guò)程乐埠，就是棧幀入棧和出棧的過(guò)程。
隊(duì)列ADT
隊(duì)列模型
隊(duì)列也是表，使用隊(duì)列時(shí)丈咐，插入在一端進(jìn)行而刪除則在另一端進(jìn)行瑞眼。隊(duì)列的基本操作是入隊(duì)（enqueue）和出隊(duì)（dequeue）；入隊(duì)即在表的末端（隊(duì)尾rear）插入一個(gè)元素棵逊，出隊(duì)即刪除并返回在表的開(kāi)頭（隊(duì)頭front）的元素负拟。
隊(duì)列的數(shù)組實(shí)現(xiàn)
- 循環(huán)數(shù)組：head或者tail每次加1之后需要對(duì)array.length取模
- head出隊(duì)列，tail入隊(duì)列歹河，初始化時(shí)掩浙，tail要比head索引小1。
- 以下隊(duì)列不支持動(dòng)態(tài)擴(kuò)容秸歧，不支持多線程
public class MyCircularQueue<T> {
private T[] array;
private int head;
private int tail;
private int size;
public MyCircularQueue(Class<T> type, int capacity) {
array = (T[]) Array.newInstance(type, capacity);
head = 0;
tail = array.length - 1; // or tail = -1
size = 0;
}
public boolean poll(T value) {
if (isFull()) {
return false;
}
tail = (tail + 1) % array.length;
array[tail] = value;
size++;
return true;
}
public T add() {
if (isEmpty()) {
return null;
}
T element = array[head];
head = (head + 1) % array.length;
size--;
return element;
}
public T front() {
if (isEmpty() == true) {
return null;
}
return array[head];
}
public T rear() {
if (isEmpty() == true) {
return null;
}
return array[tail];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == array.length;
}
}
隊(duì)列的單鏈表實(shí)現(xiàn)
- 維護(hù)一個(gè)dummyHead啞節(jié)點(diǎn)厨姚，指向頭元素的前一個(gè)節(jié)點(diǎn)；維護(hù)一個(gè)tail節(jié)點(diǎn)键菱，指向尾元素谬墙；
- 加入節(jié)點(diǎn)，成為tail的next節(jié)點(diǎn)经备，tail再指向加入的新節(jié)點(diǎn)拭抬；
- 移除節(jié)點(diǎn)，返回dummyHead節(jié)點(diǎn)的next節(jié)點(diǎn)元素（即頭元素）侵蒙，然后將dummyHead.next指向dummyHead.next.next節(jié)點(diǎn)造虎；注意，如果dummyHead.next.next節(jié)點(diǎn)為null纷闺，即剛剛刪除的元素為最后一個(gè)元素算凿，需要將tail指向dummyHead。
public class MyQueue<T> {
private LNode dummyHead;
private LNode tail;
private Integer size;
public MyQueue() {
dummyHead = new LNode<T>(); // dummyHead指向首元素的前一個(gè)節(jié)點(diǎn)
tail = dummyHead; // tail指向尾元素, 當(dāng)tail == dummyHead時(shí), 說(shuō)明隊(duì)列為空
size = 0;
}
public MyQueue clearQueue() {
tail = dummyHead;
size = 0;
return this;
}
public Boolean isEmpty() {
return tail == dummyHead; // 或者 return size == 0;
}
public Integer getSize() {
return size;
}
public T getDummyHead() {
return (T) dummyHead.getNext().getData();
}
public Boolean add(T e) {
//入隊(duì) 從隊(duì)尾入
LNode newNode = new LNode<>(e, null);
tail.setNext(newNode);
tail = newNode;
size++;
return Boolean.TRUE;
}
public T DeQueue() {
// 刪除的時(shí)候, 如果是最后一個(gè)元素, 這個(gè)時(shí)候尾指針需要調(diào)整為指向頭節(jié)點(diǎn)
if (dummyHead.getNext().getNext() == null) {
T e = (T) dummyHead.getNext().getData();
dummyHead.setNext(null);
tail = dummyHead;
return e;
}
T e = (T) dummyHead.getNext().getData();
dummyHead.setNext(dummyHead.getNext().getNext());
size--;
return e;
}
static class LNode<T> {
private T data;
private LNode next;
public LNode() {
}
public LNode(T data, LNode next) {
this.data = data;
this.next = next;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public LNode getNext() {
return next;
}
public void setNext(LNode next) {
this.next = next;
}
}
public static void main(String[] args) {
MyQueue<Integer> linkedQueue = new MyQueue<>();
linkedQueue.add(1);
linkedQueue.add(2);
linkedQueue.add(3);
Integer size = linkedQueue.size;
for (Integer integer = 0; integer < size; integer++) {
System.out.println(linkedQueue.DeQueue());
}
System.out.println(linkedQueue.isEmpty());
}
}
隊(duì)列應(yīng)用
廣度優(yōu)先算法可使用隊(duì)列實(shí)現(xiàn)犁功；
深度優(yōu)先算法可使用棧實(shí)現(xiàn)氓轰；
