TableOfContents
栈Stack
1. 逻辑结构
实例
图示
2. 操作
- init(st) 初始化
- is_empty(st)判断栈是否为空
- get_top(st) 取得栈顶结点值
- push(st, x) 栈的插入操作
- pop(st) 栈的删除操作
3. 顺序实现(顺序栈)
- 栈的顺序存储方式实现又称作顺序栈 栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制它们在顺序表的同一端进行,所以同顺序表一样也可用一维数组表示。
3.1. 存储结构定义
用数组定义的顺序栈
1 #define MAXSIZE 100
2 typedef int elem_type;
3 struct seq_stack{
4 elem_type elem[MAXSIZE];
5 int size;
6 };
7 typedef struct seq_stack seq_stack;
3.2. 算法实现
顺序栈初始化
1 void init ( seq_stack * st )
2 {
3 st->size=0;
4 }
判断栈是否为空
1 int is_empty(seq_stack *st)
2 {
3 return st->size==0;
4 }
获取顺序栈栈顶元素
1 elem_type get_top(seq_stack *st)
2 {
3 return st->elem[st->size-1];
4 }
入栈
1 void push(seq_stack *st, elem_type x)
2 {
3 if(st->size < MAXSIZE) {
4 st->elem[st->size]=x;
5 st->size++;
6 }
7 }
出栈
1 elem_type pop(seq_stack *st)
2 {
3 return st->elem[--st->size];
4 }
打印栈
1 void print_stack (seq_stack *st)
2 {
3 int i;
4 for(i = 0; i < st->size; i++)
5 printf("%5d", st->elem[i]);
6 }
判断顺序栈是否已满
1 int is_full(seq_stack *st) {
2 return st->size == MAXSIZE;
3 }
4. 链式实现
- 栈的链式存储称为链式栈。链式栈就是一个特殊的单链表,对于这特殊的单链表,它的插入和删除只在单链表的头部进行。 这里采用带头结点的单链表实现。
4.1. 存储结构结构定义
数据结构定义同带头结点的单链表。
1 typedef int elem_type;
2 struct node {
3 elem_type data;
4 struct node *next;
5 };
6 typedef struct node node;
7 typedef struct node *link_list
4.2. 算法实现
初始化
取栈顶元素
1 ElemType get_top(node *head) {
2 return head->next->data;
3 }
入栈
1 void push(node *head, ElemType x){
2 Node*p=(Node*)malloc(sizeof(Node));
3 p->data=x;
4 p->next=head->next;
5 head->next = p;
6 }
出栈
1 ElemType pop(node *head) {
2 Node *p = head->next;
3 ElemType x = p->data;
4 head->next = p->next;
5 free(p);
6 return x;
7 }
5. 应用
5.1. 括号匹配
5.1.1. 问题描述
设一个表达式中可以包含三种括号:小括号、中括号和大括号,各种括号之间允许任意嵌套,如小括号内可以嵌套中括号、大括号,但是不能交叉。举例如下:
([]{}) 正确的
([()]) 正确的
{([])} 正确的
{[(])} 不正确的
{(}[]) 不正确的
5.1.2. 算法思路
- 自左向右扫描一个表达式,当遇到的左括号,都期待后面有一个和它对应的右括号与之匹配。我们将所遇到的开括号存放入一个栈中,等待匹配。
- 当遇到一个右括号时,就查看这个栈的栈顶结点,如果它们匹配,则删除栈顶结点,如果不匹配,则说明表达式中括号是不匹配的。
- 如果扫描它整个表达式后,这个栈是空的,则说明表达式中的括号是匹配的,否则表达式的括号是不匹配的。
5.1.3. 算法实现
1 int match_kuohao (char *s) {
2 int i;
3 seq_stack st;
4 init_stack(&st);
5 for(i = 0; s[i]!='\0'; i++) {
6 switch (s[i]) {
7 case '{': case '[': case '(':
8 push(&st, s[i]); break;
9 case '}':
10 if(!is_empty(&st)&&get_top(&st)=='{')
11 { pop(&st);break; } else return 0;
12 case ']':
13 if(!is_empty(&st)&&get_top(&st)=='[')
14 { pop(&st);break; } else return 0;
15 case ')':
16 if(!is_empty(&st)&&get_top(&st)=='(')
17 { pop(&st);break; } else return 0;
18 }
19 }
20 return is_empty(&st);
21 }
5.2. 算术表达式求值
对简单的中缀表达式进行求值
从左到右扫描表达式,进行如下处理: 1. 遇到运算数进operand栈 1. 遇到运算符,与operator栈顶运算符比较优先级
- 如果比栈顶运算优先级高,则入栈。
- 否则operator出栈,operand出栈,进行运算,结果入栈。重做2
5.3. 递归算法改非递归算法
队列Queue
1. 逻辑结构
只允许在一端插入元素,在另一端删除元素的线性表。
队列具有先进先出的特性
插入的一端称作队尾,删除的一端称为队头。
2. 操作
- init_queue 初始化
- is_empty 判断空
- is_full 判断满
- enter_queue 入队列
- delete_queue 出队列
- get_head 取队列头部元素
3. 顺序实现(循环队列)
3.1. 存储结构
1 #define MAXSIZE 100
2 typedef int elem_type;
3 struct seq_queue{
4 elem_type elem[MAXSIZE];
5 int front;
6 int rear;
7 };
8 typedef struct seq_queue seq_queue;
3.2. 操作实现
初始化
1 void init(seq_queue *q)
2 {
3 q->rear = 0;
4 q->front = 0;
5 }
入队操作
1 void push(seq_queue *q, elem_type e)
2 {
3 q->elem[q->rear] = e;
4 q->rear = (q->rear+1) % MAXSIZE;
5 }
出队操作
1 elem_type pop(seq_queue *q)
2 {
3 int pos = q->front;
4 q->front = (q->front + 1) % MAXSIZE;
5 return q->elem[pos];
6 }
取队首
1 elem_type get_head() {
2 return q->elem[q->front];
3 }
判断是否为空
1 bool is_empty(seq_queue *q)
2 {
3 return q->rear == q->front;
4 }
判断是否满
1 bool is_full(seq_queue *q)
2 {
3 return (q->rear+1)%MAXSIZE == q->front;
4 }
4. 链式实现(单循环链表实现)
4.1. 存储结构定义
数据结构定义同带头结点的循环单链表。
1 typedef int elem_type;
2 struct node {
3 elem_type data;
4 struct node *next;
5 };
6 typedef struct node node;
7 typedef struct node *link_list
8 struct link_queue {
9 node *front;
10 node *rear;
11 };
12 typedef struct link_queue link_queue;
4.2. 操作实现
初始化
1 void init(link_queue *q){
2 q->front = (node*)malloc(sizeof(node));
3 q->front->next = NULL;
4 q->rear = q->front;
5 }
入队
1 void push(link_queue *q, elem_type e){
2 node *p = (node *)malloc(sizeof(node));
3 p->data = e;
4 p->next = NULL;
5 q->rear->next = p;
6 q->rear = p;
7 }
出队
1 elem_type pop(link_queue *q){
2 node *p = q->front->next;
3 elem_type e = p->data;
4 q->front->next = p->next;
5 if( q->rear == p)
6 q->rear = q->front;
7 free(p);
8 return e;
9 }
判断空
1 int is_empty(link_queue *q) {
2 return q->front == q->rear;
3 }
取队首
1 elem_type get_top(link_queue *q) {
2 return q->front->next->data;
3 }