摘要:栈和队列的基本概念、顺序栈/队列、链栈/队列的构成方法。
基本概念
栈的基本概念
-
定义
栈是一种只能在一端进行插入和删除操作的线性表。其中允许进行插入或者删除操作的一端称为栈顶(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 条评论