栈
栈的特点是先进后出，一张图简单介绍一下。
#include "stdio.h"
#include "math.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
typedef char ElemType;
typedef struct{
ElemType *base;
ElemType *top;
int stacksize;
}sqStack;
void initStack(sqStack *s)
{
/*内存中开辟一段连续空间作为栈空间，首地址赋值给s->base*/
s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!s->base) exit(0); /*分配空间失败*/
s->top = s->base; /*最开始，栈顶就是栈底*/
s->stacksize = STACK_INIT_SIZE; /*最大容量为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) ;//计算栈的长度
}
void main()
{
ElemType c;
sqStack s;
int len , i , sum = 0;
printf("Please input a Binary digit\n");
initStack(&s); /*创建一个栈，用来存放二进制字符串*/
/*输入0/1字符表示的二进制数，以#结束*/
scanf("%c",&c);
while(c!='#')//遇到#则结束
{
Push(&s,c);//输入一个压入一个
scanf("%c",&c);
}
len = StackLen(s); /*得到栈中的元素个数，即二进制数的长度*/
for(i=0;i<len;i++){
Pop(&s,&c);
sum = (int)(sum + (c-48) * pow(2,i)); /*转换为十进制*/
//二进制转十进制的算法
}
printf("Decimal is %d\n",sum);
}
队列
队列的特点是先进先出，就跟我们平常排队一个意思。
#include "stdio.h"
#include "stdlib.h"
typedef char ElemType;
typedef struct QNode{
ElemType data;
struct QNode *next;
} QNode , *QueuePtr;
typedef struct{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
void initQueue(LinkQueue *q){
/*初始化一个空队列*/
q->front = q->rear = (QueuePtr)malloc(sizeof(QNode)); /*创建一个头结点，队头队尾指针 指向该结点*/
if( !q->front) exit(0); /*创建头结点失败*/
q->front->next = NULL; /*头结点指针域置NULL*/
}
void EnQueue(LinkQueue *q, ElemType e){
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode)); /*创建一个队列元素结点*/
if( !q->front) exit(0); /*创建头结点失败*/
p->data = e;//元素节点写入数据
p->next = NULL;//元素节点的向后的指针指向空
q->rear ->next = p;//将队列中的队尾指针指向刚生成的元素节点
q->rear = p;
}
void DeQueue(LinkQueue *q, ElemType *e){
/*如果队列q不为空，删除q的队头元素，用e返回其值*/
QueuePtr p;
if(q->front == q->rear) return; /*队列为空，返回*/
p = q->front->next;//队头给p
*e = p->data;//取出来的队头的数据
q->front->next = p->next;//取出来的队头的下一个指向给新的队头的指向
if(q->rear == p) q->rear = q->front; /*如果队头就是队尾，则修改队尾指针*/
free(p);
}
/*测试函数*/
void main()
{
ElemType e;
LinkQueue q;
initQueue(&q); /*初始化一个队列q*/
printf("Please input a string into a queue\n");
scanf("%c",&e);
while(e!='@'){
EnQueue(&q,e); /*向队列中输入字符串，以@表示结束*/
scanf("%c",&e);
}
printf("The string into the queue is\n");
while(q.front != q.rear){ /*将队列中的元素出队列，并打印在屏幕上*/
DeQueue(&q,&e);
printf("%c",e);
}
printf("\n");
}