数据结构中的栈，队列和链表 介绍和算法模拟C++

概述：误区

本文说的是数据结构中的堆栈

数据结构中的堆栈

是一种逻辑结构，栈一般是后进后出；队列一般是先进先出；链表一般是彼此间使用指针联系的结构，指针实现的队列就是一种链表；堆一般指二叉树。

计算机结构的堆栈

是一种物理结构，准确的来说是内存分配中的堆栈，一般学习汇编会用到。大体上来说是计算机汇编层将内存分为堆和栈两部分，各自的用途有的是用于储存函数调用帧，有的是用于保存变量数据。

代码实现

栈 ：Stack

栈一般使用数组来实现（数组单段性很时候用于实现栈）

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+10;
//指针p永远指向最后一个已写入的位置
int stack[MAXN]={0};int p=-1;

int main(){
    //入栈
    int value;cin>>value;
    stack[++p]=value;
    //出栈
    cout<<stack[p--];
    return 0;
}

队列：Queue

队列一般使用链表来实现，因为链是向的结构，因此不需要last+next只需要保存下一个就可以了，这里为了方便用面向对象的写法

#include<bits/stdc++.h>
using namespace std;

struct Node{
    int data;
    Node* next;
};

class MyQueue{
    public:
        MyQueue();
        void push(int value);
        void pop();
        void print();
    private:
        struct Node* head;
        struct Node* tail;
};

MyQueue::MyQueue(){
    head=NULL;
    tail=NULL;
};
void MyQueue::push(int value){
    Node* node= (Node*)malloc(sizeof(Node));
    node->data=value;
    node->next=NULL;
    if(tail==NULL){
        head=tail=node;
    }else{
        tail->next=node;
        tail=node;
    }
};
void MyQueue::pop(){
    if(tail==NULL){
        cout<<"erro in pop in null Queue"<<endl;
    }else{
        Node* was=head->next;
        free(head);
        head=was;
    }
};

void MyQueue::print(){
    cout<<"stack print start\n";
    for(Node* tmp=head; tmp!=NULL; tmp=tmp->next){
        cout<<tmp->data<<" ";
    }
    cout<<"\nend\n";
}; 

int main(){
    /*
        A a; 
        A * a = new a(); 进入动态内存中不能使用malloc 
    */
    //初始化队列并给第一个值为18
    MyQueue queue; 
    queue.push(18);

    //左出右进来表示队列
    struct Node zero;zero.data=18;
    queue.push(1);//18 1 1 
    queue.push(1);//18 1 1 
    queue.push(5);//18 1 1 5
    queue.print();//18 1 1 5

    //弹出第一个进去的也就是18变成115 
    queue.pop();//1 1 5
    queue.print();//1 1 5

    return 0;
};

C++STL版队列

队列一般使用其中的 list 容器进行对应的操作（list是双向链表正反查询都很快）

一，无序容器

set、map：都是字典，后者的元素有唯一性，底层都是堆也就是平衡二叉树，因此搜索很容易，但是插入费时

二，有序容器

STL参考总结：（非博文不好用链接形式引用，来自网络）

1 vector
向量 相当于一个数组
在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时，bai首先分配一个非常大的内存空间预备进行存储，即capacituy（）函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储，这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。
优点：(1) 不指定一块内存大小的数组的连续存储，即可以像数组一样操作，但可以对此数组
进行动态操作。通常体现在push_back() pop_back()
(2) 随机访问方便，即支持[ ]操作符和vector.at()
(3) 节省空间。
缺点：(1) 在内部进行插入删除操作效率低。
(2) 只能在vector的最后进行push和pop，不能在vector的头进行push和pop。
(3) 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释
放
2 list
双向链表
每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。
优点：(1) 不使用连续内存完成动态操作。
(2) 在内部方便的进行插入和删除操作
(3) 可在两端进行push、pop
缺点：(1) 不能进行内部的随机访问，即不支持[ ]操作符和vector.at()
(2) 相对于verctor占用内存多
3 deque
双端队列 double-end queue
deque是在功能上合并了vector和list。
优点：(1) 随机访问方便，即支持[ ]操作符和vector.at()
(2) 在内部方便的进行插入和删除操作
(3) 可在两端进行push、pop
缺点：(1) 占用内存多
使用区别：
1 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
2 如果你需要大量的插入和删除，而不关心随即存取，则应使用list
3 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque

4.string：类似类的classname: value即直线对应