数据结构与算法之:栈和队列(三)
栈
栈的定义
- 栈是一种后进先出(Last in first out,LIFO)的线性表,只能在表尾进行插入和删除操作
栈的插入和删除操作
-
站的插入操作(push),叫做进栈,也称为压栈,入栈
-
栈的删除操作(pop),叫做出栈,也叫做弹栈
栈的顺序存储结构
-
因为栈的本质是一个线性表,线性表有两种存储形式,那么栈也分为栈的顺序存储结构和栈的链式存储结构
-
最开始栈中不含有任何数据,叫做空栈,此时栈顶就是栈底.然后数据从栈顶进入,栈顶栈底分离,整个栈的当前容量变大.数据出栈时从栈顶弹出,栈顶下移,整个栈的当前容量变小
栈的顺序存储结构
typedef struct
{
ElemType *base;
ElemType *top;
int stackSize;
}sqStack;- 这里定义了一个顺序存储的栈,它包含了三个元素:base,top,stackSize.其中base是指向栈底的指针变量,top是指向栈顶的指针变量,stsck
- Size指示栈的当前可使用的最大容量
创建一个栈
#define STACK_INIT_SIZE 100
void initStack(sqStack *s)
{
s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!s->base)
exit(0);
s->top = s->base;
s->stackSize = STACK_INIT_SIZE;
}入栈操作
- 入栈操作要在栈顶进行,每次向栈中压入一个数据,top指针就要+1,指导栈满为止
#define STACKINCREMENT 10
void push(sqStack *s,ElemType e)
{
//如果栈满,追加空间
if(s->top - s->base >= s->stackSize)
{
s->base = (ElemType *)realloc(s->base,(s->stackSize + STACKINCREMENT) *
sizeof(ElemType));
if(!s->base)
exit(0);
s->top = s->base + s->stackSize;//设置栈顶
s->stackSize = s->stackSize + STACKINCREMENT;//设置栈的最大容量
}
*(s->top) = e;
s->top++;
}出栈操作
-
出栈操作就是在栈顶取出数据,栈顶指针随之下移的操作
-
每当从栈内弹出一个数据,栈的当前容量就-1
void pop(sqStack *s,ElemType *e)
{
//如果栈为空返回
if(s->top == s->base)
return;
*e = *--(s->top);
}- 清空一个栈
void ClearStack(sqStack *s)
{
s->top = s->base;
}- 销毁一个栈
void DestoryStack(sqStack *s)
{
int i,len;
len = s->stackSize;
for(i=0;i<len;i++)
{
free(s->base);
s->base++;
}
s->base = s->top = NULL;
s->stackSize = 0;
}- 当前容量
int StackLen(sqStack s)
{
return (s.top - s.base);
}二进制转10进制
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef char ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stackSize;
}sqStack;
void initStack(sqStack *s)
{
s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!s->base)
exit(0);
s->top = s->base;
s->stackSize = STACK_INIT_SIZE;
}
void push(sqStack *s,ElemType e)
{
//如果栈满,追加空间
if(s->top - s->base >= s->stackSize)
{
s->base = (ElemType *)realloc(s->base,(s->stackSize + STACKINCREMENT) *
sizeof(ElemType));
if(!s->base)
exit(0);
s->top = s->base + s->stackSize;//设置栈顶
s->stackSize = s->stackSize + STACKINCREMENT;//设置栈的最大容量
}
*(s->top) = e;
s->top++;
}
void pop(sqStack *s,ElemType *e)
{
//如果栈为空返回
if(s->top == s->base)
return;
*e = *--(s->top);
}
void ClearStack(sqStack *s)
{
s->top = s->base;
}
void DestoryStack(sqStack *s)
{
int i,len;
len = s->stackSize;
for(i=0;i<len;i++)
{
free(s->base);
s->base++;
}
s->base = s->top = NULL;
s->stackSize = 0;
}
int StackLen(sqStack s)
{
return (s.top - s.base);
}
int main()
{
ElemType c;
sqStack s;
int len,i,sum = 0;
initStack(&s);
printf("请输入二进制数,输入#号表示结束!\n");
scanf("%c",&c);
while(c!='#')
{
push(&s,c);
scanf("%c",&c);
}
//把回车从缓冲区去掉
getchar();
len = StackLen(s);
printf("栈的容量为:%d\n",len);
for(i=0;i<len;i++)
{
pop(&s,&c);
sum = sum + (c-48)*pow(2,i);
}
printf("%d\n",sum);
return 0;
}括号匹配
二进制转八进制
- 二进制与十六进制对应关系
0 0
1 1
10 2
11 3
100 4
101 5
110 6
111 7
1000 8
1001 9
1010 A
1011 B
1100 C
1101 D
1110 E
1111 F- 一个字节(8bit)刚好用两个十六进制数可以表示完整,大大街上了显示空间
- 先把每三位取出来,转换成8进制压入另一个栈,再从另外一个栈弹出
栈的链式储结构
typedef struct StackNode
{
ElemType data;
struct StackNode *next;
}StackNode,LinkStackPtr;
typedef struct LinkStack
{
//top指针
LinkStack top;
//栈元素计数器
int count;
}- 进栈操作
Status push(LinkStack *s,ElemType e)
{
LinkStackPtr p = (LinkStackPtr)malloc
(sizeof(StackNode));
p->data = e;
p->next = s->top;
s->top = p;
s->count++;
return OK;
}
- 出栈操作
Ststus pop(LinkStack *s,ElemType *e)
{
LinkStackPtr p;
if(StackEmpty(*s))
return ERROR;
*e = s->top->data;
p = s->top;
s->top = s->top->next;
free(p);
s->count--;
return OK;
}逆波兰表达式
-
20世纪三十年代,波兰逻辑学家Jan.Lukasiewicz发明了一种不需要括号的后缀表达式,我们通常把它称为逆波兰表达式(RPN)
-
对于(1-2)(4+5),如果用逆波兰表示发,应该是这样:1 2 - 4 5 +
-
数字1和2进栈,遇到减号运算符则弹出两个元素进行运算,并把结果入栈
-
4和5入栈,遇到加号运算符,4和5弹出栈,相加后结果9入栈
-
然后又遇到乘法运算符,将9和-1弹出栈进行乘法计算,此时栈空并无数据压栈,-9为最终结果
逆波兰表达式计算器
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAXBUFFER 10
typedef double ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stackSize;
}sqStack;
void initStack(sqStack *s)
{
s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!s->base)
exit(0);
s->top = s->base;
s->stackSize = STACK_INIT_SIZE;
}
void push(sqStack *s,ElemType e)
{
//如果栈满,追加空间
if(s->top - s->base >= s->stackSize)
{
s->base = (ElemType *)realloc(s->base,(s->stackSize + STACKINCREMENT)
* sizeof(ElemType));
if(!s->base)
exit(0);
s->top = s->base + s->stackSize;//设置栈顶
s->stackSize = s->stackSize + STACKINCREMENT;//设置栈的最大容量
}
*(s->top) = e;
s->top++;
}
void pop(sqStack *s,ElemType *e)
{
//如果栈为空返回
if(s->top == s->base)
return;
*e = *--(s->top);
}
int main()
{
sqStack s;
char c;
double d,e;
int i = 0;
char str[MAXBUFFER];
initStack(&s);
printf("请按逆波兰表达式输入待计算数据,数据与运算符之间用空格隔开,以#作为结束标志!\n");
scanf("%c",&c);
while(c!='#')
{
while(isdigit(c)||c=='.')
{
str[i++] = c;
str[i] = '\n';
if(i>=10)
{
printf("出错:输入的单个数据过大!\n");
return -1;
}
//过滤空格
scanf("%c",&c);
if(c==' ')
{
d = atof(str);
push(&s,d);
i = 0;
break;
}
}
switch(c)
{
case '+':
pop(&s,&e);
pop(&s,&d);
push(&s,d+e);
break;
case '-':
//下面减上面
pop(&s,&e);
pop(&s,&d);
push(&s,d-e);
break;
case '*':
pop(&s,&e);
pop(&s,&d);
push(&s,d*e);
break;
case '/':
pop(&s,&e);
pop(&s,&d);
if(e!=0)
{
push(&s,d/e);
}
else
{
printf("\n出错:除0!\n");
}
break;
}
scanf("%c",&c);
}
pop(&s,&d);
printf("最终的计算结果为:%lf",d);
return 0;
}中缀表达式转换为后缀表达式
- 从左到右遍历中缀表达式的每个数字和符号,若是数字则直接输出,若是符号,则判断其与栈顶符号的优先级,是右括号或者优先级低于栈顶符号,则栈顶元素一次出栈并输出,直到遇到左括号或栈空才将那个符号入栈
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAXBUFFER 10
typedef char ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stackSize;
}sqStack;
void initStack(sqStack *s)
{
s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!s->base)
exit(0);
s->top = s->base;
s->stackSize = STACK_INIT_SIZE;
}
void push(sqStack *s,ElemType e)
{
//如果栈满,追加空间
if(s->top - s->base >= s->stackSize)
{
s->base = (ElemType *)realloc(s->base,(s->stackSize + STACKINCREMENT) * sizeof(ElemType));
if(!s->base)
exit(0);
s->top = s->base + s->stackSize;//设置栈顶
s->stackSize = s->stackSize + STACKINCREMENT;//设置栈的最大容量
}
*(s->top) = e;
s->top++;
}
void pop(sqStack *s,ElemType *e)
{
//如果栈为空返回
if(s->top == s->base)
return;
*e = *--(s->top);
}
int StackLen(sqStack s)
{
return (s.top - s.base);
}
int main()
{
sqStack s;
char c,e;
initStack(&s);
printf("请输入中缀表达式,以#作为结束标志:\n");
scanf("%c",&c);
while(c!='#')
{
while(c>='0'&&c<='9')
{
printf("%c",c);
scanf("%c",&c);
if(c<'0'||c>'9')
{
printf(" ");
}
}
if(')' == c)
{
pop(&s,&e);
while('('!=e)
{
printf("%c ",e);
pop(&s,&e);
}
}
else if('+'==c || '-'==c)
{
if(!StackLen(s))
{
push(&s,c);
}
else
{
do
{
pop(&s,&e);
if('('==e)
{
push(&s,e);
}
else
{
printf("%c ",e);
}
}while(StackLen(s)&&'('!=e);
push(&s,c);
}
}
else if('*'==c||'/'==c||'('==c)
{
push(&s,c);
}
else if('#'==c)
{
break;
}
else
{
printf("\n输入错误!\n");
return -1;
}
scanf("%c",&c);
}
while(StackLen(s))
{
pop(&s,&e);
printf("%c ",e);
}
return 0;
}队列
什么是队列
-
队列(queue)是只允许在一段进行插入操作,而在另一端进行删除操作的线性表
-
与栈相反,队列是一种先进先出(First In First Out,FIFO)的线性表
-
与栈相同的是,队列也是一种重要的线性结构,实现一个队列同样需要顺序表或链表作为基础
-
队列既可以用链表实现,也可以用顺序表实现.跟栈相反的是,栈一般用顺序表来实现,二队列常4用链表来实现,简称为链队列
队列的链式存储结构
typedef struct QNode
{
ElemType data;
struct QNode *next;
}QNode,*queuePrt;
typedef struct
{
//队头,尾指针
queuePrt front,rear;
}LinkQueue;- 我们将头指针指向队列的头结点,而队尾指针指向终端节点.(注:头结点不是必须的,但为了方便操作,我们加上了)
- 空队列时,front和rear都指向头结点
创建一个队列
void initQueue(LinkQueue *q)
{
q->front = q->rear = (queuePrt)malloc(sizeof(QNode));
if(!q->front)
exit(0);
q->front->next=NULL;
}入队列操作
void InsertQueue(LinkQueue *q,ElemType)
{
p = (queuePrt)malloc(sizeof(QNode));
if(p==NULL)
exit(0);
p->data = e;
p->next = NULL;
q->rear->next = p;
q->rear = p;
}出队列操作
- 出队列操作是将队列中的第一个元素移除,队头指针不发生改变,改变头结点的next指针即可
void DeleteQueue(LinkQueue *q,ElemType *e)
{
queuePrt p;
if(q->front == q->rear)
return;
p = q->front->next;
*e = p->data;
q->front->next = p->next;
if(q->rear==p)
q->rear = q->front;
free(p);
}销毁一个队列
- 由于连队列建立在内存的动态区,因此当一个队列不在有用时应当把它及时销毁掉,以免过多的占用空间
void DestoryQueue(LinkQueue *q)
{
while(q->front)
{
q->rear = q->front->next;
free(q->front);
q->front = q->rear;
}
}队列的顺序存储结构
- 队列顺序存储会出现对头有空余而队尾溢出的情况,这种情况叫做假溢出.
循环队列的定义
-
要解决假溢出的办法就是如果后面满了,就再从头开始,也就是头尾相接的循环
-
循环队列它的容量是固定的,并且它的队头和队尾指针都可以随着元素出入队列而发生改变,这样循环队列逻辑上就好像是一个环形的存储空间
-
循环队列的实现只需要灵活改变front和rear指针即可
-
也就是让front或rear指针不断加1,即使超出了地址范围,也会自动从头开始,我们可以采取取模运算处理
-
(rear+1) % QueueSize
-
(front+1) % QueueSize
-
-
定义一个循环队列
#define MAXSIZE 100
typedef struct
{
ElemType *base;
int front;
int rear;
}- 初始化一个循环队列
void initQueue(cycleQueue *q)
{
q->base = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
if(!q->base)
exit(0);
q->front = q->rear = 0;
}- 如队列操作
void InsertQueue(cycleQueue *q,ElemType e)
{
if((q->rear+1)%MAXSIZE == q->front)
return;
q->base[q->rear] = e;
q->rear = (q->rear+1)%MAXSIZE;
}出队列操作
void DeleteQueue(cycleQueue *q,ElemType *e)
{
if(q->front == q->rear)
return;
*e = q->base[q->front];
q->front = (q->front+1)%MAXSIZE;
}