棧與隊(duì)列_基礎(chǔ)1

棧與隊(duì)列
P1739 表達(dá)式括號(hào)匹配
P1449 后綴表達(dá)式
P1981 [NOIP2013 普及組] 表達(dá)式求值
B3616 【模板】隊(duì)列
P1996 約瑟夫問題

棧與隊(duì)列

棧：具有后進(jìn)先出（Last In First Out）特性的線性表

//stack  棧
int sta[N], head=0;  // 數(shù)組模擬棧，head 指向棧頂 

sta[++head] = x; // 入棧
--head;          // 出棧 
if(head)         // 棧不為空
sta[head];       // 棧頂

隊(duì)列：具有先進(jìn)先出（First In First Out）特性的線性表

// queue 隊(duì)列， front 隊(duì)首， tail 隊(duì)尾 
int que[N], front=0, tail=-1;

que[++tail] = x; // 入隊(duì)
++front;         // 出隊(duì)
que[front];      //隊(duì)頭
if(front <= tail) //隊(duì)列不為空

P1739 表達(dá)式括號(hào)匹配

表達(dá)式有英文字母（小寫）、運(yùn)算符（+、-、*、/）和左右小（圓）括號(hào)構(gòu)成，以 @ 作為表達(dá)式的結(jié)束符。請(qǐng)編寫一個(gè)程序檢查表達(dá)式中的左右圓括號(hào)是否匹配；

若匹配，則輸出 YES；
否則輸出 NO。

表達(dá)式長(zhǎng)度小于 $255$，左圓括號(hào)少于 $20$ 個(gè)。

樣例輸入

2*(x+y)/(1-x)@

樣例輸出

YES

分析

統(tǒng)計(jì)左括號(hào)的數(shù)量 h，如果出現(xiàn)右括號(hào)，那么左括號(hào)的數(shù)量 h-1。
合法的情況下：h 永遠(yuǎn) ≥0，且最后 h=0。

參考程序

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
int main(){
    string s; cin>>s;
    int h=0;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='(') h++;
        else if(s[i]==')'){
            h--;
            if(h < 0) break;
        }
    }
    if(h==0) cout<<"YES";
    else cout<<"NO";
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,INF=0x3f3f3f3f;
char sta[N];  //stack  棧
int head=0;  // 數(shù)組模擬棧，head 指向棧頂 

int main(){
    string s; cin>>s;
    bool flag=1; // 假設(shè)原本括號(hào)是匹配的 
    for(int i=0; i<s.size(); i++){
        if(s[i]=='(') sta[++head]=s[i]; 
        else if(s[i]==')'){
            if(head) head--; // 出棧
            else { // 空棧， 無法出棧，括號(hào)不匹配 
                flag=0; break;
            }
        }
    }
    if(head) flag=0;
    if(flag) cout<<"YES";
    else cout<<"NO";
    return 0;
}

P1449 后綴表達(dá)式

所謂后綴表達(dá)式是指這樣的一個(gè)表達(dá)式：式中不再引用括號(hào)，運(yùn)算符號(hào)放在兩個(gè)運(yùn)算對(duì)象之后，所有計(jì)算按運(yùn)算符號(hào)出現(xiàn)的順序，嚴(yán)格地由左而右新進(jìn)行（不用考慮運(yùn)算符的優(yōu)先級(jí)）。

如：$\texttt{3*(5-2)+7}$ 對(duì)應(yīng)的后綴表達(dá)式為：$\texttt{3.5.2.-*7.+@}$。在該式中，@ 為表達(dá)式的結(jié)束符號(hào)。. 為操作數(shù)的結(jié)束符號(hào)。

數(shù)據(jù)保證，$1 \leq |s| \leq 50$，答案和計(jì)算過程中的每一個(gè)值的絕對(duì)值不超過 $10^9$。

樣例輸入

3.5.2.-*7.+@

樣例輸出

參考程序

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,INF=0x3f3f3f3f;

int sta[N], head=0, t=0;
int main(){
    string s; cin>>s; 
    for(int i=0; i<s.size(); i++){
        if(s[i] >='0' & s[i]<='9')
          t = t*10 + s[i]-'0';
        else if(s[i]=='.'){
            sta[++head] = t; t=0; // t需要?dú)w 0 
        }else {
            if(s[i]=='@') break; // 退出放最前面 
            int a=sta[head]; head--;
            int b=sta[head]; head--;
            if(s[i]=='+') sta[++head] = a+b;
            if(s[i]=='-') sta[++head] = b-a;//注意先后
            if(s[i]=='*') sta[++head] = a*b;
            if(s[i]=='/') sta[++head] = b/a;
        }
    }
    cout<<sta[head];
    return 0;
}

P1981 [NOIP2013 普及組] 表達(dá)式求值

給定一個(gè)只包含加法和乘法的算術(shù)表達(dá)式，請(qǐng)你編程計(jì)算表達(dá)式的值。

