第三章 栈和队列

顺序栈的实现

#include <bits/stdc++.h>

using namespace std;
const int N=1e4+5;
class Seqstack
{
    
public:
    Seqstack();
    ~Seqstack(){
    }
    void Push(int k);
    int Pop();
    bool Empty();
    int Gettop();
private:
    int data[N];
    int top;
};
Seqstack::Seqstack()
{
    
    top=-1;
}
void Seqstack::Push(int k)
{
    
    if(top==N)
    {
    
        cout<<"上溢"<<endl;return;
    }
    data[++top]=k;
}
int Seqstack::Pop()
{
    
    if(top==-1)
        return -1;
    return data[top--];
}
int Seqstack::Gettop()
{
    
    if(top==-1)
        return -1;
    return data[top];
}
bool Seqstack::Empty()
{
    
    if(top==-1)
        return 1;
    return 0;
}
int main()
{
    
    Seqstack s=Seqstack();
    s.Push(1);
    s.Push(2);
    cout<<s.Pop()<<endl;
    cout<<s.Gettop()<<endl;
    if(s.Empty()!=1)
        cout<<"非空"<<endl;
    else
        cout<<"空"<<endl;
    return 0;
}

链栈的实现

#include <bits/stdc++.h>

using namespace std;
const int N=1e4+5;
struct Node
{
    
    int x;
    Node *nxt;
};
class Linkstack
{
    
public:
    Linkstack();
    ~Linkstack();
    void Push(int k);
    int Pop();
    bool Empty();
    int Gettop();
private:
    Node *top;
};
Linkstack::Linkstack()
{
    
    top=new Node;
    top->nxt=NULL;
}
Linkstack::~Linkstack()
{
    
    Node *p=top;
    while(top!=NULL)
    {
    
        top=top->nxt;
        delete p;
        p=top;
    }
}
void Linkstack::Push(int k)
{
    
    Node* s=new Node;
    s->x=k;
    s->nxt=top;
    top=s;
}
int Linkstack::Pop()
{
    
    if(top->nxt==NULL)
        return -1;
    int x=top->x;
    Node *p=top;
    top=top->nxt;
    delete p;
    return x;
}
int Linkstack::Gettop()
{
    
    return top->x;
}
bool Linkstack::Empty()
{
    
    if(top->nxt==NULL)
        return 1;
    return 0;
}
int main()
{
    
    Linkstack ls=Linkstack();
    if(ls.Empty()!=1)
        cout<<"非空"<<endl;
    else
        cout<<"空"<<endl;
    ls.Push(1);
    ls.Push(22);
    cout<<ls.Pop()<<endl;
    cout<<ls.Gettop()<<endl;
    ls.Pop();
    if(ls.Empty()!=1)
        cout<<"非空"<<endl;
    else
        cout<<"空"<<endl;
    return 0;
}

循环队列的实现

#include <bits/stdc++.h>

using namespace std;
const int N=1e4+5;
class Cirqueue
{
    
public:
    Cirqueue();
    ~Cirqueue(){
    };
    void en_que(int k);
    int de_que();
    int Gethead();
    bool Empty();
public:
    int data[N];
    int fr,re;
};
Cirqueue::Cirqueue()
{
    
    fr=re=N-1;
}
void Cirqueue::en_que(int k)
{
    
    if((re+1)%N==fr)
    {
    
        cout<<"上溢"<<endl;return ;
    }
    re=(re+1)%N;
    data[re]=k;
}
int Cirqueue::de_que()
{
    
    if(re==fr)
    {
    
        cout<<"下溢"<<endl;return 0;
    }
    fr=(fr+1)%N;
    return data[fr];
}
int Cirqueue::Gethead()
{
    
    return data[(fr+1)%N];
}
bool Cirqueue::Empty()
{
    
    if(fr==re)
        return 1;
    else
        return 0;
}
int main()
{
    
    Cirqueue cq=Cirqueue();
    cq.en_que(1);
    cq.en_que(22);
    cq.en_que(33);
    cout<<cq.de_que()<<endl;
    cout<<cq.de_que()<<endl;
    cout<<cq.Gethead()<<endl;
    cq.de_que();
    cout<<cq.Empty()<<endl;
    return 0;
}

链队列的存储实现