在大二懵懵懂懂上数据结构的时候，当时学完了栈、队列、树我都不知道学这些数据结构有什么用，直到我大四在力扣上刷到这道题20. 有效的括号 - 力扣（LeetCode），这道题的算法用栈是最简单的，从此我才知道这些数据结构原来这么有用，于是我赶紧回过头来重新刷一遍数据结构！

我主要是用的这本教材

 并且由于我在自学C++，因此教材中用C实现的部分我全部换成C++进行实现(也不用改太多东西的一说..)

栈的顺序存储结构

栈是一种先进后出的结构。

我们对顺序栈的实现是用一个数组（容纳栈中的元素）以及一个栈顶元素（指向栈顶）来实现！

 下面实现初始化栈、销毁栈、判断栈是否为空、进栈、出栈、取栈顶元素等操作：

#include 
using namespace std;
 
typedef int Elemtype; //栈内元素的类型
#define MaxSize 50
 
class SqStack
{
public:
    Elemtype data[MaxSize];
    int top;
};
 
void InitStack(SqStack *&s)
{
    s = new SqStack;
    s->top = -1;
}
 
void DestroyStack(SqStack *&s)
{
    delete s;
}
 
bool StackIsEmpty(SqStack *s)
{
    return (s->top == -1);
}
 
bool Push(SqStack *&s, Elemtype e)
{
    if (s->top == MaxSize - 1)
        return false;
    s->top++;
    s->data[s->top] = e; // !!!
    return true;
}
 
bool Pop(SqStack *&s, Elemtype &e) //只能出栈栈顶元素，e用来保存出栈的栈顶元素
{
    if (s->top == -1)
        return false;
    e = s->data[s->top];
    s->top--;
    return true;
}
 
bool GetTop(SqStack *&s, Elemtype &e)
{
    if (s->top == -1)
        return false;
    e = s->data[s->top];
    return true;
}

 再次给出一个验证上面函数的主函数防止小白不会用这些函数。

int main()
{
    SqStack *s; //定义栈指针
    InitStack(s); //初始化栈
    Push(s, 1); //进栈
    Push(s, 2);
    int temp;
    GetTop(s, temp);//取得栈顶元素
    cout << "the top element of the stack:" << temp << endl;
    Pop(s, temp); // 出栈
    GetTop(s, temp);
    cout << "the top element of the stack:" << temp << endl;
    system("pause");
    return 0;
}

栈的链式存储结构

刚刚的额顺序栈采用数组存取元素，所以我们当然也可以用链式存储结构进行存储！

链栈的优点是不存在栈满上溢的情况，并且插入和删除结点都很方便，时间复杂度为O(1)。

 注意：这里头节点指向栈顶节点，因此我们进栈相当于头插法！

 在实现方面，我们的链栈的一个结点可以用一个指针(指向下一个元素)以及一个变量(存取自身元素的值)。

 同样的，实现初始化栈、销毁栈、判断栈是否为空、进栈、出栈、取栈顶元素等操作：

#include 
using namespace std;
typedef int ElemType;
 
 
class LinkStNode
{
public:
    ElemType data;
    LinkStNode *next;
};
 
void InitStack(LinkStNode *&s)
{
    s = new LinkStNode;
    s->next = NULL;
}
 
void DestroyStack(LinkStNode *&s)
{
    LinkStNode *pre = s, *p = s->next;
    while (p != NULL)
    {
        delete p;
        pre = p;
        p = pre->next;
    }
    delete pre;
}
 
bool StackIsEmpty(LinkStNode *&s)
{
    return (s->next == NULL);
}
 
void Push(LinkStNode *&s, ElemType e)
{
    LinkStNode *p;
    p = new LinkStNode;
    p->data = e;
    p->next = s->next;
    s->next = p;
}
 
bool Pop(LinkStNode *&s, ElemType &e)
{
    LinkStNode *p;
    if (s->next == NULL)
        return false;
    p = s->next;
    e = p->data;
    s->next = p->next;
    delete p;
    return true;
}
 
bool GetTop(LinkStNode *&s, ElemType &e)
{
    if (s->next == NULL)
        return false;
    LinkStNode *p = s->next;
    e = p->data;
    return true;
}

顺序队列

队列是一种先进先出的结构，仅限制在一端进行插入，一端进行删除。

实现方面我们用一个数组(容纳队内元素)以及一个队头变量front和队尾变量rear表示。

 同样的，我们实现初始化、销毁等等操作：

