数据结构之栈

偏执的太偏执、 2022-05-25 02:37 219阅读 0赞

## 一、顺序栈 ##

### 1.0 理解栈 ###

栈是一种比线性表还要简单的数据结构，因为他就是对线性表的限制后的数据结构
    即 只允许在线性表的尾部进行插入和删除操作

#### 1.1 几个基本概念 ####

##### 1.1.1 进栈 压栈 #####

这两个词一个意思，都是往栈中添加元素

##### 1.1.2 出栈 弹栈 #####

也是一个意思，就是删除栈顶元素

##### 1.1.3 栈的特性 #####

后进先出也可以说先进后出，因为只允许在线性表的尾部进行操作，所以先进去的元素会被后进去的元素压住，不能先取出来，所以要后出

### 2.0 代码实例演示 ###

#include <iostream>
    using namespace std;
    //默认的栈空间大小，自己根据需要设定 
    const int StackSize = 10;
    
    class Stack{
        private:
            int stack[StackSize];  //用线性表来标识栈 
            int top;                //栈顶指针
        public:
            //构造函数 初始化栈顶指针为-1 表示栈没有元素 
             Stack(){
                top = -1;
             } 
            //压栈 添加元素
            void Push(int a){
                if(top==StackSize-1) throw "上溢"; 
                //++top 的值为top+1 的值 top++ 值为top 
                //栈中第一各元素为a的值，同时top+1 
                stack[++top]= a; 
            } 
            //弹栈同时栈顶指针减去1 
             int Pop(){
                int x =  stack[top--];
                return x;
             } 
            //取栈顶元素不删除栈顶元素
            int getTop(){
                return stack[top];
            } 
            //判断栈是否为空
            int Isempty(){
                return  top==-1 ? 1 : 0;
            } 
    };
    int main(){
        Stack stack;
        stack.Push(10);
        cout<<stack.Isempty()<<endl;
        cout<<stack.getTop();
    }

关于顺序栈的话就这点，没啥说的了。。。  
还是多说一下吧，就是如果在一个类中有两个栈的时候，  
最直接的方法是给每个栈都分配一个数组空间但是这样有时候就比较浪费  
所以我们可以用另一张方法解决**两栈共享空间**  
就是用一个数组存两个栈，一个栈的栈底位于数组的始端，一个栈的栈底在数组的末端，然后同时向中间延伸，  
这个自己愿意试就自己实现以下，然后网上会有很多资源，我就不写了，如果找不到的话，留言吧！

--------------------

## 二、链栈 ##

### 1.0 什么是链栈？ ###

链栈就是用链表实现的栈结构

### 2.0 怎么搞？看代码 ###

#include <iostream>
    using namespace std;
    struct linkstack{
        int data;
        linkstack *next;
    };
    class LinkStack{
        private:
            linkstack *top;//栈顶指针
        public:
            LinkStack(){
                top = NULL;
             }
            //入栈
            void Push(int a){
                linkstack* s = new linkstack;
                s->data = a;
                //链栈的结构为 1<-2<-3<-4 top指向的是4 
                s->next = top;
                top  = s;
            } 
            //出栈
            int Pop(){
                if(top==NULL) throw "下一处";
    
                    int x = top->data;
                    linkstack *p = top;
                    top = top->next; 
                    delete p;
                    return x;
    
    
            } 
            //读栈顶元素
            int getTop(){
                return top->data;
            } 
            //判断栈是否为空
            int Isempty(){
                return top==NULL?1:0;
            } 
    };
    int main(){
        LinkStack linkStack;
        linkStack.Push(10);
        cout<<"执行的操作 linkStack.Push(10) \n栈是否为空 0代表不是空"
        <<linkStack.Isempty()<<endl<<"栈顶元素是" <<linkStack.getTop()<<endl
        <<"是空吗?" <<linkStack.Isempty()<<endl;
        cout<<linkStack.Pop();
        cout<<"是空吗?" <<linkStack.Isempty()<<endl;
    }

> 两种栈的实现方式的比较  
> 栈的时间性能都是常数，所以只能比较空间性能，空间性能来说呢，因为栈多了一个指针域，所以如果元素个数变化比较大适合用链栈，反之顺序栈