栈，队列及循环队列，是数据结构中的重要的且常用的内容，最近在学习数据结构，于是作一篇笔记记录一下，希望以后复习有帮助
1.栈：
栈是限定仅在表尾进行插入或删除操作的线性表。我们把表尾称作栈顶(top)，相应的，表头称作栈底(bottom)，由栈的特性可知，栈是一种后进先出(LIFO)的线性表，下面对栈的建立、基本操作及注意事项做一个说明：
上图详细的勾勒出了栈的四种基本形态，通过观察我们知道，非空栈的top指针永远指向栈顶的后一位，并且base指针的位置保持不变，事实上，base指针除了在创建栈、扩容栈的时候被直接调用外，它都是不变的，这是因为我们不能直接对栈底元素进行操作，所以改变bese的指向之类的行为是毫无意义的。当我们注意看第四个图，发现栈已经满了，top指针溢出有效位置，实际上这种情况是不被允许的，对计算机随机位置的内存空间进行调用是不被推荐的，因此我们为了让栈保持功能，选择了对其进行扩容处理，就是在栈满时使用realloc()对其重新进行空间分配，确保不会有指针溢出的情况。
基于上面的原理，我们不难想到实现思路：
1.规定top、base指针，并确定栈的初始大小stacksize，将这三者封装为一个整体MyStack;
2.初始化一个栈，使用malloc()动态分配空间，注意空间大小是stacksize × sizeof(ElemType)，即元素类型大小×元素个数，并 将top和base指针同时指向这片空间的存储首地址;
3.元素入栈先判断是否满栈，是就扩容，否就让元素入栈，并且让top指向下一个位置;
4.元素出栈先判断是否空栈，是就退出，否就让元素出栈，并且让top指向上一个位置;
5.元素空栈的充要条件是top = base; 满栈是top >= base+stacksize;
6.清空栈即是让top = base; 销毁栈则是free(base),top = base =NULL;
7.可以通过top指针来遍历栈;
8.top - base的值即是栈长度;
下面给出代码：
#include
#include
#define InitSize 100 //初始大小;
#define DLC 10 //增量;
using namespace std;
typedef struct Stack
{
char *base;
char *top;
int stacksize;
}MyStack;
bool InitStack(MyStack &S) //初始化;
{
S.base = (char *)malloc(InitSize*sizeof (char));
if(!S.base) return false; //内存分配失败;
S.top = S.base;
S.stacksize = InitSize;
return true;
}
bool IsEmpty(MyStack &S) //判空;
{
if(S.base == S.top) return true;
return false;
}
bool IsFull(MyStack &S) //判满;
{
if(S.top >= S.base + S.stacksize) return true;
else return false;
}
bool GetTop(MyStack &S,char &e) //取栈顶;
{
if(IsEmpty(S)) return false;
e = *(S.top - 1);
return true;
}
bool Push(MyStack &S,char e) //入栈;
{
if(IsFull(S))
{
S.base = (char *)realloc(S.base,(S.stacksize + DLC)*sizeof(char));
if(!S.base) return false;
S.stacksize += DLC;
}
*(S.top++) = e;
return true;
}
bool Pop(MyStack &S,char &e) //出栈;
{
if(IsEmpty(S)) return false;
e = *(--S.top);
return true;
}
bool DestoryStack(MyStack S) //销毁;
{
free(S.base);
S.top = S.base = NULL;
S.stacksize = 0;
return true;
}
bool ClearStack(MyStack &S) //清空;
{
S.top = S.base;
return true;
}
bool Traverse(MyStack S) //遍历栈;
{
while(S.top > S.base)
{
cout<<*(--S.top)< } return true; } int GetLength(MyStack S) //取栈长; { return S.top - S.base; } int main() { int n; char e; MyStack S; InitStack(S); cout<<"Enter the number of Elem(s) you want to Push: "< cin>>n; cout<<"Enter each Elem: "< for(int i = 0; i < n; i++) { cin>>e; Push(S,e); } cout<<"Here is what they look like: "< Traverse(S); cout<<"Size: "< cout<<"The top is: "; GetTop(S,e); cout< cout<<"How many Elem(s) do you want to Pop: "< cin>>n; for(int i = 0; i < n; i++) { if(Pop(S,e)) continue; else { cout<<"The stack is empty now!"< break; } } if(!IsEmpty(S)) { cout<<"Here is what's left: "< Traverse(S); cout<<"Size: "< cout<<"The top is: "; GetTop(S,e); cout< } if(ClearStack(S)) cout<<"The stack has been cleared."< Traverse(S); //验证是否清空; if(DestoryStack(S)) cout<<"The stack has been destoryed."< Traverse(S); return 0; } 以上代码DLC是每次栈满时增加的容量，代码中的栈包括初始化、判空、判满、清空、销毁、入栈、出栈、遍历、取栈长、取 栈顶等方法，不是很难写，关键是要理解栈的原理，剩下的都是体力活了。 2.队列： 和栈相反，队列是一种先进先出(FIFO)的线性表，它只允许在一边插入，而在另一边删除元素，我们把删除的一端称为队首(front)，插入的一端称为队尾(rear)，下面对队列做一个说明： 上图很好的反映了队列的几种状态，实际上，形如上图所示的队列叫做链式队列，这是最常用的一种队列，除此之外还有循环队列和双端队列，但是双端队列由于其局限性一般推荐不使用，因此不做说明，这里先介绍链式队列： 显然，跟链表一样，链式队列的基本结构是数据域+指针域，不过多了两个指针——Front和Rear，有了这两个指针的限制，队列就远远不如链表那么灵活，在操作上也有别于链表，下面根据上图，给出实现的思路： 1.首先，将数据域和指针域封装成Queue，再将两个Queue类型的指针Front和Rear封装在一起; 2.用malloc()动态分配空间，并用Front和Rear同时指向它; 3.插入元素的时候，Rear向后指向插入的元素，Front不动; 4.删除元素的时候，Front向后指向被删除元素的后一个元素，Rear不动; 5.以上两条均应该注意是否有越界; 6.队列为空的充要条件是Front = Rear; 下面根据以上思路写出代码： #include #include using namespace std; typedef struct QNode { int data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr Front; QueuePtr Rear; }LinkQueue; bool InitQueue(LinkQueue &Q) //初始化队列; { Q.Front = Q.Rear = (QueuePtr)malloc(sizeof(QNode)); if(!Q.Front) return false; //内存分配失败; Q.Front->next = NULL; return true; } bool DestoryQueue(LinkQueue &Q) //销毁; { while(Q.Front->next != NULL) { Q.Rear = Q.Front->next; free(Q.Front); Q.Front = Q.Rear; } return true; } bool ClearQueue(LinkQueue &Q) //清空; { Q.Rear = Q.Front; return true; } bool Push(LinkQueue &Q,int e) //入队; { QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); if(!p) return false; p->data = e; p->next = NULL; Q.Rear->next = p; Q.Rear = p; p = NULL; return true; } bool Pop(LinkQueue &Q,int &e) //出队; { if(Q.Front == Q.Rear) return false; e = Q.Front->next->data; Q.Front->next = Q.Front->next->next; if(Q.Rear == Q.Front->next) Q.Front = Q.Rear; //空队列; return true; } bool GetFront(LinkQueue Q,int &e) //取队首; { if(Q.Front == Q.Rear) return false; e = Q.Front->next->data; return true; } bool GetLength(LinkQueue Q,int &l) //取队长; { int i = 0; while(Q.Front->next != NULL) { Q.Rear = Q.Front->next; Q.Front = Q.Rear; i++; } l = i; } bool IsEmpty(LinkQueue Q) //判空; { if(Q.Front == Q.Rear) return true; return false; } bool Traverse(LinkQueue Q) //判满; { if(IsEmpty(Q)) return false; while(Q.Front->next != NULL) { Q.Rear = Q.Front->next; cout< Q.Front = Q.Rear; } cout< return true; } int main() { int l,n,e; LinkQueue Q; InitQueue(Q); cout<<"How many elem(s) do you want to push: "< cin>>n; cout<<"Enter "< for(int i = 0; i < n; i++) { cin>>e; Push(Q,e); } cout<<"Here is what they look like: "< Traverse(Q); GetLength(Q,l); GetFront(Q,e); cout<<"Length: "< cout<<"The head is: "< cout<<"How many elem(s) do you want to pop: "< cin>>n; for(int i = 0; i < n; i++) { if(!IsEmpty(Q)) Pop(Q,e); else break; } cout<<"Here is what they look like: "< Traverse(Q); GetLength(Q,l); cout<<"Length: "< if(GetFront(Q,e)) cout<<"The head is: "< if(ClearQueue(Q)) cout<<"Queue Cleared!"< Traverse(Q); //验证是否清空; if(DestoryQueue(Q)) cout<<"Queue Destoryed!"< Traverse(Q); return 0; } 相比链表，链式队列的写法或许显得稍微简单一些，关键还是掌握原理而不要死扣细节，细节是在不断修改的痛苦之上建立起来的，而正确理解原理，才是使代码从一开始就正确的唯一途径。 3.循环队列： 通过以上代码的剖析，不难发现链式队列是（理论上）可以开辟无限空间的，这些空间是动态分配的，而稍不注意就有可能导致空指针、野指针问题出现，为了避免以上问题，我们可以使用循环队列，即，将队列的大小定死，插入和删除在一个封闭的空间内执行，一旦队列满则不再进行插入，而一旦有空闲位置就可以重新插入别的元素，这样可以让空间的使用更加有节制，而不会出现无法控制的情况，但是它的缺点是：空间有限，使用完不能再动态分配空间。这样的队列适合知道具体问题中最大元素个数的时候使用，下面来说明循环队列的原理： 通过上图，不难发现，循环队列是一个（抽象意义上）闭合的内存空间，Rear每次指向队尾的下一个位置，0位置为其首地址，而循环队列的Front却不一定要指向其首地址（哪怕是在队列空或者是满的时候），因为随着不断有元素入队、出队，Front和Rear的位置在不断发生变化，并不能确保每一次队列空/满的时候Front都在首地址上，并且图中画的是满队列和空队列状态一致（Front = Rear），仅仅是出于好理解的意图，实际上这样是不好分辨队列是满或是空的，一般的做法是，认为Front = Rear时队列为空，Rear 的下一个循环位置（等下会解释）等于Front时为满。下面给出实现思路： 1.将ElemType型的指针base、int 型的Front、Rear封装成CQueue; 2.用base指向malloc()新开辟的空间首地址，Front = Rear = 0; 3.为什么要这么做？因为base引用[]符号，如base[Rear]，可以直接调用这一片空间内的第Rear个位置，因此Front和Rear不必是指针类型（封闭空间的好处，和数组是一样的用法）; 4.每次插入元素时，判断队列是否为满，不满则插入，并让Rear指向队尾下一个位置; 5.Rear指向队尾下一个位置的原因是：每次插入后Rear的值都要+1；空队列时Rear = 0，插入后base[0] = Elem;如果Rear指向插入元素，就不能+1，这样会使得后续步骤受影响/也可以单独处理第一个元素的插入，但很麻烦，并且Rear指向下一个位置还有利于判断队列是否满，如果Rear的下一个位置为Front，则认定它满了，因为Rear已经不能再+1了，否则和Front就相等了，这样循环队列最多存MAX-1个元素（MAX为队列最大长度）; 6.每次删除元素时，判断队列是否为空，不空则删除，并让Front向前移一位; 7.其余事项和链式队列大致相当; 下面写出代码： #include #include #include #define MAX 101 //最多存MAX-1个数据元素; using namespace std; typedef struct CQueue { char *base; int Front; int Rear; }CQueue; bool InitCQueue(CQueue &Q) //初始化; { Q.base = (char *)malloc(MAX*sizeof(char)); if(!Q.base) return false; memset(Q.base,'@',sizeof Q.base); //定义'@'代表此处为空; Q.Front = Q.Rear = 0; return true; } bool DestoryCQueue(CQueue &Q) //销毁; { free(Q.base); Q.Front = Q.Rear = 0; return true; } bool ClearCQueue(CQueue &Q) //清空; { memset(Q.base,'@',sizeof Q.base); Q.Front = Q.Rear = 0; return true; } bool IsEmpty(CQueue Q) //判空; { if(Q.Front == Q.Rear) return true; return false; } bool IsFull(CQueue Q) //判满; { if((Q.Rear+1)%MAX == Q.Front) return true; return false; } bool Push(CQueue &Q,char e) //入队; { if(IsFull(Q) || Q.base[Q.Rear] != '@') return false; Q.base[Q.Rear] = e; Q.Rear = (Q.Rear+1)%MAX; return true; } bool Pop(CQueue &Q,char &e) //出队; { if(IsEmpty(Q)) return false; e = Q.base[Q.Front]; Q.Front = (Q.Front+1)%MAX; return true; } bool GetHead(CQueue Q,char &e) //取队首; { if(IsEmpty(Q)) return false; e = Q.base[Q.Front]; return true; } int GetLength(CQueue Q) //取队长; { return (Q.Rear-Q.Front+MAX)%MAX; } bool Traverse(CQueue Q) //遍历队列; { if(IsEmpty(Q)) return false; while(!IsEmpty(Q)) { cout< Q.Front = (Q.Front+1)%MAX; } cout< return true; } int main() { char e; CQueue Q; int n,l; InitCQueue(Q); cout<<"How many elem(s) do you want to push: "< cin>>n; cout<<"Enter "< for(int i = 0; i < n; i++) { cin>>e; if(!IsFull(Q)) Push(Q,e); else continue; } cout<<"Here is what they look like: "< Traverse(Q); GetHead(Q,e); cout<<"Length: "< cout<<"The Head is: "< cout<<"How many elem(s) do you want to pop: "< cin>>n; for(int i = 0; i < n; i++) { if(!IsEmpty(Q)) Pop(Q,e); else break; } cout<<"Here is what they look like: "< Traverse(Q); cout<<"Length: "< if(GetHead(Q,e)) cout<<"The head is: "< if(ClearCQueue(Q)) cout<<"Queue Cleared!"< Traverse(Q); //验证是否清空; if(DestoryCQueue(Q)) cout<<"Queue Destoryed!"< Traverse(Q); return 0; } 这里有一个需要注意的地方：虽然图画成一个圈，但是其存储的物理结构仍然是一条链，不难看出图上内存空间编号是0-8的连续片断，那么如何让它们围成一个圈呢？显然%运算是关键，可以根据初等数论的内容，将此过程与模运算联系起来。 请思考下面的几句代码： if((Q.Rear+1)%MAX == Q.Front) return true; Q.Front = (Q.Front+1)%MAX; Q.Rear = (Q.Rear+1)%MAX; 上面的三句代码正是解决这个问题最核心的东西，我不能保证Front、Rear加1以后不超过MAX的范围，但是我能保证它们的结果对MAX取模以后一定小于MAX，而我们知道取模以后的数，刚好是一个循环，比如0-9分别对3取模，得到序列： 0%3 1%3 2%3 3%3 4%3 5%3 6%3 7%3 8%3 9%3 ... 0 1 2 0 1 2 0 1 2 0 ... 这样可得到永远小于MAX的序列，也就实现了循环而不会使指针越界 其他便没有什么需要注意的了，其实循环队列是最好写也是最好理解的队列了，跟一个数组基本没什么区别，相信只要语言基本功扎实，便不成什么问题。 以上就是今天要写的全部了，Coder之路，路遥而险，还是接着写代码吧...