线性表之栈和队列(数据结构)(VS)(C语言)(stack and Queue)

---

前言

  这是我由C语言写的栈和队列，希望对大家有帮助。

---

1.Stack

1.1 Stack.h

#pragma once

#define _CRT_SECURE_NO_WARNINGS 1
//_CRT_SECURE_NO_WARNINGS

#include 
#include 
#include 
#include 

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* data;
	size_t top;		// 栈顶
	size_t capacity;  // 容量 
}Stack;

// 初始化栈 
void StackInit(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
// 压栈 
void StackPush(Stack* ps, const STDataType x);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 判断栈是否为空
bool StackEmpty(Stack* ps);
// 获取栈中有效元素个数 
size_t StackSize(Stack* ps);
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

---

1.1 Stack.c

#include "Stack.h"

// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	ps->data = NULL;
	ps->top = ps->capacity = 0;
}

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->top = ps->capacity = 0;
}

// 压栈 
void StackPush(Stack* ps, const STDataType x)
{
	assert(ps);
	// 判定是否扩容
	if (ps->top == ps->capacity)
	{
		size_t new_capacity = ps->capacity == 0 ? 4 : ps->capacity * 4;
		STDataType* new_data = (STDataType*)realloc(ps->data, sizeof(STDataType) * new_capacity);
		if (!new_data)
		{
			perror("StackPush");
			exit(-1);
		}
		ps->capacity = new_capacity;
		ps->data = new_data;
	}
	ps->data[ps->top++] = x;
}

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->data[ps->top - 1];
}

// 判断栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

// 获取栈中有效元素个数 
size_t StackSize(Stack* ps)
{
	assert(ps);
	return ps->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
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

---

2.Queue

2.1 Queue.h

#pragma once

#define _CRT_SECURE_NO_WARNINGS 1
//_CRT_SECURE_NO_WARNINGS

#include 
#include 
#include 
#include 

// 支持动态增长的栈
typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
	QDataType data;
	struct QListNode* next;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	size_t size;
}Queue;

// 初始化队列 
void QueueInit(Queue* pq);
// 销毁队列 
void QueueDestroy(Queue* pq);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq);
// 队尾入队列 
void QueuePush(Queue* pq,const QDataType x);
// 队头出队列 
void QueuePop(Queue* pq);
// 获取队列头部元素 
QDataType QueueFront(Queue* pq);
// 获取队列队尾元素 
QDataType QueueBack(Queue* pq);
// 获取队列中有效元素个数 
size_t 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

---

2.2 Queue.c

#include "Queue.h"

// 初始化队列 
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
// 销毁队列 
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* node = pq->head;
	while (node)
	{
		QNode* tmp_node = node;
		node = node->next;
		free(tmp_node);
	}
	pq->head = pq->tail = NULL;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq)
{
	return pq->head == NULL;
}
// 队尾入队列 
void QueuePush(Queue* pq, const QDataType x)
{
	assert(pq);
	QNode* new_node = (QNode*)malloc(sizeof(QNode));
	if (!new_node)
	{
		perror("BuyQNode");
		exit(-1);
	}
	new_node->data = x;
	new_node->next = NULL;
	if (QueueEmpty(pq))
	{
		pq->tail = pq->head = new_node;
	}
	else
	{
		pq->tail->next = new_node;
		pq->tail = pq->tail->next;
	}
	pq->size++;
}
// 队头出队列 
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (!pq->head->next)
	{
		free(pq->head);
		pq->tail = pq->head = NULL;
	}
	else
	{
		QNode* tmo_node = pq->head;
		pq->head = pq->head->next;
		free(tmo_node);
	}
	pq->size--;
}
// 获取队列头部元素 
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;
}
// 获取队列中有效元素个数 
size_t QueueSize(Queue* pq)
{
	assert(pq);
	return pq->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
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

---

3.StackQueueTest.c

#include "Stack.h"
#include "Queue.h"

// 栈测试
void StackTest()
{
    Stack s;
    StackInit(&s);
    StackPush(&s, 1);
    StackPush(&s, 2);
    StackPush(&s, 3);
    StackPush(&s, 4);
    printf("%d\n", (int)StackSize(&s));
    while (!StackEmpty(&s))
    {
        printf("%d ", StackTop(&s));
        StackPop(&s);
    }
    printf("\n");
    printf("%d\n", (int)StackSize(&s));
    StackDestroy(&s);
}

// 队列测试
void QueueTest()
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
    printf("%d\n", (int)QueueSize(&q));
    while (!QueueEmpty(&q))
    {
        printf("%d ", QueueFront(&q));
        printf("%d ", QueueBack(&q));
        QueuePop(&q);
    }
    printf("\n");
    printf("%d\n", (int)QueueSize(&q));
    QueueDestroy(&q);
}

int main(void)
{
    printf("栈测试：\n");
    StackTest();
    printf("队列测试：\n");
    QueueTest();
    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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

---

---

看完给个关注，多谢了！！！