栈
栈的定义
栈（stack）是限定仅在表尾进行插入和删除操作的线性表。表尾端被称为栈顶，表头端称为栈底。向一个栈插入（删除）元素称作进栈、入栈、压栈（出栈、退栈）。后进先出，入栈：把元素放在栈的顶部
栈的顺序存储结构
1
2
3
4
5
6
7
8
| typedef struct Stack{
int data[100];
int top;
} Stack;
void intStack(Stack* stack){
stack->top=-1;
}
|
- 如何判断栈是否为空：top=-1的时候，此时没有新元素入栈，所以栈就是空的，有元素增加，top就会增加，即判断stack是否为-1
1
2
3
| int isEmpty(Stack* stack){
return stack->top==-1;
}
|
- 入栈：循环top+1，存储元素在top所指向的位置
1
2
3
4
5
6
7
8
9
| void push(Stack* stack,int value){
if(stack->top<99){
stack->top++;
stack->data[stack->top]=value;
}
else{
printf("栈满，无法入栈\n");
}
}
|
- 出栈：删除栈顶元素，还要把栈顶元素保存在变量之中（可以看到删除元素是谁），删除元素只需要top–，依次从上到下删除，但是并没有在内存中删除。
1
2
3
4
5
6
7
8
9
10
11
| int pop(Stack* stack){
if(!isEmpty(stack)){
int value = stack->data[stack->top];
stack->top--;
return value;
}
else{
printf("栈空，无法出栈\n");
return -1;
}
}
|
栈的链式存储结构
只能固定在一个栈点添加，或删除元素
1
2
3
4
| typedef struct Stack{
int data;
struct Stack* next;
} Stack;
|
1
2
3
4
5
6
| int push(Stack *head,int e){
Stack *newNode = (Stack*)malloc(sizeof(Stack));
newNode->data = e;
newNode->next = newNode;
return 1;
}
|
1
2
3
4
5
6
7
8
9
10
11
| int pop(Stack *head,int *value){
if(head->next==NULL){
printf("空的\n");
return 0;
}
*value = head->next->data;
Stack *tempNode =head->next;
head->next =tempNode->next;
free(tempNode);
return 1;
}
|
队列
队列的定义
队列（queue）是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端删除元素。队列中，允许插入的一端为队尾（rear），允许删除的一段叫做队头（front），出队顺序和入队顺序一样
队列的顺序结构实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| typedef struct{
int data[100];
int front;
int rear;
} Queue;
void initQueue(Queue *q){
q->front = 0;
q->rear = 0;
}
int isEmpty(Queue *q){
return q->front == q->rear;
}
|
1
2
3
4
5
6
7
8
9
| int deQueue(Queue *q){
if (isEmpty(q)){
printf("队列为空，无法出队\n");
return -1;
}
int value = q->data[q->front];
q->front = q->front + 1;
return value;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void enQueue(Queue *q,int value){
if(isFull(q)){
if(q->front>0){
int i;
for(i=0;i<q->rear -q ->front;i++){
q->data[i] = q->data[q->front+i];
}
q->rear =q->rear - q->front;
q->front = 0;
} else{
printf("队列已满，无法入队\n");
return;
}
}
q->data[q->rear]=value;
q->rear++;
}
|
- 上述操作都是基于栈内存声明的队列。
- 队列（动态分配内存）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| typedef struct {
int *data;
int front;
int rear;
} Queue;
Queue* initQueue(){
Queue *q =(Queue *)malloc(sizeof(Queue));
q->data = (int *)malloc(100 * sizeof(int));
q->front = 0;
q->rear = 0;
return q;
}
|
循环队列
- 普通队列的缺点：队尾指针超出了数组的索引范围，需要大量移动元素
- 循环队列特点：队尾永远不会超出数组范围，当对位走到最后一位元素，下一步又回到数组开头
- 循环队列入队
1
2
3
4
5
6
7
8
9
| void enQueue(Queue *q,int value){
if((q->rear+1)%100 == q->front){
printf("队列已满，无法入队\n");
return;
}
q->data[q->rear] = value;
q->rear = (q->rear + 1)% 100;
}
|
1
2
3
4
5
6
7
8
9
| int deQueue(Queue *q){
if(q->front == q->rear){
printf("队列为空，无法出队\n");
return -1;
}
int value = q->data[q->front];
q->front = (q->front + 1) % 100;
return value;
}
|
队列的链式存储结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| typedef struct QueueNode{
int data;
struct QueueNode *next;
} QueueNode;
typedef struct {
QueueNode *front;
QueueNode *rear;
} Queue;
Queue* initializeQueue(){
Queue *newNode = (Queue *)malloc(sizeof(Queue));
QueueNode *newnode = (QueueNode *)malloc(sizeof(QueueNode));
newNode->data = 0;
newNode->next = NULL;
newQueue->front = newNode;
newQueue->rear = newNode;
return newQueue;
}
|
1
2
3
4
5
6
7
| int isEmpty(Queue *queue){
if(queue->front == queue->rear){
return 1;
} else{
return 0;
}
}
|
链式存储如何入队：
1.创建新节点
2.把尾节点的next指向新节点
3.把rear指针移动到新节点
1
2
3
4
5
6
7
| void enQueue(Queue *queue,int element){
QueueNode *newNode = (QueueNode*)malloc(sizeof(QueueNode));
newNode->data = element;
newNode->next = NULL;
queue->rear->next = newNode;
queue->rear = newNode;
}
|
如何出队
1.把头节点的next指向第一个节点的next
2.free()释放原本的第一个节点
1
2
3
4
5
6
7
8
9
10
| int dequeue(Queue *queue,int *element){
QueueNode *node = queue->front->next;
*element = node->data;
queue->front->next = node->next;
if(queue->rear == node){
queue->rear = queue->front;
}
free(node);
return 1;
}
|
