C++数据结构的栈与队列实例分析

今天小编给大家分享一下C++数据结构的栈与队列实例分析的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。

1. 栈

1.1 栈的概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1.2 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。

Stack.h#pragma once#include #include #include typedef int bool;#define TRUE 1;#define FALSE 0;typedef int STDataType;struct Stack{        STDataType* a;        int top;       //栈顶        int capacity;  //容量，方便增容};//typedef struct Stack ST;typedef struct Stack Stack;//初始化void StackInit(Stack* pst);//销毁void StackDestroy(Stack* pst);//入栈void StackPush(Stack* pst, STDataType x);//出栈void StackPop(Stack* pst);//返回栈顶数据STDataType StackTop(Stack* pst);//判断栈是否为空,空返回1非空返回0//int StackEmpty(Stack* pst);bool StackEmpty(Stack* pst);//栈中数据个数int StackSize(Stack* pst);

Stack.c#include "Stack.h"//初始化void StackInit(Stack* pst){        assert(pst);        /*pst->a = NULL;        pst->top = 0;        pst->capacity = 0;*/        //开始就申请空间，好处在于空间不够时直接容量*2即可(如果刚开始是0就要单独处理)        pst->a = malloc(sizeof(STDataType) * 4);        pst->top = 0;        pst->capacity = 4;}//销毁void StackDestroy(Stack* pst){        assert(pst);        free(pst->a);        pst->a = NULL;        pst->capacity = pst->top = 0;}//入栈void StackPush(Stack* pst, STDataType x){        assert(pst);        //从top为0的位置开始放        //如果满了就增容        if (pst->top == pst->capacity)        {                STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2);                if (tmp == NULL)                {                        //如果开辟空间失败                        printf("realloc fail\n");                        exit(-1);//结束整个程序(-1表示异常退出)                }                pst->a = tmp;                pst->capacity *= 2;        }        //入数据        pst->a[pst->top] = x;        pst->top++;}//出栈void StackPop(Stack* pst){        assert(pst);//不能是空指针        assert(!StackEmpty(pst)); //栈内还有元素才能出战        pst->top--;}//返回栈顶数据STDataType StackTop(Stack* pst){        assert(pst);        assert(!StackEmpty(pst));        return pst->a[pst->top - 1];}//判断栈是否为空,空返回1非空返回0bool StackEmpty(Stack* pst){        assert(pst);        return pst->top == 0;}int StackSize(Stack* pst){        assert(pst);        return pst->top;}

test.c#include "Stack.h"//对栈操作的测试void TestStack(){        Stack st;        StackInit(&st);        StackPush(&st, 1);        StackPush(&st, 2);        StackPush(&st, 3);        StackPush(&st, 4);        //栈遍历数据        while (!StackEmpty(&st))        {                printf("%d ", StackTop(&st));                StackPop(&st);        }        //4 3 2 1        StackDestroy(&st);}int main(){        TestStack();        return 0;}

2. 队列

2.1 队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

2.2 队列的实现

Queue.h#pragma once#include #include #include #include typedef int QDataType;//队列中的一个结点typedef struct QueueNode{        struct QueueNode* next;        QDataType data;}QueueNode;//队列(由于需要两个指针，所以用结构体定义)typedef struct Queue{        QueueNode* head; //头指针        QueueNode* tail; //尾指针}Queue;//初始化void QueueInit(Queue* pq);//销毁void QueueDestroy(Queue* pq);//入队void QueuePush(Queue* pq, QDataType x);//出队void QueuePop(Queue* pq);//取队头数据QDataType QueueFront(Queue* pq);//取队尾数据QDataType QueueBack(Queue* pq);//判空bool QueueEmpty(Queue* pq);//计算队列元素个数int QueueSize(Queue* pq);

