栈和队列的基本操作（分顺序和链式，5种基本操作有创建，判空，判满，入，出）

顺序栈的两种方式：

//法一：数组方式，最常用 #include<iostream> using namespace std; #define MAXSIZE 2 //const ElementType MAXSIZE=2; typedef int ElementType; struct SeqStack{ ElementType data[MAXSIZE]; int top; }; //typedef struct node * SeqStack;//节点的结构体内没有出现指针，所以不能有指针 void CreateStack(SeqStack & S){ //栈发生改变，要& S.top= -1; } bool IsEmpty(SeqStack S){ //判断栈是否为空 return (S.top == -1); } bool IsFull( SeqStack S ){ //判断栈满 return (S.top == MAXSIZE-1); } bool Push(SeqStack & S, ElementType x){ //栈发生改变，而入栈的元素本身不发生改变，所以前者要&,后者不要& if ( IsFull( S ) ) return false; /*即S->top==MAXSIZE-1栈满不能入栈*/ else{ S.data[++S.top]=x; return true; } } ElementType Pop(SeqStack & S){ if ( IsEmpty( S ) ) return false; /*即S->top==-1栈空不能出栈,false就是0，0是 ElementType类型的  */ else return (S.data[(S.top)--]); } int main(){ SeqStack S; CreateStack(S); bool aa=IsEmpty(S); cout<<aa<<endl; //1即true Push(S,21); Push(S,23); bool bb=IsFull(S); cout<<bb<<endl;//1即true int x=Pop(S); cout<<x<<endl;//23 int y=Pop(S); cout<<y<<endl;//21 return 0; }

//法二：指针方式 #include<iostream> //#include<malloc.h> //c用malloc和free创建和删除节点，C++中用new和delete来创建 和删除节点 #define MAXSIZE 2 //const ElementType MAXSIZE=2; using namespace std; typedef int ElementType; struct SeqStack{ ElementType * data; /* 存储元素的数组 */ int max; /* 堆栈最大容量 */ int top; /* 栈顶指针 */ }; SeqStack * CreateStack( int max){ SeqStack * S = new SeqStack;//(SeqStack) malloc (sizeof(struct node)) S->data = new ElementType;//(ElementType *)malloc(max * sizeof(ElementType)) S->top = -1; S->max = max; return S; } bool IsFull( SeqStack * S ){ return (S->top == S->max-1); } bool IsEmpty( SeqStack * S ){ return (S->top == -1); } bool Push( SeqStack * S, ElementType x){ if ( IsFull(S) ) return false; /*即S->Top == -1栈满不能入栈*/ else { S->data[++(S->top)] = x; return true; } } ElementType Pop( SeqStack * S ){ if ( IsEmpty(S) ) return false; /*即S->Top == max-1栈满不能入栈，false就是0，0是 ElementType类型的*/ else return ( S->data[(S->top)--] ); } int main(){ SeqStack * S; S=CreateStack(MAXSIZE); bool aa=IsEmpty(S); cout<<aa<<endl; //1即true Push(S,21); Push(S,23); bool bb=IsFull(S); cout<<bb<<endl;//1即true int x=Pop(S); cout<<x<<endl;//23 int y=Pop(S); cout<<y<<endl;//21 return 0; }

链栈

//链栈即为：带空白头结点的单链表 #include<iostream> //#include<malloc.h> //c用malloc和free创建和删除节点，C++中用new和delete来创建 using namespace std; typedef int ElementType; struct LinkStack{ ElementType data; LinkStack * next; }; LinkStack * CreateStack(){ /* 构建一个堆栈的空白头结点，返回该结点指针 */ LinkStack * S = new LinkStack;//(LinkStack *)malloc(sizeof(struct LinkStack)) S->next = NULL; return S; } bool IsEmpty(LinkStack * S){ /* 判断堆栈S是否为空，若是返回true；否则返回false */ return ( S->next == NULL ); } //链表不存在栈满的情况 bool Push(LinkStack * S, ElementType x){ /* 将元素X压入堆栈S */ LinkStack * tmp = new LinkStack;//(LinkStack *)malloc(sizeof(struct LinkStack)) tmp->data = x; tmp->next=NULL; //头插法 tmp->next = S->next; S->next = tmp; return true; } ElementType Pop(LinkStack * S){ /* 删除并返回堆栈S的栈顶元素 */ LinkStack * first; ElementType x; if( IsEmpty(S) ) return false; //false就是0，0是 ElementType类型的 else{ first = S->next; x = first->data; S->next = first->next; delete(first);//free(first); return x; } } int main(){ LinkStack * S; S=CreateStack(); bool aa=IsEmpty(S); cout<<aa<<endl; //1即true Push(S,21); Push(S,23); int x=Pop(S); cout<<x<<endl;//23 int y=Pop(S); cout<<y<<endl;//21 return 0; }

顺序循环队列的两种方式

