物理结构和逻辑结构

逻辑结构本身只是一个抽象的概念

它依托于物理结构而存在

也就是说顺序表也好

还是接下来要讲的栈和队列也好

都是依托于数组或者类等物理结构而实现的

分类大致如下


什么是栈

用简单的四个字便可以概括栈的特点:先进后出

大家打羽毛球的时候经常需要从球筒里取球

但是我们没有办法直接取到最里面的球

我们就可以把这个结构理解为栈

先放进去的羽毛球通常只能最后才能取到(直接倒出来当然不算了)

最早放进去的羽毛球就叫做栈底


栈的实现

栈可以用数组也可用链表来实现

通过上表我们已经知道了存储有两种结构

一种顺序存储结构一种链式存储结构

在这里我们先实现顺序存储结构也就是顺序栈

顺序栈

顺序表和顺序栈的底层其实是基本一致的(数组实现)

只不过顺序栈对读取做了限制(先进后出)

我们并不是记录栈底而是去记录栈顶

然后再用记录的栈顶来决定出栈的顺序

下面是一个简单的实现

//这里写的进出栈并不是很严谨,严格上说应该一个一个进一个一个出

#include<iostream>
#define Maxsize 5
typedef int Elemtype;
using namespace std;

class Stack{
    public:
        Stack();
        void push(Elemtype a[],int n);
        void out();
        
    private:
        Elemtype data[Maxsize];
        int top;
};

Stack::Stack(){
    top = -1;
}

void Stack::push(Elemtype a[],int n){
    for(int i=0;i<n;i++){
        data[i] = a[i];
        top++;
    }
}

void Stack::out(){
    if(top == -1){
        cout<<"栈内没有元素"<<endl;
    }else{
        for(int i=top;i>=0;i--){
            cout<<data[i]<<" ";
        }
    }
    cout<<endl;
}


int main(){
    
    Elemtype a[Maxsize]={1,2,3,4,5};
    
    Stack s;
    s.push(a,5);
    s.out();
    
    return 0;
}

链栈

通常我们将链表的头部作为栈顶,尾部作为栈底

实现入栈就需要在链表的头部插入结点

实现出栈就需要删除链表头部的首元结点

因此,链栈实际上就是一个只能采用头插法插入或删除数据的链表

#include<iostream>
#define Maxsize 5
typedef char Elemtype;
using namespace std;

struct Node{
    Elemtype data;
    Node *next;
};//单链表里的最小结点

class ListStack{
    public:
        ListStack();
        void push(Elemtype e);
        void out();
        void ifempty();
        void deletedata();
        
    private:
        Node *head;
};

ListStack::ListStack(){
    head = new Node;
    head->next = NULL;
}//初始化链栈

void ListStack::push(Elemtype e){
    Node *p;
    p = new Node;
    p->data = e;
    p->next = head->next;
    head->next = p;
}//进栈

void ListStack::out(){
    Node *p;
    if(head->next == NULL){
        cout<<"目前为空栈"<<endl;
    }else{
        p=head->next;
        cout<<p->data; 
        head->next = p->next;
        delete p;
    }
}//出栈 

void ListStack::ifempty(){
    if(head->next == NULL){
        cout<<"目前为空栈"<<endl;
    }else{
        cout<<"目前不是空栈"<<endl;
    }
}//判断是否为空

void ListStack::deletedata(){
    delete head;
} 

int main(){
    ListStack s;
    s.push('a');
    s.push('b');
    s.push('c');
    s.push('d');
    s.push('e');
    s.ifempty();
    s.out();
    s.out();
    s.out();
    s.out();
    s.out();
    s.ifempty();
    s.deletedata();
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。