#include
using namespace std;
typedef int ElemType;
#define MaxSize 50
 
class SqQueue
{
public:
    ElemType data[MaxSize];
    ElemType front,rear;//队头和队尾指针
};
 
void InitQueue(SqQueue *&q)
{
    q = new SqQueue;
    q->front = q->rear = -1;
}
 
void DestroyQueue(SqQueue *&q)
{
    delete q;
}
 
bool QueueIsEmpty(SqQueue *&q)
{
    return(q->front == q->rear);
}
//进队列
bool enQueue(SqQueue *&q, ElemType e)
{
    if(q->rear == MaxSize - 1)
        return false;//队列满
    q->rear++;
    q->data[q->rear] = e;
    return true;
}
//出队列
bool deQueue(SqQueue *&q, ElemType &e)
{
    if(q->front == q->rear)
        return false;//队列空
    q->front++;
    e = q->data[q->front]; //说是出队，但是出队元素还在数组中，环形队列也只是进行覆盖！
    return true;
}

环形队列

我们发现上述的队列结构队列满可能不是真的队列满

 这种虽然队尾元素已经到最后了，但是实际上对头元素前面还有空余！

于是我们提出了环形队列！

 

 也就是说我们牺牲了一个元素空间来换取队满条件！

同样的，我们实现一些基本函数：

#include
using namespace std;
typedef int ElemType;
#define MaxSize 50
 
class SqQueue
{
public:
    ElemType data[MaxSize];
    int front, rear; //队头和队尾指针
};
 
void InitQueue(SqQueue *&q)
{
    q = new SqQueue;
    q->front = q->rear = 0;
}
 
void DestroyQueue(SqQueue *&q)
{
    delete q;
}
 
bool QueueIsEmpty(SqQueue *&q)
{
    return(q->front == q->rear);
}
 
bool enQueue(SqQueue *&q, ElemType e)
{
    if((q->rear + 1) % MaxSize == q->front)
        return false;
    q->rear++;
    q->data[q->rear] = e;
    return true;
}
 
bool deQueue(SqQueue *&q, ElemType &e)
{
    if(QueueIsEmpty(q))
        return false;
    q->front++;
    e = q->data[q->front];
    return true;
}

队列的链式存储结构

由于队列的数据元素的逻辑关系呈线性，同样的，我们可以采用链表进行存储。

也是采用一个指针(指向下个元素)以及一个data变量存储自身数据。但是由于我们的链队有两个指针，因此我们要定义两个类！一个链节点类，一个链队类！

同样的，对一些函数进行实现: 

#include 
using namespace std;
typedef int ElemType;
 
class DataNode //链队中数据节点
{
public:
    ElemType data;
    DataNode *next;
};
 
class LinkQuNode //链队中头节点
{
public:
    DataNode *front; //注意有两个节点哦
    DataNode *rear;
};
 
void InitQueue(LinkQuNode *&q)
{
    LinkQuNode *q = new LinkQuNode;
    q->front = q->rear = NULL;
}
 
void DestroyQueue(LinkQuNode *&q) //对于前面的顺序队没有多余指针，我们可以直接销毁。而这里链队必须销毁后面跟着的一些指针，不然他们就变成孤魂野鬼了！
{
    DataNode *pre = q->front, *p;
    if (pre->next != NULL)
    {
        p = pre->next;
        while (p != NULL)
        {
            delete pre;
            pre = p;
            p = p->next;
        }
        delete p;
    }
    delete q;
}
 
bool QueuqIsEmpty(LinkQuNode *q)
{
    return (q->rear == NULL);
}
//进队
bool enQueue(LinkQuNode *&q, ElemType e)
{
    DataNode *p = new DataNode;
    p->data = e;
    p->next = NULL;
    if (QueuqIsEmpty(q))
        q->front = q->rear = p;
    else
    {
        q->rear->next = p;
        q->rear = p;
    }
}
 
bool deQueue(LinkQuNode *&q, ElemType &e)
{
    DataNode *t = q->front;
    if (QueuqIsEmpty(q))
        return false;
    else if (q->front == q->rear) //只有一个元素时，从队头删除也会影响到队尾
    {
        q->front = q->rear = NULL;
    }
    else
    {
        e = q->rear->data;
        q->front = q->front->next;
    }
    delete t;
    return true;
}