栈
栈是一种特殊的线性表,其只允许在固定的一端进行插入删除,进行数据的插入和删除操作的一段称为栈顶,而另一端称为栈底。栈之中的元素遵循后进先出的原则。
- 压栈:栈的插入操作叫做进栈 / 压栈 / 入栈,入数据在栈顶。
- 出栈:栈的删除操作叫出栈,出数据也在栈顶。
C语言中栈的实现
栈的实现一般可用数组或链表形式实现,相对而言,数组的结构更好一些,因为数组的尾插时间复杂度为O(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
| #pragma once #include<stdio.h> #include<stdlib.h>
typedef int STDataType; typedef struct Stack { STDataType* _a; int _top; int _capacity; }Stack;
void StackInit(Stack* ps);
void StackPush(Stack* ps, STDataType data);
void StackPop(Stack* ps);
STDataType StackTop(Stack* ps);
int StackSize(Stack* ps);
int StackEmpty(Stack* ps);
void StackDestroy(Stack* ps);
void Realo(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 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
| #define _CRT_SECURE_NO_WARNINGS 1 #include "stack.h"
void StackInit(Stack* ps) { ps->_capacity = 20; ps->_a = (STDataType*)malloc(sizeof(STDataType) * ps->_capacity); ps->_top = 0; }
void Realo(Stack* ps) { ps->_capacity *= 2; ps->_a = (STDataType*)realloc(ps->_a, sizeof(STDataType)* ps->_capacity); }
void StackPush(Stack* ps, STDataType data) { if (ps->_top == ps->_capacity) { Realo(ps); } ps->_a[ps->_top] = data; ps->_top++; }
void StackPop(Stack* ps) { if (ps->_top) ps->_top--; }
STDataType StackTop(Stack* ps) { if(ps->_top) return ps->_a[ps->_top - 1]; return -1; }
int StackSize(Stack* ps) { return ps->_top; }
int StackEmpty(Stack* ps) { if (ps->_top == 0) return 1; else return 0; }
void StackDestroy(Stack* ps) { free(ps->_a); ps->_a = NULL; ps->_capacity = 0; ps->_top = 0; }
|
队列
队列也是一种特殊的线形表,其只允许在一段插入数据,在另一端删除数据,遵循先进先出的原则
- 入队:从队尾进行插入数据的操作。
- 出队:从队头进行数据删除的操作。
C语言中队列的实现
队列的实现可以使用数组和链表,但是使用一个带尾指针的单链表效果更优。
代码如下:
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
| #include<stdio.h> #include<stdlib.h>
typedef int QDataType;
typedef struct QListNode { struct QListNode* _next; QDataType _data; }QNode;
typedef struct Queue { QNode* _front; QNode* _rear; size_t size; }Queue;
void QueueInit(Queue* q);
void QueuePush(Queue* q, QDataType data);
void QueuePop(Queue* q);
QNode* CreatNode(QDataType data);
QDataType QueueFront(Queue* q);
QDataType QueueBack(Queue* q);
int QueueSize(Queue* q);
int QueueEmpty(Queue* q);
void QueueDestroy(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 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
| #define _CRT_SECURE_NO_WARNINGS 1 #include "qnode.h"
void QueueInit(Queue* q) { q->_front = NULL; q->_rear = NULL; q->size = 0; }
QNode* CreatNode(QDataType data) { QNode* newNode = (QNode*)malloc(sizeof(QNode)); newNode->_data = data; newNode->_next = NULL; return newNode; }
void QueuePush(Queue* q, QDataType data) { QNode* newNode = CreatNode(data); if (q->_rear == NULL) { q->_front = newNode; q->_rear = newNode; } else { q->_rear->_next = newNode; q->_rear = newNode; } q->size++; }
void QueuePop(Queue* q) { if (q->_front) { QNode* next = q->_front->_next; free(q->_front); q->_front = next; if (q->_front == NULL) q->_rear = NULL; q->size--; } }
QDataType QueueFront(Queue* q) { int empty = QueueEmpty(q); if (!empty) return q->_front->_data; return -1;
}
QDataType QueueBack(Queue* q) { int empty = QueueEmpty(q); if (!empty) return q->_rear->_data; return -1; }
int QueueSize(Queue* q) { return q->size; }
int QueueEmpty(Queue* q) { if (q->_front == NULL) return 1; else return 0; }
void QueueDestroy(Queue* q) { QNode* cur = q->_front; while (cur) { QNode* next = cur->_next; free(cur); cur = next; } q->_front = NULL; q->_rear = NULL; q->size = 0; }
|