C++ 棧和典型迷宮問題
C++ 棧和迷宮問題
1. 前言
棧是一種受限的數據結構，要求在存儲數據時遵循先進後出（Last In First Out）的原則。可以把棧看成只有一個口子的桶子，進和出都是走的這個口子（也稱為棧頂），封閉的另一端稱為棧底。
什麼時候會用到棧？
現實世界裡，類似於棧的存儲現象很普通。
當我們需要同時存儲經常和不經常使用的物品時，我們總是把不經常使用的物品先放到箱子的最裡層，把經常使用的物品放到箱子的最外層。這是典型的棧存儲思想。
在編程的世界裡，可把稍後要用的數據存儲在棧底，把當前需要用的數據存儲在棧頂。或者說，如果數據A依賴數據B，也就是必須先處理完B後才能處理A。可以把數據B存儲在棧頂，數據A存儲在棧底。
棧的抽象數據類型：
棧最基本的操作是入棧、出棧，除此之外，還有查看棧頂、檢查棧是為空、檢查棧已滿……操作。
棧有 2 種實現方案：
- 順序存儲。
- 鏈式存儲。
2. 順序存儲
順序存儲指使用數組模擬棧實現。
2.1 初始化棧
數組是開放式的數據存儲結構，為了保證向數組中存儲數據時，遵循棧的存儲理念，棧類需要做 2 點準備：
- 對外隱藏數組(私有化)。
- 棧內部確定存儲位置。入口（棧頂）位置可以從數組的首地址開始，也可以從數組的尾地址開始。
template <typename T>
class Stack {
private:
//數組地址（這裡使用動態創建數組）
int *items;
//用來控制數組中的有效存儲位置（位置控制指針）
int *index;
//棧的實際數據的大小
int size=0;
public:
//構造函數
Stack(int stackSize) {
this->items=new T[stackSize];
this->size=stackSize;
//從數組的首地址開始存儲
this->index=this->items;
}
//入棧
void push(T data);
//出棧
T pop();
//查看棧頂數據
T getTop();
//是否為空
bool isEmpty();
//是否滿了
bool isFill();
};
2.2 棧的狀態
棧有 2 種狀態：
-
可用：入棧時，棧中有空位置，出棧時，棧中有數據，此時棧為可用狀態。
-
不可用：出棧時，如果棧為空，或入棧時，棧已滿，此時棧為不可用狀態。
為了保證入棧和出棧能正常工作，先要實現狀態檢查函數。
2.2.1 是否為空
這個演算法很簡單，只需要檢查位置控制指針是不是為構建棧時的最初狀態。
//是否為空
bool isEmpty() {
return this->items==this->index;
}
2.2.2 是否已滿
只需要檢查棧的大小是否和數組的實際存儲大小相等。或者檢查位置控制指針是否已經到達數組尾部。
//是否滿了
bool isFill(){
return this->index-this->items==this->size;
}
2.3 入棧和出棧
2.3.1 入棧
入棧操作需要檢查棧是否有空位置。如果有，存儲在位置控制指針所指向位置，然後讓位置控制指針指向下一個可用位置。
//入棧
bool push(T data) {
if(this->isFill()) {
//棧滿了，不能存儲
return 0;
}
//存儲至位置控制指針所指位置
*(this->index)=data;
//移動
this->index++;
this->size++;
return 1;
}
2.3.2 出棧
出棧時需要檢查棧是否為空，為空時，出棧失敗。不為空時，把位置控制指針向後移動到數據所在位置，然後得出數據。
//出棧
T pop() {
if(this->isEmpty()) {
//棧為空
return NULL;
}
this->index--;
this->size--;
return *(this->index);
}
2.3.3 其它函數
返回棧中實際數據的函數。
//得到棧中的實際數據大小
int getSize(){
return this->index-this->items;
}
僅查詢棧頂數據，不從棧中刪除數據。
//查看棧頂數據
T getTop() {
if(this->isEmpty()) {
return NULL;
}
return *(this->index-1);
}
2.3.4 測試入棧出棧
棧存儲會導致存入的順序和輸出的順序是相反的。
int main(int argc, char** argv) {
Stack<int> myStack(10);
//向棧中壓入數據
for(int i=0; i<15; i++) {
myStack.push(i);
}
int top=myStack.getTop();
cout<<"棧頂數據："<<top<<endl;
int size=myStack.getSize();
cout<<"棧中數據的大小:"<<size<<endl;
cout<<"輸出棧中所有數據："<<endl;
for(int i=0; i<15; i++) {
cout<<myStack.pop()<<endl;
}
return 0;
}
輸出結果：
向棧中添加了 15 次數據，因棧的容量只有 10，最終輸出只有 10 個有效數據。最後的 5 個 0 表示出棧失敗。
2.4 小結
因順序棧基於數組，實現過程相對而言較簡單，但受限於數組的物理特性，在壓入的數據多於棧內部大小時，會出現數據溢出問題。雖然可以採用擴容演算法，但同時增加了程式碼的維護量。
3. 鏈式存儲
鏈式存儲是基於結點的存儲方式，數據在物理結構上是不連續的。鏈表存儲的優點是可以自行動態擴容，不需要演算法層面的支援。
鏈式存儲的流程：
3.1 結點類型
結點類型和單鏈表相同，只需要數據域和存儲下一個結點的指針域。
template <typename T>
class Node {
public:
T data;
Node *next;
Node(T data) {
this->data=data;
this->next=NULL;
}
};
3.2 初始化
創建鏈表時，通常會增加一個空白頭結點作為標誌結點，在構建鏈表棧時是不需要的。
template <typename T>
class Stack {
private:
//頭結點指針
Node *head;
//棧中實際數據的大小
int size;
public:
//構造函數
Stack() {
//不需要空白頭結點
this->head=NULL;
this->size=0;
}
//入棧
bool push(T data) ;
//出棧
T pop() ;
//查看棧頂數據
T getTop() ;
//得到棧中的實際數據大小
int getSize(){
return this->size;
}
};
3.3 入棧、出棧
鏈表的數據插入方案有頭部插入和尾部插入兩種方案。在模擬棧時須保證數據的維護只能在一端進行，可以有 2 種方案：
- 數據的插入和刪除在頭部進行。
- 數據的插入和刪除在尾部進行。
本文以頭部插入實現入棧和出棧演算法。
3.3.1 入棧
鏈式棧不需要考慮棧是已經滿的問題。入棧實現流程：
- 創建一個新結點對象。
- 原來的頭結點成為新結點的後驅結點。
- 新結點成為頭結點。
//入棧
bool push(T data) {
//創建新結點
Node<T> *newNode=new Node<T>(data);
if(newNode){
//原來的頭結點成為新結點的後驅
newNode->next=this->head;
//新結點成為頭結點
this->head=newNode;
this->size++;
return 1;
}else{
return 0;
}
}
3.3.2 出棧
鏈式棧的出棧操作需要判斷棧是否為空。如果不為空剛取出頭結點數據，並把結點從鏈表中刪除。實現流程：
//出棧
T pop() {
Node<T> * node=NULL;
T data;
if(this->head){
//獲取頭結點
node=this->head;
//得到數據
data=node->data;
//原來頭結點的後驅成為新頭結點
this->head=this->head->next;
//刪除結點
delete node;
this->size--;
return data;
}else{
//鏈表為空
return NULL;
}
}
為了方便查詢棧頂數據，需要提供一個查詢棧頂數據的操作。
//查看棧頂數據
T getTop() {
if(this->head) {
return this->head->data;
} else {
return NULL;
}
}
3.3.3 測試鏈式棧
int main(int argc, char** argv) {
Stack<int> stack ;
//入棧
for(int i=0; i<10; i++) {
stack.push(i);
}
cout<<"棧中實際數據大小："<<stack.getSize()<<endl;
cout<<"查詢棧頂數據:"<<stack.getTop()<<endl;
//出棧
for(int i=0; i<10; i++) {
cout<<stack.pop()<<endl;
}
return 0;
}
執行結果：
4. STL 中的棧
實際應用時，可以使用STL的stack容器。除了上述的基本操作外，stack容器還提供比較操作，這些操作可以被用於棧與棧之間的比較， 相等指棧有相同的元素並有著相同的順序。
#include <iostream>
#include <stack>
using namespace std;
int main(int argc, char** argv) {
stack<int> myStack;
//入棧
for(int i=0;i<5;i++){
myStack.push(i);
}
cout<<"棧中數據大小:"<<myStack.size()<<endl;
//出棧
for(int i=0;i<4;i++) {
cout<<"棧頂數據："<<myStack.top()<<endl;
myStack.pop();
}
cout<<"棧頂數據："<<myStack.top()<<endl;
stack<int> myStack_;
myStack_.push(0);
bool res= myStack_==myStack;
cout<<"比較結果："<<res<<endl;
return 0;
}
輸出結果：
5. 棧的應用
總是在想，如果沒有棧，編程將如何進行，可想而知，棧的重要性。函數調用、遞歸演算法……無處不有棧的身影。下面將通過一個典型的案例加深對棧的理解。
5.1 迷宮問題
迷宮問題描述：在一個錯綜複雜的迷宮世界，有一個入口，有一個出口。在入口位置有一隻小老鼠，出口位置有一塊乳酪。要求通過編碼的方式幫助小老鼠在入口到出口之間找到一個可行的路徑。
迷宮問題是一類典型問題，解決此類問題的關鍵思想包括：
- 試探過程：每到達一個當前位置（第一個當前位置為入口），記錄此當前位置四周可嘗試的其它位置，然後選擇其中一個位置作為當前位置嘗試著繼續前進。
如下表格，設值為0的單元格為可通行，1為不可通行。值標識為紅色的單元格表示當前位置，在繼續前進時，記錄其左、右、下三個可行位置。並選擇右邊位置為新的當前位置。
- 回溯過程：當在前進時被阻礙後，退到記錄表中下一個可行位置再試。重複試探再回溯至到找到出口。
如上圖所示後繼續選擇右行，則發現被阻礙。
這時就需要在已經存儲的可行位置選擇一個，這步操作稱為回溯。
很明顯，每次記錄的可嘗試位置是在回溯後使用的，符合先進後出的存儲理念。棧在迷宮問題中用來存儲可試探的位置。
實現流程：
- 使用二維數組模擬迷宮。在二維數組中用
0表示可通行，1表示不可通行。
#include <iostream>
#include <stack>
#include <vector>
//全局聲明
int nums[10][10];
- 初始化迷宮。為了簡化問題，會把二維數組的第一行和最後一行，第一列和最一列中的所有單元格賦值
1，表示牆面。
如下圖，設置入口位置(1,1)、出口位置為(8,8)。
//全局聲明
int nums[10][10]= {
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,1,1,1,1,1},
{1,1,0,1,0,0,1,1,1,1},
{1,1,0,1,0,0,0,0,1,1},
{1,1,0,0,0,0,1,0,1,1},
{1,1,1,1,0,0,1,0,1,1},
{1,1,0,0,0,0,1,0,1,1},
{1,1,1,1,0,0,1,0,1,1},
{1,1,0,0,0,1,1,0,0,1},
{1,1,1,1,1,1,1,1,1,1},
};
對於二維數組中的任一位置有左、下、右、上 4 個方向，當前位置的坐標與 4個方位的坐標關係如下圖所示：
這裡定義一個方向結構體，用來存儲 4 個方位的增量資訊，便於計算。
//方向
struct Direction{
//x 方向增量
int xOffset;
//y 方向增量
int yOffset;
};
並且創建 Direction類型數組，用於保存 4 個方向的增量資訊。
//全局聲明
Direction dirs[4]={ {0,1},{1,0},{0,-1},{-1,0} };
方向資訊，為快速找到當前位置周邊的坐標提供了便利。為了存儲坐標，這裡需要一個坐標結構體：
struct Position {
//x坐標
int x;
//y坐標
int y;
//無參構造
Position() {
}
//有參構造
Position(int x,int y) {
this->x=x;
this->y=y;
}
//判斷 2 個坐標是不是同一個位置
bool equals(Position pos) {
return this->x==pos.x && this->y==pos.y;
}
//自我顯示
void desc() {
cout<<"x:"<<x<<"y:"<<y<<endl;
}
};
- 創建棧。
用來存儲當前位置周邊所有可以通行的位置。
這裡使用
STL提供的stack容器。別忘記包含<stack>頭文件。
//全局聲明
stack<Position> myStack;
- 核心搜索演算法。
所有核心程式碼直接編寫在 main 函數中，下面程式碼中使用到了 vector，存儲已經搜索到的位置。還有一點要注意，當某個位置被 壓入棧中後，要標識為被壓入，這裡把此位置值設置為 -1。
int main(int argc, char** argv) {
//起點位置
Position startPos(1,1);
//終點位置
Position endPos(8,8);
//保存走過的位置
vector<Position> paths;
//向棧中壓入起始位置
mazeStack.push(startPos);
//設置起始位置為已經訪問過
maze[startPos.x][startPos.y]=-1;
//臨時存儲棧頂位置
Position tmp;
while(!mazeStack.empty()) {
//取出棧頂位置
tmp=mazeStack.top();
//刪除棧頂數據
mazeStack.pop();
//當前搜索位置存儲在 vector 中
paths.push_back(tmp);
//判斷是否已經到了終點
if (tmp.equals(endPos)) {
//到達終點，結束
break;
} else {
for(int i=0; i<4; i++) {
//查找當前位置 4 個方向有無可通行位置,並壓入棧中
Position nextPos(tmp.x+dirs[i].xOffset,tmp.y+dirs[i].yOffset);
if(maze[nextPos.x][nextPos.y]==0) {
mazeStack.push(nextPos);
//標識為已經被壓入，避免重複壓入
maze[nextPos.x][nextPos.y]=-1;
}
}
}
}
//顯示搜索路徑
for(int i=0;i<paths.size();i++){
tmp=paths[i];
tmp.desc();
}
return 0;
}
執行結果：
在演示圖中標註出搜索路徑，可驗證搜索到的路徑是可行的。
6. 總結
本文編碼實現了順序棧和鏈式棧，簡要介紹了STL中的stack容品，並使用它解決了典型的迷宮問題。