//法一:数组方式，最常用 #include<iostream> //#include<malloc.h> //c用malloc和free创建和删除节点，C++中用new和delete来创建 using namespace std; #define MAXSIZE 3 typedef int ElementType; struct SeqQueue{ ElementType data[MAXSIZE]; /*存储元素的数组*/ int front,rear; /*队列的头、尾指针*/ int max; /*队列最大容量*/ }; void CreateQueue(SeqQueue & Q){ Q.front=Q.rear=0; } bool IsEmpty(SeqQueue Q){ return (Q.front==Q.rear); } bool IsFull(SeqQueue Q){ return ( (Q.rear+1) % MAXSIZE == Q.front ); } bool Push(SeqQueue & Q,ElementType x){ if(IsFull(Q)){ return false; }else{ Q.rear=(Q.rear+1) % MAXSIZE;//先移动指针 Q.data[Q.rear]=x; return true; } } ElementType Pop(SeqQueue & Q){ if(IsEmpty(Q)) return false;//false就是0，0是 ElementType类型的 else{ Q.front=(Q.front+1) % MAXSIZE;//先移动指针 return Q.data[Q.front]; } } int main(){ SeqQueue Q; CreateQueue(Q); bool aa=IsEmpty(Q); cout<<aa<<endl; //1即true Push(Q,21); Push(Q,23); bool bb=IsFull(Q); cout<<bb<<endl;//1即true int x=Pop(Q); cout<<x<<endl;//21 int y=Pop(Q); cout<<y<<endl;//23 return 0; }

//法二:指针方式 #include<iostream> //#include<malloc.h> //c用malloc和free创建和删除节点，C++中用new和delete来创建 using namespace std; #define MAXSIZE 3 typedef int ElementType; struct SeqQueue{ ElementType * data; /*存储元素的数组*/ int front,rear; /*队列的头、尾指针*/ int max; /*队列最大容量*/ }; SeqQueue * CreateQueue(int max){ SeqQueue * Q =new SeqQueue; //(SeqQueue *)malloc(sizeof(struct SeqQueue)) Q->data=new ElementType; //(ElementType *)malloc( max * sizeof(ElementType) ) Q->front=Q->rear=0; Q->max=max; return Q; } bool IsEmpty(SeqQueue * Q){ return (Q->front==Q->rear); } bool IsFull(SeqQueue * Q){ return ( (Q->rear+1) % Q->max == Q->front ); } bool Push(SeqQueue * Q,ElementType x){ if(IsFull(Q)){ return false; }else{ Q->rear=(Q->rear+1) % Q->max;//先移动指针 Q->data[Q->rear]=x; return true; } } ElementType Pop(SeqQueue * Q){ if(IsEmpty(Q)){ return false;//false就是0，0是 ElementType类型的 }else{ Q->front=(Q->front+1) % Q->max;//先移动指针 return Q->data[Q->front]; } } int main(){ SeqQueue * Q; Q=CreateQueue(MAXSIZE); bool aa=IsEmpty(Q); cout<<aa<<endl; //1即true Push(Q,21); Push(Q,23); bool bb=IsFull(Q); cout<<bb<<endl;//1即true int x=Pop(Q); cout<<x<<endl;//21 int y=Pop(Q); cout<<y<<endl;//23 return 0; }

链队列

//链队列即为：带空白头结点的单链表，单链表实体节点部分设置一头一尾指针 #include<iostream> //#include<malloc.h> //c用malloc和free创建和删除节点，C++中用new和delete来创建 using namespace std; #define MAXSIZE 3 typedef int ElementType; struct node{ //队列中的每个节点 ElementType data; node * next; }; struct LinkQueue{ //队列 node * front,* rear; /*队列的头、尾指针*/ }; LinkQueue * CreateQueue(){ LinkQueue * Q=new LinkQueue;//(LinkQueue *)malloc(sizeof(LinkQueue)) Q->front=Q->rear=NULL; return Q; } bool IsEmpty(LinkQueue * Q){ return ( Q->rear == NULL); //也可以这么写：return ( (Q->front == NULL) || (Q->rear == NULL) ); } //不存在队列满的情况 bool Push(LinkQueue * Q,ElementType x){ node * tmp= new node;//(node *)malloc(sizeof(node)) tmp->data=x; tmp->next=NULL; if( IsEmpty(Q) ){//队空,则新节点既是队首节点，也是队尾节点 Q->front=Q->rear=tmp; }else{//队不空 Q->rear->next=tmp; Q->rear=tmp; } return true; } ElementType Pop(LinkQueue * Q){ node * tmp;// int x; if(IsEmpty(Q)) return false;//false就是0，0是 ElementType类型的 else tmp=Q->front; if(Q->front==Q->rear){//队列中只剩最后一个节点时 Q->front=Q->rear=NULL; }else{ Q->front=Q->front->next; } x=tmp->data; delete(tmp);//free(tmp); return x; } int main(){ LinkQueue * Q; Q=CreateQueue(); bool aa=IsEmpty(Q); cout<<aa<<endl; //1即true Push(Q,21); Push(Q,23); int x=Pop(Q); cout<<x<<endl;//21 int y=Pop(Q); cout<<y<<endl;//23 return 0; }