栈和队列的插入、删除、获取头尾元素操作_队列 取头尾

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈又称为后进先出的线性表。

Stack.h

#pragma once

#include<stdio.h>
#include<assert.h>
#include<Windows.h>

typedef int DataType;

typedef struct Stack
{
    DataType* _array;
    int _top; //栈顶
    int _end;//栈底
}Stack;

// 栈的实现接口
void StackInit(Stack* s);//栈初始化
void StackPush(Stack* s, DataType x);//压栈
void StackPop(Stack* s);//出栈
DataType StackTop(Stack* s);//栈顶元素
size_t StackSize(Stack* s);//栈大小
int StackEmpty(Stack* s);//栈判空
void StackDestory(Stack *s);//栈销毁
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Stack.c

#include"Stack.h"

void StackInit(Stack* s)//初始化栈
{
    s->_array = NULL;
    s->_end = 0;
    s->_top = 0;
}

void StackPush(Stack* s, DataType x)//压栈
{
    assert(s);

    if (s->_end == s->_top)
    {   
        int size = (s->_end == 0) ? 5 : (s->_end) * 2;
        s->_array = (DataType*)realloc(s->_array, sizeof(DataType)*size);
        assert(s->_array);
        s->_end = size;
    }
    s->_array[s->_top++] = x;

}

void StackPop(Stack* s)//出栈

{
    assert(s);
    if (s->_top > 0)
    {
        s->_top--;
    }
}

DataType StackTop(Stack* s)//栈顶元素
{
    assert(s);
    return s->_array[s->_top - 1];

}
size_t StackSize(Stack* s)//栈大小
{
    assert(s);
    return s->_top;
}

int StackEmpty(Stack* s)//判空
{
    assert(s);
    return s->_top;
}

void StackDestory(Stack *s)//栈销毁
{
    assert(s);

    s->_end = 0;
    s->_top = 0;

    free(s->_array);
    s->_array = NULL;
}
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

Test.c

#include"Stack.h"

Test()
{
    Stack s;
    StackInit(&s);

    StackPush(&s, 5);
    StackPush(&s, 4);
    StackPush(&s, 3);
    StackPush(&s, 2);
    StackPush(&s, 1);

    printf("Stack has %d element.\n", StackSize(&s));//

    while (StackEmpty(&s))
    {
        printf("%d\n", StackTop(&s));
        StackPop(&s);
    }

    StackDestory(&s);
}

int main()
{
    Test();

    system("pause");
    return 0;
}
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

队列：一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列具有先进先出(FIFO)的特性顺序队列。

Queue.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<Windows.h>

typedef int DataType;


typedef struct QueueNode
{
    DataType _data;
    struct QueueNode* _next;
}QueueNode;

typedef struct Queue
{
    QueueNode* _head;
    QueueNode* _tail;
}Queue;

void QueueInit(Queue* q);//初始化队列
void QueuePush(Queue* q, DataType x);//入队列
void QueuePop(Queue* q);//出队列
DataType QueueFront(Queue* q);//队头元素
DataType QueueBack(Queue* q);//队尾元素
size_t QueueSize(Queue* q);//队列元素个数
DataType QueueEmpty(Queue* q);//判空
void QueueDestory(Queue* q);//销毁队列
void QueuePrint(Queue *q);//打印队列
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

Queue.c

#include"Queue.h"

void QueueInit(Queue* q)//初始化队列
{
    assert(q);
    q->_head = q->_tail = NULL;
}

void QueuePush(Queue* q, DataType x)//入队列
{
    assert(q);
    QueueNode *qNode = (QueueNode*)malloc(sizeof(QueueNode));
    assert(qNode);

    qNode->_data = x;
    qNode->_next = NULL;

    if (q->_head==NULL)//栈为空
    {

        q->_head = q->_tail = qNode;
    }
    else//栈不为空
    {
        q->_tail->_next = qNode;
        q->_tail = qNode;
    }

}

void QueuePop(Queue* q)//出队列
{
    assert(q && q->_head);

    QueueNode *tmp = q->_head;
    q->_head = tmp->_next;
    free(tmp);
    tmp = NULL;
}

DataType QueueFront(Queue* q)//队头元素
{
    assert(q && q->_head);

    return q->_head->_data;

}

DataType QueueBack(Queue* q)//队尾元素
{
    assert(q && q->_head);

    return q->_tail->_data;

}

size_t QueueSize(Queue* q)//队列元素个数
{
    assert(q);

    QueueNode *tmp = q->_head;
    DataType i = 0;
    while (tmp)
    {
        i++;
        tmp = tmp->_next;
    }
    return i;
}

void QueuePrint(Queue *q)//打印队列
{
    assert(q);

    QueueNode *tmp = q->_head;
    while (tmp)
    {
        printf("%d\n", tmp->_data);
        tmp = tmp->_next;
    }
}

DataType QueueEmpty(Queue* q)//判空
{
    assert(q);
    return q->_head == NULL ? 0 : 1;
}

void QueueDestory(Queue* q)//销毁队列
{
    assert(q);

    QueueNode *tmp = q->_head;
    while (tmp)
    {
        q->_head = tmp;
        tmp = tmp->_next;
        free(q->_head);
        q->_head = NULL;
    }

}
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

Test.c

#include"Queue.h"

Test()
{
    Queue q;

    QueueInit(&q);
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
    QueuePush(&q, 5);

    QueuePrint(&q);

    printf("Queue font is %d\n", (&q)->_head->_data);
    printf("Queue back is %d\n", (&q)->_tail->_data);
    printf("Queue size is %d\n", QueueSize(&q));

    QueuePop(&q);
    QueuePop(&q);
    QueuePush(&q, 7);
    QueuePush(&q, 8);
    QueuePush(&q, 9);

    while (QueueEmpty(&q))
    {
        printf("%d\n", (&q)->_head->_data);
        QueuePop(&q);
    }

    QueueEmpty(&q);

}


int main()
{
    Test();

    return 0;
    system("pause");
}
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