栈与队列（c语言实现）

1.栈

栈的主要操作可以分为以下几种：

1.1基于数组实现栈

1.1.1定义栈的结构体

typedef int ElemType;  
typedef struct {  ElemType* data;  int length;  
}SqStack;

1.1.2栈的初始化

SqStack *InitStack() {  SqStack* stack = malloc(sizeof(SqStack));  stack->data = (ElemType*)malloc(sizeof(ElemType)*Max_Size);  stack->length = 0;  return stack;  
}

1.1.3栈的释放

//栈的释放  
void DestoryStack(SqStack* stack) {  free(stack->data);  free(stack);  
}

1.1.4元素入栈

void push(SqStack* stack,ElemType e) {  if(stack->length == Max_Size) {  printf("栈满！\n");  return;  }  stack->data[stack->length++] = e;  
}

stack->data[stack->length++] = e;：如果栈未满，将元素 e 存储在栈的当前位置（由 stack->length 指示），然后增加 stack->length 的值，表示栈中元素的数量增加了。

1.1.5元素出栈

 //元素出栈  
ElemType pop(SqStack* stack) {  if (stack->length == 0) {  printf("栈空！\n");  return -1;  }  return stack->data[stack->length--];  
}

1.1.6访问栈顶元素

//访问栈顶元素  
ElemType peek(SqStack* stack) {  if(stack->length == 0) {  printf("栈空！\n");  return -1;  }  return stack->data[stack->length-1];  
}

1.2基于链表实现栈

1.2.1链表的结构体定义

typedef int ElemType;  
//定义链表结构体  
typedef struct StackNode{  ElemType* data;  struct StackNode* next;  
}StackNode, *LinkStackPtr;  
//定义栈的结构体  
typedef struct {  StackNode* top;  int length;  
}LinkStack;

1.2.2初始化栈

//初始化栈  
LinkStack* InitStack() {  LinkStack* s = malloc(sizeof(LinkStack));  if (s == NULL) {  printf("内存分配失败！\n");  return NULL;  }  s->top = NULL;  s->length = 0;  return s;  
}

1.2.3销毁栈

//销毁栈  
void DestroyStack(LinkStack* s) {  //由栈顶到栈底，逐次释放  while (s->top) {  StackNode *n = s->top;  free(n);  s->top = s->top->next;  }  free(s);  
}

1.2.4元素出栈

//元素出栈  
ElemType pop(LinkStack* s) {  StackNode *node = malloc(sizeof(StackNode));  node->data = s->top->data;//将元素复制到node链表  StackNode *tmp = s->top;  s->top = s->top->next;//这里将top更新  free(tmp);  s->length--;return node->data;  
}

1.2.5访问栈顶元素

//访问栈顶元素  
ElemType peek(LinkStack* s) {  if(s->length == 0) {  printf("栈空");  return -1;  }  return s->top->data;  
}

2.队列

为了实现队列，我们需要一种数据结构，可以在一端添加元素，并在另一端删除元素，链表和数组都符合要求。

2.1基于数组的队列

2.1.1队列的结构体定义

//结构体定义  
typedef int ElemType;  
typedef struct {  ElemType* data;  ElemType front;     //队首指针  ElemType end;       //队尾指针  int length;     //队列长度  
}ArrayQueue;

2.1.2队列的初始化

//队列的初始化  
ArrayQueue *InitQueue(int queCapcity) {  ArrayQueue* queue = (ArrayQueue*)malloc(sizeof(ArrayQueue));  queue->length = queCapcity;  queue->front = queue->end = 0;  queue->data = (ElemType*)malloc(sizeof(ElemType)*queue->length);  return queue;  
}

2.1.3销毁队列

//销毁队列  
bool DestoryQueue(ArrayQueue* queue) {  free(queue->data);  free(queue);  return true;  
}

2.1.4入队

//入队  
void push(ArrayQueue* queue,ElemType e) {  if(queue->length == queue->end) {  printf("队满");  return;  }  int rear = (queue->front + queue->end) % queue->length;  queue->data[rear] = e;  queue->end++;  
}

2.1.5访问队首元素

//访问队首元素  
ElemType geek(ArrayQueue* queue) {  return queue->data[queue->front];  
}

2.1.6出队

//出队  
ElemType pop(ArrayQueue* queue) {  ElemType num = peek(queue);  queue->front = (queue->front + 1) % queue->length;  return num;  
}

2.2基于链表的队列

2.1.1队列结构体的定义

我们可以将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”，规定队尾仅可添加节点，队首仅可删除节点。

typedef int ElumType;  
typedef struct Linklist{  ElumType* data;  struct Linklist* next;  
}LNode;  
typedef struct {  LNode *front,*rear;  int quelength;  
}LinkListQueue;

2.1.2队列初始化

//队列的初始化  
LinkListQueue* InitLinkListQueue() {  LinkListQueue* queue = (LinkListQueue*)malloc(sizeof(LinkListQueue));  queue->front = NULL;  queue->rear = NULL;  queue->quelength = 0;  return queue;  
}

2.1.3队列的删除

//队列的删除  
void DestroyLinkListQueue(LinkListQueue *queue) {  while (queue->front != NULL) {  LNode* temp = queue->front;  queue->front = queue->front->next;  free(temp);  }  free(queue);  
}

2.1.4元素入队

//入队  
bool push(LinkListQueue* queue,ElumType e) {  LNode* node = (LNode*)malloc(sizeof(LNode));  node->data = e;  //队列为空，头尾指针都指向node  if(queue->quelength == 0) {  queue->front = node;  queue->rear = node;  queue->quelength++;  }  else {  queue->rear->next = node;  queue->rear = node;  queue->quelength++;  }  return true;  
}

2.1.5访问队首元素

//访问队首元素  
ElumType peek(LinkListQueue* queue) {  if(queue->quelength == 0) {  printf("队空！\n");  return -1;  }  return queue->front->data;  
}

2.1.6出队

//出队  
ElumType pop(LinkListQueue* queue) {  ElumType num = peek(queue);  LNode *tmp = queue->front;  queue->front = queue->front->next;  free(tmp);  queue->quelength--;  return num;  
}

以上是栈与队列的一些基本操作，原版代码上传至(https://gitee.com/shi-chengfu)

如果有错误请联系QQ:303613518