堆疊是一種先進后出的資料結構，以下是其常見操作：
（1)清空（clear)
堆疊的清空操作將堆疊頂指標TOP置為-1，表示堆疊中沒有元素，
void clear() { TOP = -1; }
（2)獲取堆疊內元素個數(size)
由于堆疊項指標TOP始終指向堆疊頂元素，而陣列下標從0開始、因此堆疊內元素的數為TOP+1
int size() { return TOP + 1; }
(3）判空(empty）
由堆疊頂指標TOP的定義可知，僅當TOP== -1時為堆疊空，回傳true；否則，回傳false，
bool empty() { if (TOP == -1) return true; else return false; }
(4)進堆疊(push)
push(x)操作將元素x置于堆疊頂，由于堆疊頂指標TOP指向堆疊頂元素，因此需要先把TOP
加1，然后再把x存入TOP指向的位置，
void push() { st[++TOP] = x; }
(5)出堆疊(pop)
pop()操作將堆疊頂元素出堆疊，而事實上可以直接將堆疊頂指標TOP減1來實作這個效果，
void pop(){ TOP--; }
(6)取堆疊頂元素(top）
由于堆疊頂指標 TOP始終指向堆疊頂元素，因此可以st[TOP]即為堆疊頂元素，
int top() { return st[TOP]; }
(7)堆疊的清空
使用一個while回圈反復pop出元素直至堆疊空，
while (TOP != -1) { st.pop(); }
或者重新定義一個堆疊以變相的實作堆疊的清空，
佇列是一種先進先出的資料結構，區別于堆疊，
應當注意到，佇列總是從隊尾加入元素，而從隊首移除元素，并且滿足先進先出的規則，
一般來說，需要一個隊首指標front來指向隊首元素的前一個位置，而使用一個隊尾指標rear來指向隊尾元素，
和堆疊類似，當使用陣列來實作佇列時，隊首指標front 和隊尾指標rear 為int型變數(陣列下標從0開始）；而當使用鏈表來實作佇列時，則為int* 型變數的指標，
這樣當使用陣列來實作上面的例子時，隊首指標front和隊尾指標rear的指向情況如圖7 - 3所示，
接下來介紹佇列的常用操作，包括清空（clear)、獲取佇列內元素的個數(size)、判空(empty)、入隊（push)、出隊(pop)、取隊首元素（get_front）、取隊尾元素（get_rear)等，
下面將使用陣列q[]來實作佇列，而int型變數front存放隊首元素的前一個元素的下標、 rear存放隊尾元素的下標（陣列下標從0開始），下面對常見操作進行示范實作：
(1）清空(clear)
使用陣列來實作佇列時，初始狀態為front = -1、rear = -1，圖中第一步rear指向0是因為此時佇列中已經有一個元素了，如果沒有元素，rear應當是指向 - 1位置的，
void clear() { front = rear = -1; }
(2)獲取佇列內元素的個數（size)
顯然rear - front即為佇列內元素的個數，這一點可以從圖中很容易看出來，
int size() { return rear - front; }
(3)判空(empty）
判定佇列為空的條件為front == rear，
bool empty() { if (front = rear) return true; else return false; }
(4)入隊(push)
由于隊尾指標rear指向隊尾元素，因此把元素入隊時，需要先把rear加1，然后再存放到rear指向的位置
bool empty() { if (front = rear) return true; else return false; }
(5)出隊（pop）
可以直接把隊首指標front加1來實作出隊的效果
void pop(int x) { front++; }
(6)取隊首元素(get_front）
由于隊首指標front指向的是隊首元素的前一個元素，因此font + 1才是隊首元素的位置
int get_front() { return q[front + 1]; }
(7)取隊尾元素(get_rear)
由于隊尾指標 rear指向的是隊尾元素，因此可以直接訪問rear的位置，
int get_rear() { return q[rear]; }
(8)佇列的清空
與堆疊類似，出隊操作和取隊首、隊尾元素操作必須在佇列非空的情形下才能使用，因此在使用pop()函式、get_front()函式、get_ rear()函式之前必須先使用empty()函式判斷佇列是否為空，
同樣的，可以使用C++STL中的queue容器來非常容易地使用佇列，STL中的queue實作好了佇列的常用操作，當需要使用時，只需直接呼叫函式即可，和與堆疊一樣，STL中也沒有實作佇列的清空，所以如果需要實作佇列的清空，可以用一個while回圈反復pop出元素直到佇列為空，也就是下面這樣的寫法：
while (!q.empty()){ q.pop(); }
而更常用的方法是重新定義一個佇列以實作佇列的清空，因為這并不需要花很多時間，
STL的 queue進行定義的時間復雜度和定義slack一樣都是O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/280176.html
標籤：其他