# 栈和队列

## 三、栈的顺序存储结构

``````typedef int ElemType;
typedef struct{
ElemType *base;
ElemType *top;
int stackSize;
}sqStack;
``````

``````typedef int ElemType;
type struct{
ElemType data[MAXSIZE];
int top;/用于标注栈顶的位置
int stackSize;
}
``````

### 创建一个栈

``````#define STACK_INIT_SIZE 100
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;
}
``````

### 入栈操作

``````#define SATCKINCREMENT 10

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++;
}
``````

### 出栈操作

``````Pop(sqStack *s,ElemType *e){
if(s->top == s->base){//栈已空
return;
}
*e = *--(s->top);
}
``````

### 清空一个栈

``````ClearStack(sqStack *s){
s->top = s->base;
}
``````

### 销毁一个栈

``````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(){
return (s.top - s.base);//初学者需要重点讲解
}
``````

### 实例分析

``````#include<stdio.h>
#include<stdlib.h>
#include<math.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 = (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 >= STACK_INIT_SIZE){
s->base = (ElemType *)realloc(s->base,(s->stackSize+STACKINCREMENT) *sizeof(ElemType));

if(s->base){
exit(0);
}
}
*(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(){
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();//把\n从缓冲区去掉

len = StackLen(s);

for(i=0;i<len;i++){
Pop(&s,&c);
sum = sum + (c-48) * pow(2,i);
}
printf("转化为十进制值:%d\n",sum);
return 0;
}
``````

## 四、栈的链式存储结构

``````typedef struct StackNode{
ElemType data;//存放栈的数据
struct StackNode *next;

int count;//栈元素计数器
}
``````

### 进栈操作

``````Status Push(LinkStack *s,ElemType e){

p->data = e;
p->next = s->top;
s->top = p;
s->count++;
return OK;
}
``````

### 出栈操作

``````Status Pop(LinkStack *s,ElemType *e){

if(StackEmpty(*s)){//判断是否为空栈
return ERROR;
}

*e = s->top->data;
p = s->top;
free(p);
s->count--;
return OK;
}
``````

## 五、队列

### 队列的链式存储结构

``````typedef struct QNode{
ElemType data;
struct QNode *next;
}QNode,*QueuePrt;

typedef struct{
QueuePrt front,rear;//队头、尾指针
``````

### 创建一个队列

``````initQueue(LinkQueue *q){
q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));

if(!q->front){
exit(0);
}
q->front->next = NULL;
}
``````

### 入队列操作

``````InsertQueue(LinkQueue *q,ElemType e){
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if(p == NULL){
exit(0);
}

p->data = e;
p->next = NULL;
q->rear->next = p;
q->rear = p;
}
``````

### 出对列操作

``````DeletedQueue(LinkQueue *q,ElemType *e){
QueuePtr 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);
}
``````

### 销毁一个队列

``````DestroyQueue(LinkQueue *q){
while(q->front){
q->rear = q->front->next;
free(q->front);
q->front = q->rear;
}
}
``````

## 六、队列的顺序存储结构

### 循环队列

``````#define MAXSIZE 100
typedef struct{
ElemType *base;//用于存放内存分配基地址
int front;
int rear;
}
``````

### 初始化一个循环队列

``````initQueue(cycleQueue *q){
q->base = (ElemType *)malloc(MAXSIZE*sizeof(ElemType));
if(!q->base){
exit(0);
}

q->front = q->rear = 0;
}
``````

### 循环队列入队

``````InsertQueue(cycleQueue *q,ElemType e){
if((q->rear+1)%MAXSIZE == q->front){
return;//队列已满
}
q->base[q->rear] = e;
q->rear = (q->rear+1) % MAXSIZE;
}
``````

### 循环队列出队列

``````DeletedQueue(cycleQueue *q,ElemType *e){
if(q->front == q->rear){
return;//队列为空
}

*e = q->base[q->front];
q->front = (1->front+1)%MAXSIZE;
}
``````

JSmiles

2512 文章
30 评论
82727 人气