Queue.c#include "Queue.h"//初始化void QueueInit(Queue* pq){        assert(pq);        //不带哨兵位        pq->head = pq->tail = NULL;}//销毁void QueueDestroy(Queue* pq){        assert(pq);        QueueNode* cur = pq->head;        while (cur)        {                QueueNode* next = cur->next;                free(cur);                cur = next;        }        pq->head = pq->tail = NULL;}//判空bool QueueEmpty(Queue* pq){        assert(pq);        return pq->head == NULL; //等于空就为真, 不为空就是假}//入队void QueuePush(Queue* pq, QDataType x){        assert(pq);        QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));        if (newnode == NULL)//申请空间失败        {                printf("malloc fail\n");                exit(-1);        }        newnode->data = x;        newnode->next = NULL;        if (pq->tail == NULL)        {                pq->head = pq->tail = newnode;        }        else        {                pq->tail->next = newnode;                pq->tail = newnode;        }}//出队void QueuePop(Queue* pq){        assert(pq);        assert(!QueueEmpty(pq));//空队列也不能调用出队操作        if (pq->head->next == NULL)//只有一个结点的情况(如果不单独考虑，那当只有一个结点时，tail会仍然指向曾经的队尾)        {                free(pq->head);                pq->head = pq->tail = NULL;        }        else        {                QueueNode* next = pq->head->next;                free(pq->head);                pq->head = next;        }}//取队头数据QDataType QueueFront(Queue* pq){        assert(pq);        assert(!QueueEmpty(pq));        return pq->head->data;}//取队尾数据QDataType QueueBack(Queue* pq){        assert(pq);        assert(!QueueEmpty(pq));        return pq->tail->data;}int QueueSize(Queue* pq){        int size = 0;        QueueNode* cur = pq->head;        while (cur)        {                size++;                cur = cur->next;        }        return size;}

test.c#include "Queue.h"//对队列操作的测试void TestQueue(){        Queue q;        QueueInit(&q);        QueuePush(&q, 1);        QueuePush(&q, 2);        QueuePush(&q, 3);        QueuePush(&q, 4);        printf("%d\n", QueueSize(&q)); //4        while (!QueueEmpty(&q))        {                printf("%d ", QueueFront(&q));                QueuePop(&q);        }        //1 2 3 4        QueueDestroy(&q);}int main(){        TestQueue();        return 0;}

3. 栈和队列面试题

3.1 括号匹配问题

