栈,队列与循环队列 模拟

栈 模拟

typedef int STDataType;
typedef struct Stack
{
    STDataType* p;
    int top;
    int capacity;
}ST;

//初始化​​
#define INIT_CAPACITY 5
void STInit(ST* ps)
{
    assert(ps);
    ps->p = (STDataType*)malloc(sizeof(STDataType) * INIT_CAPACITY);
    if (ps->p == NULL)
    {
        perror("STInit::Malloc");
        return;
    }
    ps->top = 0;
    ps->capacity = INIT_CAPACITY;
}

//栈的销毁​​
void STDestroy(ST* ps)
{
    assert(ps);
    free(ps->p);
    ps->p = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

//压栈​​
void STPush(ST* ps, STDataType x)
{
    assert(ps);
    if (ps->top == ps->capacity)
    {
        STDataType* pp = (STDataType*)realloc(ps->p, sizeof(STDataType) * (ps->capacity) * 2);
        if (pp == NULL)
        {
            perror("STPush::Realloc");
            return;
        }
        ps->p = pp;
        ps->capacity *= 2;
    }
    ps->p[ps->top] = x;
    ps->top++;
}

//出栈​​
void STPop(ST* ps)
{
    assert(ps);
    assert(!STEmpty(ps));
    ps->top--;
}

//求栈元素个数​​
int STSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

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

//求栈顶元素​​
int STTop(ST* ps)
{
    assert(ps);
    assert(!STEmpty(ps));
    return ps->p[ps->top - 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
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

队列 模拟

typedef int QueueDataType;
typedef struct QueueNode
{
	QueueDataType data;
	struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
	int size;
}Queue;

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->size = 0;
	pq->head = nullptr;
	pq->tail = nullptr;
}

//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	QueueNode* next = nullptr;
	while (cur != nullptr)
	{
		next = cur->next;
		delete cur;
		cur = next;
	}
	pq->size = 0;
	pq->head = nullptr;
	pq->tail = nullptr;
}

//入队
void QueuePush(Queue* pq, QueueDataType x)
{
	assert(pq);
	QueueNode* newnode = new QueueNode;
	newnode->data = x;
	newnode->next = nullptr;
	if (QueueEmpty(pq))
	{
		pq->head = newnode;
		pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

//出队
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode* del = pq->head;
	pq->head = pq->head->next;
	pq->size--;
	if (pq->size==0)
	{
		pq->tail = nullptr;
	}
	delete del;
}

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	return pq->size == 0;
}

//求元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}​

//求队头元素
QueueDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->size > 0);
	return pq->head->data;
}

//求队尾元素​
QueueDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->size > 0);
	return pq->tail->data;
}
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

循环队列 模拟

typedef int CQueueDataType;
typedef struct 
{
    int capacity;
    int front;
    int rear;
    CQueueDataType* ptr;
} MyCircularQueue;

//构造器，设置队列长度为 k 
MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->capacity=k;
    obj->ptr = (CQueueDataType*)malloc(sizeof(CQueueDataType)*(k+1));
    obj->front=obj->rear=0;
    return obj;
}

//检查循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->front==obj->rear;
}

//检查循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return (obj->rear+1)%(obj->capacity+1)==obj->front;
}

//向循环队列插入一个元素。如果成功插入则返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, CQueueDataType value) 
{
    if (myCircularQueueIsFull(obj)==true)
    {
        return false;
    }
    *(obj->ptr+obj->rear)=value;
    obj->rear=(obj->rear+1)%(obj->capacity+1);
    return true;
}

//从循环队列中删除一个元素。如果成功删除则返回真
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj)==true)
    {
        return false;
    }
    obj->front=(obj->front+1)%(obj->capacity+1);
    return true;
}

//从队首获取元素。如果队列为空，返回 -1 
int myCircularQueueFront(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj)==true)
    {
        return -1;
    }
    return *(obj->ptr+obj->front);
}

//获取队尾元素。如果队列为空，返回 -1
int myCircularQueueRear(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj)==true)
    {
        return -1;
    }
    if (obj->rear==0)
    {
        return *(obj->ptr+obj->capacity);
    }
    else
    {
        return *(obj->ptr+(obj->rear-1));
    }
}

//释放资源
void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->ptr);
    free(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
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