回顧：

????線性表——順序表（數(shù)組）、鏈表（結(jié)點(diǎn)）

鏈表插入方法：頭插法、尾插法

雙向鏈表：*next *front

1、棧——stack?先進(jìn)后出（FILO）的數(shù)據(jù)結(jié)構(gòu)，棧不為空時(shí)，只能看到棧頂元素。

結(jié)構(gòu)定義

#define MaxCnt 50//棧當(dāng)中元素的最大個(gè)數(shù)

struct Stack{//棧的定義

????EleType data[MaxCnt];//棧的數(shù)據(jù)域

????int top;//棧頂元素位置

};

鏈棧是使用類似于鏈表的結(jié)構(gòu)實(shí)現(xiàn)。

共享?xiàng)＃址Q對(duì)頂棧，兩個(gè)棧共享同一內(nèi)存空間。

使用順序表實(shí)現(xiàn)順序棧

#include <stdlib.h>

typedef struct stack{

????int *data;

????int size,cap; //元素?cái)?shù)量，容量

}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);//操作次數(shù)，容量

????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;

}

運(yùn)行結(jié)果：

鏈棧

頭插法（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);

}

//建立新結(jié)點(diǎn)，頭插法入棧

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;

}

運(yùn)行結(jié)果：

?

2、隊(duì)列——先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)

#define MaxCnt 50//隊(duì)列中元素的最大個(gè)數(shù)

struct Queue{//隊(duì)列定義

????EleType data[MaxCnt];//隊(duì)列的數(shù)據(jù)域

????int front, back;//隊(duì)首元素位置，隊(duì)尾元素位置

};

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){//隊(duì)列已滿，申請(qǐng)空間不能使用realloc，重新把數(shù)據(jù)存到新隊(duì)列中

????????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;

}

運(yùn)行結(jié)果：

總結(jié)：棧（FILO）和隊(duì)列（FIFO）

順序棧、鏈表?xiàng)?/p>