輸入一行，為需要你計(jì)算的表達(dá)式，所有參與運(yùn)算的數(shù)字均為 $0$ 到 $2^{31}-1$ 之間的整數(shù)。

輸入數(shù)據(jù)保證這一行只有 $0-9$、$+$、$ \times$ 這 $12 $種字符。

對(duì)于 $100\%$ 的數(shù)據(jù)，$0≤$ 表達(dá)式中加法運(yùn)算符和乘法運(yùn)算符的總數(shù) $≤100000$。

注意：當(dāng)答案長(zhǎng)度多于 $4$ 位時(shí)，請(qǐng)只輸出最后 $ 4$ 位，前導(dǎo) $ 0$ 不輸出。

樣例輸入

1+1*3+4

樣例輸出

參考程序

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,INF=0x3f3f3f3f;
LL sta[N], head=0, mod=1e4;
// (a+b) % p = (a%p+b%p) % p;
int main(){
    LL a,b; char ch;
    cin>>a;   sta[++head]=a%mod;
    while(cin>>ch>>b){
        if(ch=='+') sta[++head]=b%mod;
        if(ch=='*'){
            a = sta[head--];
            sta[++head] = a*b%mod;
        }
    }
    LL res=0;
    for(int i=1; i<=head; i++) res=(res+sta[i])%mod;
    cout<<res;
    return 0;
}

B3616 【模板】隊(duì)列

請(qǐng)你實(shí)現(xiàn)一個(gè)隊(duì)列（queue），支持如下操作：

push(x)：向隊(duì)列中加入一個(gè)數(shù) $x$。
pop()：將隊(duì)首彈出。如果此時(shí)隊(duì)列為空，則不進(jìn)行彈出操作，并輸出 ERR_CANNOT_POP。
query()：輸出隊(duì)首元素。如果此時(shí)隊(duì)首為空，則輸出 ERR_CANNOT_QUERY。
size()：輸出此時(shí)隊(duì)列內(nèi)元素個(gè)數(shù)。

數(shù)據(jù)范圍：$n\leq 10000$，且被插入隊(duì)列的所有元素值是 $[1, 1000000]$ 以內(nèi)的正整數(shù)。

輸入格式

第一行，一個(gè)整數(shù) $n$，表示操作的次數(shù)。

接下來 $n$ 行，每行表示一個(gè)操作。格式如下：

1 x，表示將元素 x 加入隊(duì)列。
2，表示將隊(duì)首彈出隊(duì)列。
3，表示查詢隊(duì)首。
4，表示查詢隊(duì)列內(nèi)元素個(gè)數(shù)。

輸出格式

輸出若干行，對(duì)于每個(gè)操作，按「題目描述」輸出結(jié)果。

每條輸出之間應(yīng)當(dāng)用空行隔開。

參考程序

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,INF=0x3f3f3f3f;
int que[N], front=0, tail=-1;

void push(int x){
    que[++tail] = x;
} 
void pop(){
    if(front>tail) cout<<"ERR_CANNOT_POP"<<endl;
    else ++front; // 出隊(duì) 
}
void query(){
    if(front>tail) cout<<"ERR_CANNOT_QUERY"<<endl;
    else cout<<que[front]<<endl;
}
int size(){
    return tail-front+1;
}
int main(){
    //freopen("data.in", "r", stdin);
    int n,op,x; cin>>n;
    while(n--){
        cin>>op;
        if(op==1) cin>>x,push(x);    
        if(op==2) pop();
        if(op==3) query();
        if(op==4) cout<<size()<<endl;
    }
    return 0;
}

P1996 約瑟夫問題

$n$ 個(gè)人圍成一圈，從第一個(gè)人開始報(bào)數(shù),數(shù)到 $m$ 的人出列，再由下一個(gè)人重新從 $1$ 開始報(bào)數(shù)，數(shù)到 $m$ 的人再出圈，依次類推，直到所有的人都出圈，請(qǐng)輸出依次出圈人的編號(hào)。

數(shù)據(jù)范圍：$1 \le m, n \le 100$

輸入兩個(gè)整數(shù) $n,m$。

輸出一行 $n$ 個(gè)整數(shù)，按順序輸出每個(gè)出圈人的編號(hào)。

樣例輸入

10 3

樣例輸出

3 6 9 2 7 1 8 5 10 4

參考程序

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,INF=0x3f3f3f3f;
int que[N], front=0, tail=-1;

int main() {
    int n, m, cnt=0; cin>>n>>m;
    for(int i=1; i<=n; i++) que[++tail] = i;
    while(front <= tail) {
        ++cnt;
        if(cnt%m==0) cout<<que[front]<<" "; // 殺掉
        else que[++tail] = que[front]; // 沒殺掉
        ++front;
    }
    return 0;
}

posted @ 2022-11-24 09:39 HelloHeBin 閱讀(82) 評(píng)論(0) 收藏舉報(bào)

刷新頁面返回頂部

HelloHeBin

在醒著的時(shí)間里，追求你認(rèn)為最有意義的~

棧與隊(duì)列_基礎(chǔ)1