基本数据结构之栈和队列
前言：最近看各大公司的面试笔试题，发现对栈和队列的考察还是挺多，而且这两个都是经典的数据结构，我想虽然简单，但是基础非常重要，还是有必要总结总结；
1 栈的概念
栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。
栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。
栈底(Bottom)：是固定端，又称为表头。
空栈：当表中没有元素时称为空栈。
2 栈的实现：
栈有两种实现，一种是顺序储存，一种是链式储存;
实现代码：
Stack.h
#define MAX_STACK_SIZE 100 /* 栈向量大小 */typedef int ElemType ;//栈的顺序储存/*typedef struct sqstack{ ElemType stack_array[MAX_STACK_SIZE] ;int top;int bottom;}SqStack ;SqStack Init_Stack();void push(SqStack &S , ElemType e);void pop( SqStack &S, ElemType &e );*///栈的链式表示typedef struct Stack_Node{ ElemType data ;struct Stack_Node *next ;} Stack_Node ;Stack_Node *Init_Link_Stack(void);void push(Stack_Node *top , ElemType e);void pop(Stack_Node *top , ElemType *e);Stack.c
#include "Stack.h"#include <stdlib.h>/*SqStack Init_Stack(void){ SqStack S ;S.bottom=S.top=0 ; return(S) ;}void push(SqStack &S , ElemType e){ if (S.top==MAX_STACK_SIZE-1) return ; S.stack_array[++S.top]=e ; }void pop( SqStack &S, ElemType &e ){ if ( S.top==0 )return ; e=S.stack_array[S.top--] ; }*///链表实现Stack_Node *Init_Link_Stack(void){ Stack_Node *top ;top=(Stack_Node *)malloc(sizeof(Stack_Node )) ;top->next=NULL ; return(top) ;}void push(Stack_Node *top , ElemType e){ Stack_Node *p ;p=(Stack_Node *)malloc(sizeof(Stack_Node)) ; if (!p) return;p->data=e ; p->next=top->next ; top->next=p ; /* 钩链 */}void pop(Stack_Node *top , ElemType *e)/* 将栈顶元素出栈 */{ Stack_Node *p ;if (top->next==NULL )return ;p=top->next ; *e=p->data ; /* 取栈顶元素 */top->next=p->next ; /* 修改栈顶指针 */free(p) ; }main:
#include <stdio.h>#include "Stack.h"void main(){int e= 0;Stack_Node *s=Init_Link_Stack();push(s,1);push(s,2);pop(s,&e);printf("%d\n",e);}
2 队列的基本概念
队列(Queue)：也是运算受限的线性表。是一种先进先出(First In First Out ，简称FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行删除。
队首(front) ：允许进行删除的一端称为队首。
队尾(rear) ：允许进行插入的一端称为队尾。
例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。
实现：queue.h
#define MAX_QUEUE_SIZE 100typedef int ElemType;//队列的顺序储存/*typedef struct queue{ ElemType Queue_array[MAX_QUEUE_SIZE] ;int front ;int rear ;}SqQueue;SqQueue Init_Queue(void);void enQueue(SqQueue &Q , ElemType e);void deQueue(SqQueue &Q, ElemType *x );*///队列的链式储存typedef struct Qnode{ ElemType data ;struct Qnode *next ;}QNode ;typedef struct link_queue{ QNode *front , *rear ;}LinkQueue ;LinkQueue *Init_LinkQueue(void);void enLinkQueue(LinkQueue *Q , ElemType e);void deLinkQueue(LinkQueue *Q, ElemType *x);queue.c
#include "queue.h"#include <stdlib.h>/*SqQueue Init_Queue(void){ SqQueue Q ;Q.front=Q.rear=0; return(Q) ;}void enQueue(SqQueue &Q , ElemType e){ if(Q.rear==MAX_QUEUE_SIZE-1)return ;Q.Queue_array[Q.rear++]=e ; }void deQueue(SqQueue &Q, ElemType *x ){ if (Q.front== Q.rear)return ; *x=Q.Queue_array[Q.front++] ; }*/LinkQueue *Init_LinkQueue(void){ QNode *p=(QNode *)malloc(sizeof(QNode)) ; /* 开辟头结点 */p->next=NULL ;LinkQueue *Q=(LinkQueue *)malloc(sizeof(LinkQueue)) ; /* 开辟链队的指针结点 */(*Q).front=(*Q).rear=p ; return(Q) ;}void enLinkQueue(LinkQueue *Q , ElemType e) /* 将数据元素e插入到链队列Q的队尾 */{ QNode* p=(QNode *)malloc(sizeof(QNode)) ;if (!p) return;p->data=e ; p->next=NULL ; /* 形成新结点 */(*Q).rear->next=p ; (*Q).rear=p ; /* 新结点插入到队尾 */}void deLinkQueue(LinkQueue *Q, ElemType *x) { QNode *p ;if ((*Q).front==(*Q).rear) return ; /* 队空 */p=(*Q).front->next ; /* 取队首结点 */*x=p->data ; (*Q).front->next=p->next ; /* 修改队首指针 */if (p==(*Q).rear) (*Q).rear=(*Q).front ; /* 当队列只有一个结点时应防止丢失队尾指针 */ free(p) ; }循环队列：
为充分利用向量空间，克服上述“假溢出”现象的方法是：将为队列分配的向量空间看成为一个首尾相接的圆环，并称这种队列为循环队列(Circular Queue)。
在循环队列中进行出队、入队操作时，队首、队尾指针仍要加1，朝前移动。只不过当队首、队尾指针指向向量上界(MAX_QUEUE_SIZE-1)时，其加1操作的结果是指向向量的下界0。
这种循环意义下的加1操作可以描述为：
if (i+1==MAX_QUEUE_SIZE) i=0;
else i++ ;
其中： i代表队首指针(front)或队尾指针(rear)
cirqueue.h
#define MAX_QUEUE_SIZE 100typedef int ElemType;typedef struct queue{ ElemType Queue_array[MAX_QUEUE_SIZE] ;int front ;int rear ;}SqQueue;SqQueue Init_CirQueue(void);int length(SqQueue Q);void enCirQueue(SqQueue Q , ElemType e);void deQueue(SqQueue Q, ElemType *x );cirqueue.c
#include "cirqueue.h"SqQueue Init_CirQueue(void){ SqQueue Q ;Q.front=Q.rear=0; return(Q) ;}int length(SqQueue Q){return (Q.rear-Q.front+MAX_QUEUE_SIZE)%MAX_QUEUE_SIZE;}void enCirQueue(SqQueue Q , ElemType e) /* 将数据元素e插入到循环队列Q的队尾 */{ if ((Q.rear+1)%MAX_QUEUE_SIZE== Q.front)return ; /* 队满，返回 */Q.Queue_array[Q.rear]=e ; /* 元素e入队 */Q.rear=(Q.rear+1)% MAX_QUEUE_SIZE ; }void deQueue(SqQueue Q, ElemType *x ) /* 将循环队列Q的队首元素出队 */{ if (Q.front+1== Q.rear)return ; /* 队空，返回错误标志 */*x=Q.Queue_array[Q.front] ; /* 取队首元素 */Q.front=(Q.front+1)% MAX_QUEUE_SIZE ; /* 队首指针向前移动 */}