bool isValid(char * s){    Stack st;    StackInit(&st);    while(*s)    {        //左括号入栈，右括号找最近的左括号匹配        if(*s == '[' || *s == '(' || *s == '{')        {            StackPush(&st, *s);            s++;        }        else        {            if(StackEmpty(&st))//只有后括号的情况            {                StackDestroy(&st);                return false;            }            char top = StackTop(&st);            //不匹配的情况            if ( (top == '[' && *s != ']')             || (top == '(' && *s != ')')            || (top == '{' && *s != '}') )             {                StackDestroy(&st);                return false;            }            else //匹配的情况            {                StackPop(&st);                s++;            }        }    }    //如果最后栈内为空才说明是匹配的(防止最后栈内还剩下前括号的情况)    bool ret = StackEmpty(&st);    StackDestroy(&st);    return ret;    //特别注意:在return之前需要先把栈销毁掉}

3.2用队列实现栈

//思路://入栈: 向不为空的队列入数据,始终保持另一个队列为空//出栈: 前size-1个数据导入空队列，删除最后一个typedef struct {    Queue q1;    Queue q2;} MyStack;//*为什么下面代码传参都要传&obj->q1/q2？//因为应该传入函数中的是队列的指针MyStack* myStackCreate() {    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));    QueueInit(&pst->q1);    QueueInit(&pst->q2);    return pst;}void myStackPush(MyStack* obj, int x){    //往不为空的队列里入数据    if(!QueueEmpty(&obj->q1))    {        QueuePush(&obj->q1, x);    }    else    {        QueuePush(&obj->q2, x);    }}int myStackPop(MyStack* obj) {    //假设q1为空q2不为空    Queue* pEmpty = &obj->q1;    Queue* pNonEmpty = &obj->q2;    if(!QueueEmpty(&obj->q1))    {        pEmpty = &obj->q2;        pNonEmpty = &obj->q1;    }    //取出前size-1个插入空队列    while(QueueSize(pNonEmpty) > 1)    {        QueuePush(pEmpty, QueueFront(pNonEmpty));        QueuePop(pNonEmpty);    }    //"干掉"最后一个    int front = QueueBack(pNonEmpty);    QueuePop(pNonEmpty);    return front;}int myStackTop(MyStack* obj) {    if(!QueueEmpty(&obj->q1))    {        return QueueBack(&obj->q1);    }    else    {        return QueueBack(&obj->q2);    }}bool myStackEmpty(MyStack* obj) {    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);}void myStackFree(MyStack* obj) {    //先释放两个队列，再释放malloc出来的结构体    QueueDestroy(&obj->q1);    QueueDestroy(&obj->q2);    free(obj);}

3.3 用栈实现队列

typedef struct {    Stack pushST;    Stack popST;} MyQueue;MyQueue* myQueueCreate() {    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));    StackInit(&q->pushST);    StackInit(&q->popST);    return q;}void myQueuePush(MyQueue* obj, int x){    //不管栈内有没有数据，只要是入队操作就向Push栈入数据即可    StackPush(&obj->pushST, x);}//获取队头数据int myQueuePeek(MyQueue* obj) {    //如果pop栈为空,先把push栈数据导入pop栈    if(StackEmpty(&obj->popST))    {        while(!StackEmpty(&obj->pushST))        {            StackPush(&obj->popST, StackTop(&obj->pushST));            StackPop(&obj->pushST);        }    }    return StackTop(&obj->popST);}//出队int myQueuePop(MyQueue* obj) {    //如果pop栈为空,先把push栈数据导入pop栈    /*if(StackEmpty(&obj->popST))    {        while(!StackEmpty(&obj->pushST))        {            StackPush(&obj->popST, StackTop(&obj->pushST));            StackPop(&obj->pushST);        }    }    */    //复用    int top = myQueuePeek(obj);//易错点:不能写&obj->popST,因为该传入队列的指针    StackPop(&obj->popST);    return top;}bool myQueueEmpty(MyQueue* obj) {    //push栈和pop栈同时为空,队列才为空    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);}void myQueueFree(MyQueue* obj){    StackDestroy(&obj->pushST);    StackDestroy(&obj->popST);    free(obj);}

3.4 设计循环队列

题目描述：

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为"环形缓冲器"。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。

Front: 从队首获取元素。如果队列为空，返回 -1 。

Rear: 获取队尾元素。如果队列为空，返回 -1 。

enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

isEmpty(): 检查循环队列是否为空。

isFull(): 检查循环队列是否已满。

//循环队列是逻辑上的循环(数组、链表都可以实现,本题使用数组)//永远空出一个位置不存储数据(目的是区分空和满)//当front = tail说明循环队列空//当tail+1 = front说明循环队列满typedef struct {    int* a;     //数组    int k;      //循环队列最多能存多少个数据    int front;  //头指针    int tail;   //尾指针(队尾数据的下一个位置)} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));    obj->a = (int*)malloc(sizeof(int)*(k+1)); //需要多开一个空间    obj->front = 0;    obj->tail = 0;    obj->k = k;    return obj;}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {    return obj->front == obj->tail;}bool myCircularQueueIsFull(MyCircularQueue* obj) {    int tailNext = obj->tail + 1;    if(tailNext == obj->k+1)    {        //如果tail已经走到尾(不存放数据的位置),此时认为tailNext回到了数组首元素位置        tailNext = 0;    }     return tailNext == obj->front;}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {    if(myCircularQueueIsFull(obj))    {        return false;    }    else    {        obj->a[obj->tail] = value;        obj->tail++;         if(obj->tail == obj->k+1) //也可以取模          {            obj->tail = 0;        }        /* //取模        obj->tail %= (obj->k+1);        */         return true;    }}bool myCircularQueueDeQueue(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))//如果obj为空了就不能出数据    {        return false;    }    else    {        obj->front++;        //极端情况:front加到尾后重新回到数组首元素        if(obj->front == obj->k+1)        {            obj->front = 0;        }        return true;    }}int myCircularQueueFront(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))    {        return -1;    }    else    {        return obj->a[obj->front];    }}int myCircularQueueRear(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))    {        return -1;    }    else    {        //由于取尾需要去tail的前一个,那么当tail就在首元素的时候,要把它挪到最后一个元素的位置去        int tailPrev = obj->tail - 1;        if(tailPrev == -1)        {            tailPrev = obj->k;        }        return obj->a[tailPrev];    }}void myCircularQueueFree(MyCircularQueue* obj) {    free(obj->a);    free(obj);}

以上就是"C++数据结构的栈与队列实例分析"这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注行业资讯频道。