数据结构——基础3
回顾：
线性表——顺序表（数组）、链表（结点）
链表插入方法：头插法、尾插法
双向链表：*next *front
1、栈——stack 先进后出（FILO）的数据结构，栈不为空时，只能看到栈顶元素。
结构定义
#define MaxCnt 50//栈当中元素的最大个数
struct Stack{//栈的定义
EleType data[MaxCnt];//栈的数据域
int top;//栈顶元素位置
};
链栈是使用类似于链表的结构实现。
共享栈，又称对顶栈，两个栈共享同一内存空间。
使用顺序表实现顺序栈
#include <stdlib.h>
typedef struct stack{
int *data;
int size,cap; //元素数量，容量
}stack;
stack *init_stack(int x){
stack *s = (stack *)malloc(sizeof(stack));
s->data = (int *)malloc(sizeof(int) * x);
s->size = 0, s->cap = x;
return s;
}
void delete_stack(stack *s){
free(s->data);
free(s);
}
//入栈
int push(stack *s, int x){
if(s->size == s->cap){
s->data = (int *)realloc(s->data, s->cap * 2);
s->cap *= 2;
}
s->data[s->size] = x;
s->size++;
return 0;
}
//出栈
int pop(stack *s){
if(s->size == 0){
return -1;
}
s->size--;
return 0;
}
//获取栈顶元素
int top(stack *s){
if(s->size == 0){
return -1;
}
return s->data[s->size - 1];
}
void show_stack(stack *s){
printf("size -> %d, cap -> %d\n", s->size, s->cap);
for(int i = 0; i < s->size; i++){
printf("%d ",s->data[i]);
}
printf("\n------------------------------\n");
}
int main(){
//入栈push——>出栈pop(带或不带返回值)——>获取栈顶元top
int n,m;
scanf("%d%d",&n ,&m);//操作次数，容量
stack *s = init_stack(m);
for(int i = 0; i < n; i++){
int t;
scanf("%d", &t);
if(t == 0){
int x;
scanf("%d", &x);
push(s, x);
}
else if(t == 1){
pop(s);
}
else{
printf("top -> %d\n", top(s));
}
show_stack(s);
}
delete_stack(s);
return 0;
}
运行结果：
链栈
头插法（O(1)）,尾插法（O(n)）
typedef struct node{
int data;
struct node *next;
}node;
typedef struct stack{
node *head;
int size;
}stack;
stack *init_stack(){
stack *s = (stack *)malloc(sizeof(stack));
s->head = (node *)malloc(sizeof(node));
s->head->data = 0,s->head->next = NULL:
s->size = 0;
return s;
}
void delete_stack(stack *s){
node *p = s->head;
while(p != NULL){
node *q = p->next;
free(p);
p = q;
}
free(s);
}
//建立新结点，头插法入栈
int push(stack *s, int x){
node *p = (node *)malloc(sizeof(node));
p->data = x;
p->next = s->head->next;
s->head->next = p;
s->size++;
retuen 0;
}
//出栈，并释放元素
int pop(stack *s){
if(s->size == 0){
return 1;
}
node *p = s->head->next;
s->head->next = p->next;
free(p);
s->size--;
return 0;
}
//获取栈顶元素
int top(stack *s){
if(s->size == 0){
return -1;
}
return s->head->next->data;
}
void show_stack(stack *s){
printf("size -> %d\n",s->size);
for(node *p = s->head->next; p != NULL; p = p->next){
printf("%d->", p->data);
}
printf("N\n---------------------------\n");
}
int main(){
int n;
scanf("%d", &n);
stack *s = init_stack();
for(int i = 0; i < n; i++){
int t;
scanf("%d", &t);
if(t == 0){
int x;
scanf("%d", &x);
push(s, x);
}
else if(t == 1){
pop(s);
}
else{
printf("top - > %d\n", top(s));
}
show_stacks(s);
}
delete_stack(s);
rerurn 0;
}
运行结果：
2、队列——先进先出（FIFO）的数据结构
#define MaxCnt 50//队列中元素的最大个数
struct Queue{//队列定义
EleType data[MaxCnt];//队列的数据域
int front, back;//队首元素位置，队尾元素位置
};
typedef struct queue{
int *data;
int front, rear, cap, size;
}queue;
queue *init_queue(int x){
queue *q = (queue *)malloc(sizeof(queue));
q->data = (int *)malloc(sizeof(int) * x);
q->front = q->rear = q->size = 0;
q->cap = x;
return q;
}
void delete_queue(queue *q){
free(q->data);
free(q);
}
int push(queue *q, int x){
//((q->rear + 1)%q->cap == q->front)
if(q->size + 1 == q->cap){//队列已满，申请空间不能使用realloc，重新把数据存到新队列中
int *p = (int *)malloc(sizeof(int) * q->cap *2);
for(int i = 0, j = q->front; i != q->size; i++，j++, j %= q->cap){
p[i] = q->data[j];
}
free(q->data);
q->data = p;
q->cap *= 2;
q->front = 0;
q->rear = q->size;
}
q->data[q->rear] = x;
q->rear++;
q->rear %= q->cap;
q->size++;
return 0;
}
int pop(queue *q){
//q->front == q->rear
if(q->size == 0){
return 1;
}
q->front++;
q->front %= q->cap;
q->size--;
return 0;
}
int front(queue *q){
if(q->size == 0){
return -1;
}
return q->data[q->front];
}
void show_queue(queue *q){
printf("size = %d, cap = %d\n", q->size, q->cap);
for(int i = q->front;i != q->rear; i++){
printf("%d ", p->data[i]);
}
printf("\n-------------------------\n");
}
int main(){
int n,m;
scanf("%d%d",&n, &m);
queue *q = init_queue(m);
for(int i = 0; i < n; i++){
int t;
scanf("%d", &t);
if(t == 0){
int x;
scanf("%d", &x);
push(q, x);
}
else if(t == 1){
pop(q);
}
else{
printf("front -> %d\n", front(q));
}
show_queue(q);
}
delete_queue(q);
return 0;
}
运行结果：
总结：栈（FILO）和队列（FIFO）
顺序栈、链表栈
