服务器之家：专注于VPS、云服务器配置技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C++数据结构深入探究栈与队列

C++数据结构深入探究栈与队列

2022-11-28 12:07舟叶 C/C++

栈和队列，严格意义上来说，也属于线性表，因为它们也都用于存储逻辑关系为 "一对一" 的数据，但由于它们比较特殊，本章讲解分别用队列实现栈与用栈实现队列

1. 栈

1.1 栈的概念

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

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

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

1.2 栈的实现

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Stack.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
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);
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
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非空返回0
bool StackEmpty(Stack* pst)
{
    assert(pst);
    return pst->top == 0;
}
int StackSize(Stack* pst)
{
    assert(pst);
    return pst->top;
}
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 队列的实现

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Queue.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
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);
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
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;
}
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 括号匹配问题

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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用队列实现栈

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//思路:
//入栈: 向不为空的队列入数据,始终保持另一个队列为空
//出栈: 前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 用栈实现队列

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
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(): 检查循环队列是否已满。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
//循环队列是逻辑上的循环(数组、链表都可以实现,本题使用数组)
//永远空出一个位置不存储数据(目的是区分空和满)
//当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++数据结构深入探究栈与队列的文章就介绍到这了,更多相关C++栈与队列内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://blog.csdn.net/m0_62934529/article/details/124488413

  • 队列
  • C++
  • 栈

    • 延伸 · 阅读

    精彩推荐
    • C/C++C++中关于set删除的一些坑

      C++中关于set删除的一些坑

      这篇文章主要介绍了C++中关于set删除的一些坑，因为这个问题浪费了很多的时间，所以想着分享出来给大家，方便同样遇到这个问题的朋友们，有需要的朋...

      海虹不老阁9712021-04-29
    • C/C++C/C++ Qt 数据库与ComBox实现多级联动示例代码

      C/C++ Qt 数据库与ComBox实现多级联动示例代码

      Qt中的SQL数据库组件可以与ComBox组件形成多级联动效果，在日常开发中多级联动效果应用非常广泛，今天给大家分享二级ComBox菜单如何与数据库形成联动，...

      Lyshark8762022-03-10
    • C/C++C语言中全局数组和局部数组的问题

      C语言中全局数组和局部数组的问题

      今天同学遇到一个在C语言中全局数组和局部数组的问题，卡了许久，我也没有第一时间看出问题，现在把问题梳理一下，并给出解决方案,需要的朋友可以...

      C语言教程网2332020-11-13
    • C/C++C++实现字符串删除字符后逆序输出

      C++实现字符串删除字符后逆序输出

      这篇文章主要为大家详细介绍了C++实现字符串删除字符后逆序输出，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...

      Alex山南水北12032021-09-08
    • C/C++C语言实现通用数据结构之通用椎栈

      C语言实现通用数据结构之通用椎栈

      这篇文章主要为大家详细介绍了C语言实现通用数据结构之通用椎栈，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...

      swwlqw6752022-03-05
    • C/C++C语言 循环详解及简单代码示例

      C语言 循环详解及简单代码示例

      本文主要介绍C语言的循环知识，这里整理了循环的基础资料并附简单的代码示例详细讲解，有需要的小伙伴可以参考下...

      C语言教程网4072021-04-13
    • C/C++详解C++编程中的条件判断语句if-else与switch的用法

      详解C++编程中的条件判断语句if-else与switch的用法

      这篇文章主要介绍了C++编程中的条件判断语句if-else与switch的用法,是C++入门学习中的基础知识,需要的朋友可以参考下...

      C++教程网6342021-03-22
    • C/C++解决vscode下调试c/c++程序一闪而过的问题（Windows）

      解决vscode下调试c/c++程序一闪而过的问题（Windows）

      这篇文章主要介绍了解决vscode下调试c/c++程序一闪而过（Windows）,本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可...

      张麦麦啊9082021-09-22
    最近更新
    编辑推荐
    阅读排行
    热门标签
    1015 　 GraphicsView 　 地址参数 　 多继承法 　 ZOJ 　 Fishing 　 同名 　 libfreetype 　 Simulink 　 数据滚动 　 右值引用 　 NSString 　 消息传递 　 平滑处理 　 Visual C++ 　 栈区 　 堆区 　 C语言程序设计 　 内存错误 　 对象模型 　 颜色加亮 　 程序内部 　 strcat 　 WinExec 　 打开程序 　 错误调试 　 C++教程 　 tinyxml 　 XML解析器 　 静态存储区 　
    © 2019-2022 服务器之家(www.tuohang.net) 版权所有关于我们联系我们版权申明网站地图