数据结构9：栈和队列的相互实现

队列实现栈

头文件

Queue.h

#pragma once

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

typedef int QListDataType;

typedef struct QListNode {
	QListDataType val;
	struct QListNode* next;
}QListNode;

typedef struct Queue {
	QListNode* head;
	QListNode* tail;
	int size;
}Queue;

//初始化
void QueueInit(Queue* pq);

//销毁
void QueueDestroy(Queue* pq);

//队尾入队列
void QueuePush(Queue* pq, QListDataType x);

//对头出队列
void QueuePop(Queue* pq);

//获取队列头部元素
QListDataType QueueFront(Queue* pq);

//获取队列队尾元素
QListDataType QueueBack(Queue* pq);

//获取队列中有效元素个数
int QueueSize(Queue* pq);

//检查队列是否为空，空返回真，非空返回假
bool QueueEmpty(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

MyStack.h

#pragma once

#include"Queue.h"

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

//初始化
MyStack* myStackCreate();

//压栈
void myStackPush(MyStack* obj, int x);

//出栈并返回栈顶元素
int myStackPop(MyStack* obj);

//获取栈顶元素
int myStackTop(MyStack* obj);

//判空
bool myStackEmpty(MyStack* obj);

//销毁
void myStackFree(MyStack* obj);
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

实现文件

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}

//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QListNode* cur = pq->head;
	while (cur)
	{
		QListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}

//队尾入队列
void QueuePush(Queue* pq, QListDataType x)
{
	assert(pq);

	QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}

//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->size);

	QListNode* tmp = pq->head->next;
	free(pq->head);
	pq->head = tmp;
	if (pq->head == NULL)
		pq->tail = NULL;

	pq->size--;
}

//获取队列头部元素
QListDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->size);

	return pq->head->val;
}

//获取队列队尾元素
QListDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->size);

	return pq->tail->val;
}

//获取队列中有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

//检查队列是否为空，空返回真，非空返回假
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 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
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

MyStack.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"MyStack.h"

MyStack* myStackCreate() {
    MyStack* new = (MyStack*)malloc(sizeof(MyStack));
    if (new == NULL)
    {
        perror("malloc fail");
        return NULL;
    }

    QueueInit(&(new->q1));
    QueueInit(&(new->q2));

    return new;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);

    if (QueueEmpty(&(obj->q1)))
    {
        QueuePush(&(obj->q2), x);
    }
    else
    {
        QueuePush(&(obj->q1), x);
    }
}

int myStackPop(MyStack* obj) {
    assert(obj);
    assert(!(QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2))));

    Queue* full = &(obj->q2);
    Queue* empty = &(obj->q1);
    if (QueueEmpty(&(obj->q2)))
    {
        full = &(obj->q1);
        empty = &(obj->q2);
    }

    while (QueueSize(full) > 1)
    {
        int tmp = QueueFront(full);
        QueuePop(full);
        QueuePush(empty, tmp);
    }

    int ret = QueueFront(full);
    QueuePop(full);

    return ret;
}

int myStackTop(MyStack* obj) {
    assert(obj);
    assert(!(QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2))));

    int ret = 0;
    if (QueueEmpty(&(obj->q1)))
    {
        ret = QueueBack(&(obj->q2));
    }
    else
    {
        ret = QueueBack(&(obj->q1));
    }

    return ret;
}

bool myStackEmpty(MyStack* obj) {
    assert(obj);

    return (QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2)));
}

void myStackFree(MyStack* obj) {
    assert(obj);

    QueueDestroy(&(obj->q1));
    QueueDestroy(&(obj->q2));

    free(obj);
    obj = 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

栈实现队列

头文件

Stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

#define CAPACITY_INIT 4

typedef int STDataType;

typedef struct Stack {
	STDataType* a;
	int size;
	int capacity;
}Stack;

//栈的初始化
void StackInit(Stack* ps);

//压栈
void StackPush(Stack* ps, STDataType x);

//出栈
void StackPop(Stack* ps);

//获取栈顶元素
STDataType StackTop(Stack* ps);

//获取栈中有效数据个数
int StackSize(Stack* ps);

//检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);

//栈的销毁
void StackDestroy(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
34
35
36

MyQueue.h

#pragma once
#include"Stack.h"
#include<stdbool.h>

typedef struct {
    Stack in;
    Stack out;
} MyQueue;

//初始化
MyQueue* myQueueCreate();

//将元素 x 推到队列的末尾
void myQueuePush(MyQueue* obj, int x);

//从队列的开头移除并返回元素
int myQueuePop(MyQueue* obj);

//返回队列开头的元素
int myQueuePeek(MyQueue* obj);

//如果队列为空，返回 true ；否则，返回 false
bool myQueueEmpty(MyQueue* obj);

//销毁
void myQueueFree(MyQueue* obj);
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

实现文件

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
#include<string.h>

//栈的初始化
void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * CAPACITY_INIT);
	if (ps->a == NULL)
	{
		perror("malloc fail!");
		return;
	}
	ps->size = 0;
	ps->capacity = CAPACITY_INIT;
}

//判断是否需要扩容
void StackChekCapacity(Stack* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		ps->a = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2);
		if (ps->a == NULL)
		{
			perror("realloc fail!");
			return;
		}
		ps->capacity *= 2;
	}
}

//压栈
void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	StackChekCapacity(ps);
	ps->a[ps->size++] = x;
}

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

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

//获取栈中有效数据个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->size;
}

//检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->size == 0)
		return 1;
	else
		return 0;
}

//栈的销毁
void StackDestroy(Stack* ps)
{
	assert(ps);
	ps->size = 0;
	ps->capacity = 0;
	free(ps->a);
}
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

MyQueue.c

#define _CRT_SECURE_NO_WARNINGS 1

#include<string.h>
#include"MyQueue.h"

MyQueue* myQueueCreate() {
    MyQueue* new = (MyQueue*)malloc(sizeof(MyQueue));
    if (new == NULL)
    {
        perror("malloc fail");
        return NULL;
    }

    StackInit(&new->in);
    StackInit(&new->out);

    return new;
}

void myQueuePush(MyQueue* obj, int x) {
    assert(obj);

    StackPush(&obj->in, x);
}

int myQueuePop(MyQueue* obj) {
    assert(obj);
    assert(!(StackEmpty(&obj->in) && StackEmpty(&obj->out)));

    if (StackEmpty(&obj->out))
    {
        while (StackSize(&obj->in) > 0)
        {
            int tmp = StackTop(&obj->in);
            StackPop(&obj->in);
            StackPush(&obj->out, tmp);
        }
    }

    int ret = StackTop(&obj->out);
    StackPop(&obj->out);

    return ret;
}

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    assert(!(StackEmpty(&obj->in) && StackEmpty(&obj->out)));

    if (StackEmpty(&obj->out))
    {
        while (StackSize(&obj->in) > 0)
        {
            int tmp = StackTop(&obj->in);
            StackPop(&obj->in);
            StackPush(&obj->out, tmp);
        }
    }

    int ret = StackTop(&obj->out);
    return ret;
}

bool myQueueEmpty(MyQueue* obj) {
    assert(obj);

    return StackEmpty(&obj->in) && StackEmpty(&obj->out);
}

void myQueueFree(MyQueue* obj) {
    assert(obj);

    StackDestroy(&obj->in);
    StackDestroy(&obj->out);

    free(obj);
    obj = 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