棧與遞歸

• 二、棧與遞歸
• • 1、棧的概念
  • 2、代碼實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)
  • 3、棧stack< T >的方法總結(jié)
  • 4、火車出入站問題
  • 5、遞歸的概念
  • 6、遞歸方法求n的階乘
  • 7、漢諾塔問題

二、棧與遞歸

1、棧的概念

棧是滿足一定約束的線性數(shù)據(jù)結(jié)構(gòu)，約束是：只允許在棧的一端插入或刪除元素，這一端被稱為棧頂，另一端稱為棧底。
向棧中壓入元素，稱為push;從棧頂彈出元素，稱為pop。
棧的重要性質(zhì)是先進(jìn)先出：越早進(jìn)入棧的元素，出來的時(shí)間越晚。
通常用top指示棧頂?shù)奈恢谩?/p>

2、代碼實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)

#include<iostream> using namespace std; struct Stack{//把數(shù)據(jù)結(jié)構(gòu)封裝寫成stuck,便于代碼復(fù)用和調(diào)試int data[10000];int top = -1;//初始時(shí)棧中沒有元素，top值為-1void push(int x){//入棧top++;if(top < 10000){data[top] = x;}else{ //避免插入元素導(dǎo)致數(shù)組訪問越界而棧溢出top--;count <<"stack overflow" <<endl;}}void pop(){//出棧if(top >= 0){top--;}}int topval(){if(top >= 0){return data[top];//獲取當(dāng)前棧頂元素的值}} }; int main(){Stack s;for(int i = 1; i <= 10; i++){s.push(i);}return 0; }

標(biāo)準(zhǔn)庫里面的stack在頭文件< stack >里面
stack< T > s定義一個(gè)存儲(chǔ)T類型數(shù)據(jù)的棧s。

3、棧stack< T >的方法總結(jié)

方法功能參數(shù)類型返回值類型

push	壓入元素到棧頂	T類型	無
pop	彈出棧頂元素	無	無
top	返回棧頂元素	無	T類型
empty	棧是否為空	無	bool類型：false表示不為空，true表示棧為空
size	棧的元素個(gè)數(shù)	無	非負(fù)整數(shù)（size_t類型）

4、火車出入站問題

#include<iostream> #include<vector> #include<stack> using namespace std; int main(){int n;cin >> n;vector<int> a(n);for(int i = 0; i < n; i++){cin >> a[i];}stack<int> s;int cur = 1;//記錄當(dāng)前沒有壓入棧中的元素的起始位置bool f = 1;for(int i = 0;i < n;i++){//如果棧頂不等于a[i]，就一直向棧頂push元素while(s.empty()||s.top() != a[i] && cur <= n){s.push(cur);cur++;}if(s.empty() || s.top()!=a[i]){f = 0;break;}else{s.pop();}}if(f){cout << "legal" << endl;}else{cout << "illegal" << endl;}return 0; }

5、遞歸的概念

遞歸就是函數(shù)調(diào)用函數(shù)自身，用于解決有重復(fù)子問題的問題。
直接遞歸 求 n! ，n!=n*(n-1)!

int factorial(int n){return n * factorial(n - 1); }

6、遞歸方法求n的階乘

#include<iostream> using namespace std; long long factorial(int n){if(n <= 1){return 1;}return n * factorial(n-1); } int main(){int n;cin >> n;cout << factorial(n) << endl;return 0; }

7、漢諾塔問題

#include<iostream> #include<stack> using namespace std; stack<int> S[3]; void move(int x,int y){//棧x的top()移動(dòng)到棧y的棧頂int temp = S[x].top();S[x].pop();S[y].push(temp);cout << x << "-->" << y << endl; } void hanio(int A,int b,int c,int n){//從A經(jīng)B將n個(gè)盤子移到Cif(n == 1){//終止條件move(A,C);}hanio(A,C,B,n-1);move(A,C);hanio(B,A,C,n-1); } int main(){stack<int> S[3];int n;cin >> n;for(int i = n;i >= 1;i--){S[0].push(i);}hanio(0,1,2,n);while(!S[2].empty()){cout << S[2].top() << " ";S[2].pop();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的LQ训练营(C++)学习笔记_栈与递归的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。