栈：后进先出
1-1栈的基本操作以下是利用栈判断回文序列
boolsymmetry(inta[],intl){inti,e;Stack*s;InitStack(s);for(i=0;i<l;i++){Push(s,a[i]);}for(i=0;i<l;i++){Pop(s,e);if(a[i]!=e){DestroyStack(s);returnfalse;}}DestroyStack(s);returntrue;}intmain(){inta[]={1,2,3,2,1};cout<<symmetry(a,5);}
我们也可以利用链式存储完成栈的构建
#include <iostream> #include <stdlib.h> using namespace std; struct Stack//Struct Link { int data; Stack *next; }; void InitStack(Stack *&s) { s = NULL; } void DestroyStack(Stack *&s) { if(s==NULL){ return; } Stack *p=s,*q=s->next; while(q){ free(p); p=q; q=q->next; } free(p); } bool StackEmpty(Stack *s) { return(s==NULL); }//判断栈是否为空 void Push(Stack *&s,int e)//这里不是bool是因为链式存储一般不需要考虑栈满的情况 { if(s==NULL){ s=new Stack; s->next=NULL; s->data=e; return; } Stack *p=s; for(;p->next;p=p->next); p->next=new Stack; p=p->next; p->data=e; p->next=NULL; }//栈的操作只操作最后放入的元素，如果将后来的元素放在队尾部，会给后续操作带来不便 //如果只需要进行栈操作的话，入栈建议将数据放在头部 void Push2(Stack *&s,int e) { if(s==NULL){ s=new Stack; s->next=NULL; s->data=e; return; } Stack *p=new Stack; p->next=s; p->data=e; s=p; } bool Pop(Stack *&s,int &e) { if(s==NULL)return false; e=s->data; Stack *p=s; s=s->next; free(p); return true; } bool GetTop(Stack *&s,int &e) { if(s==NULL)return false; e=s->data; return true; }
队列：先进先出
（来源：mooc——数据结构——武汉大学）
队列需要有队首和队尾两个指针，其它基本操作的实现都可参考栈
将基础操作的rear++和front++改为
#include <stdlib.h> struct Queue { int data[5]; int front; int len; }; void InitStack(Queue *&s) { s=new Queue; s->front=0; s->len=0; } void DestroyStack(Queue *&s) { free(s); } bool StackEmpty(Queue *s) { return(s->len==0); } bool enQueue(Queue *&s,int e) { if(len==5)return false; s->data[(s->front+s->len)%5]=e; len++; return true; } bool deQueue(Stack *&s,int &e) { if(len==0)return false; e=s->data[s->front]; s->front=(s->front+1)%5; return true; }
原文：https://www.cnblogs.com/applerun/p/12912848.html
