C++数据结构基础篇1-线性表（3）-栈和队列

一、栈基础概念讲解

上一张我们分析了单链表，也分析了单链表的好处，那么可以看一下就是单链表的特点：
1、单链表可以认为是最普通的一种线性表的结构，它插入和删除都是任意位置的；
2、相对于来说，栈就是不同了 $\color{red}{所谓的栈，就是先入后出，我们的插入和删除操作都是对这个表最末尾}$
$\color{red}{的位置进行操作；也就是后入的先出，先入的后出；，那么我们就引入了链表的操作；}$
综上：
我们看出了尾指针的重要性；我们的插入和删除都是对最后的尾指针进行操作；最后也都插入和删除最后一个元素

二、栈的基本操作

1、栈准备数据

和单链表是一样的；就是我们准备一个头指针和尾指针数据即可；

//结点
typedef struct Node {
    int data;
    Node * next;
}Node;
//创建列表
typedef struct ListMine {
    Node *head;
    Node *tail;
    int  length;
}ListMine;

2、单栈创建和析构

//创建栈
void createList(ListMine* SL)
{
    SL->head = SL->tail = NULL;
    SL->length = 0;
}
//删除栈
void distroyList(ListMine* SL)
{
    Node* cur = SL->head;
    while (cur != NULL)
    {
        Node* tmp = cur->next;
        free(cur);
        cur = tmp;
    }
    free(SL);
}

3、栈的插入和删除

此时我们就没有位置的概念了，因为位置一定会是最后一个；这个其实和单链表区别不是很大，就是从单链表的演化而来；

//插入结点，没有了位置的参数
bool insert(ListMine*SL,  int data)
{
    Node *p = SL->head; //0
    Node *n = (Node*)calloc(1,sizeof(Node)); //分配新内存；
    n->data = data;
    n->next = NULL;
    if (SL->head== NULL)
    {
        SL->head = SL->tail = n;
        SL->length += 1;
        return true;
    }
    //之所以单独抽出来，是因为这样可以增快最后插入的时间
    //这就是为了告诉自己，尾指针的作用
    //后面如果有栈和队列的操作的时候，就会明白这个的重要性了
    
        SL->tail->next = n;
        SL->tail = n;
        SL->length ++;
        return true;
}
//删除结点
bool pop(ListMine*SL)
{
    //有了尾指针，且如果是双向链表的话，就让这个变得很简单；
        //但是它是单链表；还需要遍历一遍，遍历到尾指针的前面才行；
    Node *p = SL->head; //0
    int j = 0;//0
    while (j < SL->length-2 && p->next)
    {
        p = p->next;
        ++j;
    }
    Node *willfree = p->next;
    p->next = p->next->next;
    delete willfree;  //释放内存
    SL->length--;
    return true;
}

3、main函数验证

///主函数///
int main() {
    ListMine* SL = (ListMine*)calloc(1, sizeof(ListMine));
    createList(SL);
    int i = 0;
    for (; i < 10; i++)
    {
        insert(SL, i);

    }
    Node*cur = SL->head;
    while (cur != NULL)
    {
        cout << "the data is " << cur->data << endl;
        cur = cur->next;
    }
    cout << "============================" << endl;
    pop(SL);
    cur = SL->head;
    while (cur!= NULL)
    {
        cout << "the data is " << cur->data << endl;
        cur = cur->next;
    }
    distroyList(SL);
}

运行结果如下：

image.png

4、队列的插入和删除

所谓的队列，就是先入先出，就像是排队一样；可以这样想象，栈就像是一个柱子；那么我们往柱子上去放铁环；队列就是排队一样；所以队列是先入先出；
分析了和栈的区别；那么可以看出队列其实说白了就是我们在pop的时候，是需要把链表的head给pop出来；代码如下：

//删除结点
bool pop(ListMine*SL)
{
    Node *p = SL->head; //0
    if (p == NULL)
    {
        cout << "the queue is error NULL!" << endl;
        return false;
    }
    Node *willfree = p->next;
    SL->head = willfree;
    delete p;  //释放内存
    SL->length--;
    return true;
}