基础数据结构_队列和栈转换

发表于2021-10-15更新于2025-09-28阅读次数

链队

头结点需要重新设计。

如果头结点只有一个next节点。入队为O(1)但出队无法都同时为O(1)。我们需要另外设计一个尾指针。

1
2
3
4
5
6
7
8
9
10
typedef struct LinkQueue
{
    struct Node * front;
    struct Node * tail;
}LinkQueue,Head;
typedef struct QNode
{
    ElemType data;
    struct Node * next;
}QNode;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#pragma once
//.h
typedef int ElemType;
typedef struct LinkQueue
{
    struct QNode* front;
    struct QNode* tail;
}LinkQueue, Head;
typedef struct QNode
{
    ElemType data;
    struct QNode* next;
}QNode;
void Init_lqueue(LinkQueue* plq);
bool Push_lqueue(LinkQueue* plq, ElemType val);
bool Pop_lqueue(LinkQueue* plq, ElemType* pval);
bool Front_lqueue(LinkQueue* plq, ElemType* pval);
int Get_Length_lqueue(LinkQueue* plq);
bool Is_Empty_lqueue(LinkQueue* plq);
void Clear_lqueue(LinkQueue* plq);
void Destroy_lqueue(LinkQueue* plq);
void Show_lqueue(LinkQueue* plq);
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
//.c
#include"lqueue.h"
#include<assert.h>
#include<stdlib.h>
#include<stdio.h>
QNode* Buy_node()
{
	QNode* s = (QNode*)malloc(sizeof(QNode));
	return s;
}
void Init_lqueue(LinkQueue* plq)
{
	assert(plq != NULL);
	QNode* node = Buy_node();
	node->next = NULL;
	plq->front = node;
	plq->tail = node;
}
//入队，尾插
bool Push_lqueue(LinkQueue* plq, ElemType val)
{
	assert(plq != NULL);
	QNode* newnode = Buy_node();
	if (NULL == newnode)return false;
	newnode->next = NULL;
	plq->tail->next = newnode;

	plq->tail = newnode;

	newnode->data = val;
	return true;
}
bool Pop_lqueue(LinkQueue* plq, ElemType* pval)
{
	assert(plq != NULL);
	if (Is_Empty_lqueue(plq))
	{
		return false;
	}
	QNode* oldnode = plq->front->next;
	*pval = oldnode->data;
	//头删
	plq->front->next = oldnode->next;
	free(oldnode);
	oldnode = NULL;
	return true;
}
bool Front_lqueue(LinkQueue* plq, ElemType* pval)
{
	assert(plq != NULL);
	if (Is_Empty_lqueue(plq))
	{
		return false;
	}
	*pval = plq->front->next->data;
	return true;
}
bool Is_Empty_lqueue(LinkQueue* plq)
{
	assert(plq != NULL);
	return plq->front->next == NULL;
}
int Get_Length_lqueue(LinkQueue* plq)
{
	assert(plq != NULL);
	int count = 0;
	QNode* p = plq->front->next;
	while (p != NULL)
	{
		count++;
		p = p->next;
	}
	return count;
}
void Clear_lqueue(LinkQueue* plq)
{
	assert(plq != NULL);
	int val;
	while (!Is_Empty_lqueue(plq))
	{
		Pop_lqueue(plq, &val);
	}
}
void Destroy_lqueue(LinkQueue* plq)
{
	assert(plq != NULL);
	Clear_lqueue(plq);
	free(plq->front);
	plq->front = NULL;
	plq->tail = NULL;
}
void Show_lqueue(LinkQueue* plq)
{
	assert(plq != NULL);
	QNode* p = plq->front->next;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

链栈

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
//.h
//LinkStack.h
#ifndef LINKSTACK_H
#define LINKSTACK_H

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define NULLPTR -3

typedef int Status;

typedef int SElemType;
typedef struct StackNode
{
    SElemType data;
    struct StackNode* next;
}StackNode, * PStackNode;
typedef struct
{
    StackNode* top;
    int cursize;
}LinkStack;

Status InitStack(LinkStack* ps);
void DestroyStack(LinkStack* ps);
void ClearStack(LinkStack* ps);
int StackLength(const LinkStack* ps);
bool StackEmpty(const LinkStack* ps);
Status Push_Stack(LinkStack* ps, SElemType val);
Status GetTop_Stack(LinkStack* ps, SElemType* pval);
Status Pop_Stack(LinkStack* ps, SElemType* pval);
bool DelFront_Stack(LinkStack* ps);
void Show_Stack(LinkStack* ps);
#endif
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
//LinkStack.cpp
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<stdio.h>
#include"LinkStack.h"
StackNode* Buynode()
{
    StackNode* newnode = (StackNode*)malloc(sizeof(StackNode));
    if (NULL != newnode)
    {
        memset(newnode, 0, sizeof(StackNode));
    }
    return newnode;
}
Status InitStack(LinkStack* ps)
{
    assert(ps != NULL);
    ps->top = Buynode();//头结点
    if (NULL == ps->top)return OVERFLOW;

    ps->cursize = 0;
    return OK;
}
void DestroyStack(LinkStack* ps)
{
    assert(ps != NULL);
    ClearStack(ps);
    free(ps->top);
    ps->top = NULL;
}
void ClearStack(LinkStack* ps)
{
    assert(ps != NULL);
    while (ps->cursize != 0)
    {
        DelFront_Stack(ps);
    }
}
int StackLength(const LinkStack* ps)
{
    assert(ps != NULL);
    return ps->cursize;
}
bool StackEmpty(const LinkStack* ps)
{
    assert(ps != NULL);
    return ps->cursize == 0;
}
Status Push_Stack(LinkStack* ps, SElemType val)
{
    assert(ps != NULL);
    StackNode* newnode = Buynode();
    if (NULL == newnode)return OVERFLOW;

    newnode->next = ps->top->next;
    ps->top->next = newnode;

    newnode->data = val;

    ps->cursize += 1;
    return OK;
}
Status GetTop_Stack(LinkStack* ps, SElemType* pval)
{
    assert(ps != NULL);
    if (pval == NULL)return NULLPTR;
    if (ps->cursize <= 0)return false;
    *pval = ps->top->next->data;
    return OK;
}
Status Pop_Stack(LinkStack* ps, SElemType* pval)
{
    assert(ps != NULL);
    if (pval == NULL)return NULLPTR;
    if (ps->cursize <= 0)return ERROR;
    GetTop_Stack(ps, pval);
    DelFront_Stack(ps);
    return OK;
}
bool DelFront_Stack(LinkStack* ps)
{
    assert(ps != NULL);
    if (ps->cursize <= 0)return false;
    StackNode* p = ps->top->next;
    ps->top->next = p->next;
    free(p);
    ps->cursize -= 1;
    return true;
}
void Show_Stack(LinkStack* ps)
{
    StackNode* p = ps->top->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    //printf("\n");
}

栈转队列

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
//.h
#ifndef MYQUEUE_H
#define MYQUEUE_H
#include"../../Stack/Stack/LinkStack.h"
#include"../../QueueTest/QueueTest/lqueue.h"
typedef int ElemType;
typedef struct MyQueue
{
	LinkStack s1;
	LinkStack s2;
}MyQueue;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define NULLPTR -3

typedef int Status;
void Init_MyQueue(MyQueue* pmyq);
Status Push_MyQueue(MyQueue* pmyq, ElemType val);
Status Pop_MyQueue(MyQueue* pmyq, ElemType* pval);
Status Front_MyQueue(MyQueue* pmyq, ElemType* pval);
int Get_Length_MyQueue(MyQueue* pmyq);
bool Is_Empty_MyQueue(MyQueue* pmyq);
void Clear_MyQueue(MyQueue* pmyq);
void Destroy_MyQueue(MyQueue* pmyq);
void Show_MyQueue(MyQueue* pmyq);
#endif

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
108
//.c
#include"MyQueue.h"
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>

void Init_MyQueue(MyQueue* pmyq)
{
	InitStack(&pmyq->s1);
	InitStack(&pmyq->s2);
}
Status Push_MyQueue(MyQueue* pmyq, ElemType val)
{
	return Push_Stack(&pmyq->s1, val);
}
Status Pop_MyQueue(MyQueue* pmyq, ElemType* pval)
{
	if (!StackEmpty(&pmyq->s2))
	{
		return Pop_Stack(&pmyq->s2, pval);
	}
	else
	{
		int val;
		while(!StackEmpty(&pmyq->s1))
		{
			Pop_Stack(&pmyq->s1, &val);
			Push_Stack(&pmyq->s2, val);
		}
		if (StackEmpty(&pmyq->s2))
		{
			return FALSE;
		}
		else
		{
			return Pop_Stack(&pmyq->s2, pval);
		}
	}
}
Status Front_MyQueue(MyQueue* pmyq, ElemType* pval)
{
	if (!StackEmpty(&pmyq->s2))
	{
		return GetTop_Stack(&pmyq->s2, pval);
	}
	else
	{
		int val;
		while (!StackEmpty(&pmyq->s1))
		{
			Pop_Stack(&pmyq->s1, &val);
			Push_Stack(&pmyq->s2, val);
		}
		if (StackEmpty(&pmyq->s2))
		{
			return FALSE;
		}
		else
		{
			return GetTop_Stack(&pmyq->s2, pval);
		}
	}
}
int Get_Length_MyQueue(MyQueue* pmyq)
{
	return StackLength(&pmyq->s1) + StackLength(&pmyq->s2);
}
bool Is_Empty_MyQueue(MyQueue* pmyq)
{
	return Get_Length_MyQueue(pmyq) == 0;
}
void Clear_MyQueue(MyQueue* pmyq)
{
	ClearStack(&pmyq->s1);
	ClearStack(&pmyq->s2);
}
void Destroy_MyQueue(MyQueue* pmyq)
{
	DestroyStack(&pmyq->s1);
	DestroyStack(&pmyq->s2);
}
void Show_MyQueue(MyQueue* pmyq)
{
	StackNode* p = pmyq->s1.top->next;
	p = pmyq->s1.top->next;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}

	LinkStack s3;
	InitStack(&s3);
	p = pmyq->s2.top->next;
	while (p != NULL)
	{
		Push_Stack(&s3, p->data);
		p = p->next;
	}

	p = s3.top->next;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

队列转栈

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
//.h
//MyStack.h
#ifndef MYSTACK_H
#define MYSTACK_H

#include"../../Stack/Stack/LinkStack.h"
#include"../../QueueTest/QueueTest/lqueue.h"

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define NULLPTR -3

typedef int Status;

typedef int ElemType;

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

Status InitMyStack(MyStack* pmys);
void DestroyMyStack(MyStack* pmys);
void ClearMyStack(MyStack* pmys);
int MyStackLength(const MyStack* pmys);
bool EmptyMyStack(const MyStack* pmys);
Status Push_MyStack(MyStack* pmys, ElemType val);
Status GetTop_MyStack(MyStack* pmys, ElemType* pval,int *flag);
Status Pop_MyStack(MyStack* pmys, ElemType* pval);
bool DelFront_LQueue(LinkQueue* plq);
void Show_MyStack(MyStack* pmys);
#endif
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
//.c
#include"MyStack.h"
#include<stdlib.h>
#include<stdio.h>
Status InitMyStack(MyStack* pmys)
{
	Init_lqueue(&pmys->q1);
	Init_lqueue(&pmys->q2);
	return OK;
}
void DestroyMyStack(MyStack* pmys)
{
	Destroy_lqueue(&pmys->q1);
	Destroy_lqueue(&pmys->q2);

}
void ClearMyStack(MyStack* pmys)
{
	Clear_lqueue(&pmys->q1);
	Clear_lqueue(&pmys->q2);

}
int MyStackLength(MyStack* pmys)
{
	return Get_Length_lqueue(&pmys->q1) + Get_Length_lqueue(&pmys->q2);
}
bool EmptyMyStack(MyStack* pmys)
{
	return MyStackLength(pmys) == 0;
}
Status Push_MyStack(MyStack* pmys, ElemType val)
{
	return Push_lqueue(&pmys->q2, val);
}
bool MostHaveOneNode_LQueue(LinkQueue* plq)
{
	return Get_Length_lqueue(plq)<=1;
}
Status GetTop_MyStack(MyStack* pmys, ElemType* pval, int *flag)
{
	int val;
	bool goodPop = false;
	if (Get_Length_lqueue(&pmys->q1) == 1)
	{
		*pval = pmys->q1.front->next->data;
		*flag = 1;
		return OK;
	}
	if (!Is_Empty_lqueue(&pmys->q2))
	{
		while (!MostHaveOneNode_LQueue(&pmys->q2))
		{
			goodPop = Pop_lqueue(&pmys->q2, &val);
			if(goodPop)Push_lqueue(&pmys->q1, val);
		}
		*flag = 2;
		return Front_lqueue(&pmys->q2, pval);
	}
	else
	{
		while (!MostHaveOneNode_LQueue(&pmys->q1))
		{
			goodPop = Pop_lqueue(&pmys->q1, &val);
			if (goodPop)Push_lqueue(&pmys->q2, val);
		}
		*flag = 1;
		return Front_lqueue(&pmys->q1, pval);
	}
	*flag = 0;
	return FALSE;
}
Status Pop_MyStack(MyStack* pmys, ElemType* pval)
{
	if (EmptyMyStack(pmys))return FALSE;
	int flag = 0;
	GetTop_MyStack(pmys,pval,&flag);
	if (flag != 0)
	{
		if (flag == 1)
		{
			DelFront_LQueue(&pmys->q1);
		}
		else if (flag == 2)
		{
			DelFront_LQueue(&pmys->q2);
		}
	}
	return TRUE;
	/*
	int val;
	if (!Is_Empty_lqueue(&pmys->q2))
	{
		while (!MostHaveOneNode_LQueue(&pmys->q2))
		{
			Pop_lqueue(&pmys->q2, &val);
			Push_lqueue(&pmys->q1, val);
		}
		return Pop_lqueue(&pmys->q2, pval);
	}
	else if (!Is_Empty_lqueue(&pmys->q1))
	{
		while (!MostHaveOneNode_LQueue(&pmys->q1))
		{
			Pop_lqueue(&pmys->q1, &val);
			Push_lqueue(&pmys->q2, val);
		}
		return Pop_lqueue(&pmys->q1, pval);
	}
	return FALSE;
	*/
}
bool DelFront_LQueue(LinkQueue *plq)
{
	if (plq->front->next == NULL)return false;
	QNode* s = plq->front->next;
	plq->front->next = s->next;
	plq->tail = plq->front;
	free(s);
	return true;
}
void Print_Queue_Reverse(LinkQueue* plq)
{
	LinkStack ls;
	InitStack(&ls);
	QNode* p = plq->front->next;
	while (p != NULL)
	{
		Push_Stack(&ls, p->data);
		p = p->next;
	}
	Show_Stack(&ls);
	DestroyStack(&ls);
}
void Show_MyStack(MyStack* pmys)
{
	Print_Queue_Reverse(&pmys->q2);
	Print_Queue_Reverse(&pmys->q1);
	printf("\n");
}

测试

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
//TestMyQueue.cpp
#if 0
#include"MyQueue.h"
int main()
{
	MyQueue myq;
	Init_MyQueue(&myq);
	int n = 10;
	for (int i = 0; i < n;i++)
	{

		Push_MyQueue(&myq, i);
		Show_MyQueue(&myq);
	}
	int val;
	for (int i = 0; i < n;i++)
	{

		Pop_MyQueue(&myq, &val);
		Show_MyQueue(&myq);
	}
	Destroy_MyQueue(&myq);
	//Show(&lq);
	return 0;
}
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//TestMyStack.cpp

#include"MyStack.h"
int main()
{
	MyStack myq;
	InitMyStack(&myq);
	int n = 10;
	for (int i = 0; i < n;i++)
	{
		Push_MyStack(&myq, i);
		Show_MyStack(&myq);
	}
	int val;
	for (int i = 0; i < n;i++)
	{
		Pop_MyStack(&myq, &val);
		Show_MyStack(&myq);
	}
	DestroyMyStack(&myq);
	//Show(&lq);
	return 0;
}