摘要：栈和队列的基本概念、顺序栈/队列、链栈/队列的构成方法。
基本概念
栈的基本概念
-
定义
栈是一种只能在一端进行插入和删除操作的线性表。其中允许进行插入或者删除操作的一端称为栈顶（top）。栈顶由一个称为栈顶指针的位置指示器（其中就是一个变量，对于顺序栈，就是进行记录栈顶元素所在数组位置标号的一个整型变量。对于链式栈，就是记录栈顶元素所在的结点地址的指针）来指示的，它是动态变化的。表的另一端称为栈底，栈底固定不变。栈的插入和删除操作一般称为入栈和出栈。
-
栈的特点
由栈的定义，栈的特点是FILO。栈中的元素就好比开进死胡同的车队。
-
栈的存储结构
可以用顺序表和链表来存储栈，栈可以依照存储结构分为两种：顺序栈和链式栈。在栈的定义中已经说明，栈是一种在操作上稍加限制的线性表，即栈本质上是一个线性表，而线性表由两种主要的存储结构——顺序表和链表，因此栈也同样有对应的两种存储结构。
-
栈的数学性质
当n个元素以某种顺序进栈，并且可以在任意时刻出栈时，所获得的元素排列的数目N恰好满足Catalan（）的计算：
N = 1/（n+1）* C （上标n下标2n）组合
队列的基本概念
-
队列的定义
队列简称队，它也是一种操作受限的线性表，其限制为仅允许在表的一段进行插入，在表的另一端进行删除。可进行插入的一端称为队尾（rear），可进行删除的一端策划归称为队头（front）。向队列中插入新的元素称为进队，新元素进队后就称为了新的队尾元素，从队列中删除元素称为出队，元素出队后，其后继元素就成为新的队头元素。
-
队列的特点
队列的特点概况起来就是FIFO。
-
队列的存储结构
可用顺序表和链表来存储队列，队列按存储结构可分为顺序队和链队两种。
栈和队列的存储结构、算法和应用
顺序栈
-
顺序栈的要素
对于顺序栈st，一共有四个要素，包括两个特殊状态和两个操作。
1） 栈空状态
st.top== -1，这里暂时这么定义，这样不会浪费一个元素大小的空间。
2）栈满状态
st.top == max_size -1。max_size为栈中最大元素个数，则max_size-1为栈满时栈顶元素在数组中的位置，因为数组下标从0开始，所以定义top为-1时栈空，即top==0的数组位置也可以存放数据元素。
3）非法状态（上溢和下溢）
栈满的时候继续入栈就会上溢，栈空的时候出栈就会下溢。
4）元素x进栈的操作： ++（st.top); st.data[st.top] =x; 。既然规定了top为-1时栈空，则元素进栈操作必须是先移动指针，再进入元素，因为不存在下标为-1的数组。
5）元素x出栈的操作： x = st.data[st.top]; - - (st.top); 。进栈操作次序决定了出栈操作次序，由于进栈操作是先变动栈顶指针，再存入元素，因此出栈的操作必须为先取出元素再变动指针。如果上述进栈操作不变的情况下先动指针，再取出元素，则栈顶元素则会丢失，取出的是栈顶下边的元素。
顺序栈定义：
typedef struct { int data[max_size]; int top; }sq_stack;初始化：
//初始化栈 void initStack(sq_stack *st) { st->top=-1; }判定栈是否为空：
//判断栈是否为空 void isEmpty(sq_stack *st) { if(st->top == -1) printf("栈为空栈！\n"); else printf("栈不为空！\n"); }进栈以及出栈操作：
//进栈操作 int push(sq_stack *st,int x) { if(st->top == max_size-1) { printf("栈已经满了！\n"); return 0; } ++(st->top); st->data[st->top]=x; return 1; } //出栈操作 int pop(sq_stack *st, int *x) { if(st->top == -1) { printf("栈已经空了！\n"); return 0; } *x = st->data[st->top]; --(st->top); return 1; }全部代码：
#include <stdio.h> #include <stdlib.h> #define max_size 128 //顺序栈的定义 typedef struct { int data[max_size]; int top; }sq_stack; //以下为顺序栈的操作 //初始化栈 void initStack(sq_stack *st) { st->top=-1; } //判断栈是否为空 void isEmpty(sq_stack *st) { if(st->top == -1) printf("栈为空栈！\n"); else printf("栈不为空！\n"); } //进栈操作 int push(sq_stack *st,int x) { if(st->top == max_size-1) { printf("栈已经满了！\n"); return 0; } ++(st->top); st->data[st->top]=x; return 1; } //出栈操作 int pop(sq_stack *st, int *x) { if(st->top == -1) { printf("栈已经空了！\n"); return 0; } *x = st->data[st->top]; --(st->top); return 1; } int main() { sq_stack *st; int x = 1; int y = 0; st = (sq_stack*)malloc(sizeof(sq_stack)); initStack(st); printf("初始化后栈顶指针为：%d\n",st->top); isEmpty(st); push(st,x); isEmpty(st); pop(st,&y); printf("y的值为：%d\n",y); return 0; } -
简化操作
其中值得说的是，顺序栈其实可以很简单的定义以及进出栈：
定义一个栈并初始化
int stack[max_size];
int top = -1;
元素进栈
stack[++top] = x;
元素出栈
stack[top--] = x;
其中元素进出栈要根据具体情况按需判断栈的空或满；
tips:
在自增操作中 a;总是比a;来得执行效率更加高效，因此独立的自增操作总是用++a;。自减也是同样的道理。
链栈
-
链栈的要素
和顺序栈对应，链栈也有4个要素，包括两个特殊状态和两个操作。
（1）两个状态
栈空状态：
lst->next == NULL;
栈满状态：
不存在栈满状态（假设内存无限大）
（2）两个操作
元素（由指针p所指）进栈操作
p->next = lst->next;
lst->next = p;
其实就是头插法建立链表的插入操作。
出栈操作（出栈元素保存在x中）
p = lst->next;
x = p->data;
lst->next = p->next;
free(p);
其实就是单链表的删除操作。
-
基本操作
链栈结点定义：
//链栈结点的定义 typedef struct LNode { int data; struct LNode *next; }LNode;初始化链栈：
//初始化链栈 LNode *initStack(LNode *lst) { lst = (LNode*)malloc(sizeof(LNode));//制造一个头结点 lst->next = NULL; return lst; }判断栈空：
//判断栈空 void isEmpty(LNode *lst) { if(lst->next == NULL) printf("栈为空栈！\n"); else printf("栈不为空！\n"); }进出栈：
//进栈 void push(LNode *lst,int x) { LNode *p = (LNode*)malloc(sizeof(LNode)); p->next = NULL; p->data = x; p->next = lst->next; lst->next = p; } //出栈 void pop(LNode * lst,int *x) { LNode *p; if(lst->next == NULL) printf("栈为空栈！\n"); else { p = lst->next; *x = p->data; lst->next = p->next; free(p); } }完整代码：
#include <stdio.h> #include <stdlib.h> //链栈结点的定义 typedef struct LNode { int data; struct LNode *next; }LNode; //初始化链栈 LNode *initStack(LNode *lst) { lst = (LNode*)malloc(sizeof(LNode));//制造一个头结点 lst->next = NULL; return lst; } //判断栈空 void isEmpty(LNode *lst) { if(lst->next == NULL) printf("栈为空栈！\n"); else printf("栈不为空！\n"); } //进栈 void push(LNode *lst,int x) { LNode *p = (LNode*)malloc(sizeof(LNode)); p->next = NULL; p->data = x; p->next = lst->next; lst->next = p; } //出栈 void pop(LNode * lst,int *x) { LNode *p; if(lst->next == NULL) printf("栈为空栈！\n"); else { p = lst->next; *x = p->data; lst->next = p->next; free(p); } } int main() { LNode *lst; int x = 1; int y = 0; lst = initStack(lst); isEmpty(lst); push(lst,x); isEmpty(lst); pop(lst,&y); printf("y的值为：%d\n",y); isEmpty(lst); return 0; }
顺序队
-
循环队列
front代表头指针； rear代表尾指针；
要实现指针在递增的过程中沿着环形道路行走，就拿front举例子，可以循环执行语句front= （front+1)%max_size (max_size指的是数组长度)。
-
两个状态
队空状态
qu.rear == qu.front
队满状态
(qu.rear+1)%max_size == qu.front
-
两个操作
元素x进队操作（移动队尾指针）
qu.rear = (qu.rear + 1)%max_size;
qu.data[qu.rear] = x;
元素x出队操作（移动队首指针）
qu.front = (qu.front + 1)%max_size;
x = qu.data[qu.front];
tips:
元素入队先移动指针，后存入元素，对应元素出队时，先移动指针，再取出元素。可能有的方式不同，但是归根究底本质是一样的。
-
顺序队的定义
typedef struct { int data[max_size]; int front; int rear; }sq_queue; -
初始化队列以及判断队列是否为空
void init_sq_queue(sq_queue *qu) { qu->front = qu->rear = 0; } //判断队空 int isEmpty(sq_queue *qu) { if(qu->front == qu->rear) return 1; else return 0; } -
进队以及出队
int in_queue(sq_queue *qu,int x) { if((qu->rear+1)%max_size == qu->front)//判断队列是否为满 { printf("队列已满！\n"); return 0; } qu->rear = (qu->rear + 1)%max_size; qu->data[qu.rear] = x; return 1; } //出队 int out_queue(sq_queue *qu,int *x) { if(qu->rear == qu->front)//判断队列是否为空 { printf("队列为空！\n"); return 0; } qu->front = (qu->front + 1)%max_size; *x = qu->data[qu.front]; return 1; } -
全部代码
#include <stdio.h> #include <stdlib.h> #define max_size 128 //顺序队定义 typedef struct { int data[max_size]; int front; int rear; }sq_queue; //初始化 void init_sq_queue(sq_queue *qu) { qu->front = qu->rear = 0; } //判断队空 void isEmpty(sq_queue *qu) { if(qu->front == qu->rear) printf("队列为空！\n"); else printf("队列不为空！\n"); } //进队 int in_queue(sq_queue *qu,int x) { if((qu->rear+1)%max_size == qu->front)//判断队列是否为满 { printf("队列已满！\n"); return 0; } qu->rear = (qu->rear + 1)%max_size; qu->data[qu->rear] = x; return 1; } //出队 int out_queue(sq_queue *qu,int *x) { if(qu->rear == qu->front)//判断队列是否为空 { printf("队列为空！\n"); return 0; } qu->front = (qu->front + 1)%max_size; *x = qu->data[qu->front]; return 1; } int main() { sq_queue *qu; int x,y; qu = (sq_queue*)malloc(sizeof(sq_queue)); isEmpty(qu); x = 5; in_queue(qu,x); isEmpty(qu); out_queue(qu,&y); printf("出队的元素y = %d\n",y); return 0; } //链队定义 typedef struct QNode { int data; struct QNode *next; }QNode;
Comments | 0 条评论