关于栈的问题，求大佬解答第三问

*/ # include # include typedef struct Node{
int date;
struct Node * pNext;}NODE,* PNODE;typedef struct Stack{
PNODE pTop;
PNODE pBottom;}STACK, * PSTACK;void init(PSTACK pS){
pS->pTop = (PNODE)malloc(sizeof(NODE));
if (NULL == pS->pTop)
{
printf("动态内存分配失败");
exit(-1);

}
else
{
pS->pBottom = pS->pTop;//如果分配成功的话，这两个节点都指向 同一个节点（头节点）
pS->pTop->pNext = NULL; //模拟最后的那个“头节点”pS->Bottom->pNext = NUll 也是一样
}
}void push(PSTACK pS, int val){
PNODE pNew = (PNODE)malloc(sizeof(NODE));
pNew->date = val;
pNew->pNext = pS->pTop;//按照逻辑来的话，进栈时，新的元素会在栈顶，所以要pNext->pTop
pS->pTop = pNew; //把新的入栈的元素作为栈的top
} void traverse(PSTACK pS){
PNODE p = pS->pTop;
while (p != pS->pBottom)
{
printf("%d ",p->date);
p = p->pNext;
}
printf("
");

return;} bool empty(PSTACK pS){
if(pS->pTop == pS->pBottom)
return true; //如果为空，返回true（证明是空的）
else
return false;} //把pS所指向的栈出栈一次，并把出栈的元素存入pVal形参所指向的变量中，//如果出栈成功，返回true，否则返回false bool pop(PSTACK pS,int * pVal){
if (empty(pS))//pS 本身存放的就是S的地址，直接返回给empty()函数
{
return false;
}
else
{
//首先需要一个指针r来指向 栈顶元素，但是如果是pS->pTop = pS->pNext 的话
//内存就没有释放，造成内存泄漏，所以这个方法不可取。

PNODE r = pS->pTop;
*pVal = r->date;
pS->pTop = r->pNext;//r 指向栈顶，所以把r的next域赋给栈顶
free(r);
r = NULL;
return true;


}}//清空 void clear(PSTACK pS){
if(empty(pS))
{
return;
}
else
{
PNODE p = pS->pTop;
PNODE q = NULL;
while(p!=pS->pBottom)
{
q = p->pNext;
free(p);
p = q;

}
//清空之后pTop 的值一定要改写
pS->pTop = pS->pBottom;

}
}int main(void){
STACK S;
int val;
init(&S);//对栈进行初始化 ,去地址才会放入元素
push(&S,1);
push(&S,2);
push(&S,3);
push(&S,4);
push(&S,5);
push(&S,6);
traverse(&S);
clear(&S); //清空之后就会提示出栈失败

if(pop(&S,&val))//需要判断是否为空，如果空了就无法出栈，所以需要一个返回值，但是进栈不会满的。
{
printf("出栈成功，出栈的元素是%d
",val);
}
else
{
printf("出栈失败!
");
}
traverse(&S);
return 0;}
运行演示

算法小结
所有的算法已经给出，值得注意的是在clear()算法中 PNODE p = pS->pTop;PNODE q = NULL; 定义了两个指针，以为一个被free掉后就无法进行操作了，对于pop()函数就没有这个问题，因为它只执行了一次 ，也就是说，只进行了一次出栈操作，然后操作完成之后才把r指针给free掉的，所以一个指针就可以完成这个操作。

限定性线性表——队列
队列是另外一种限定性的线性表，它只允许在表的一端插入元素，在另外一端删除元素。
基本算法演示（链队列）

#include #include typedef struct Node{
int date;
struct Node * pNext;}NODE, * PNODE;//LInkQueueNodetypedef struct LinkQueue{
PNODE pFront;
PNODE pRear;}LINKQUEUE,* PLINKQUEUE;bool InitQueue(PLINKQUEUE pQ){
pQ->pFront= (PNODE)malloc(sizeof(NODE));
if (NULL == pQ->pFront)
{
printf("动态内存分配失败！");
exit(-1);

}
else if(NULL != pQ->pFront)
{
pQ->pRear = pQ->pFront;
pQ->pFront->pNext = NULL;
return (true);
}
else
return (false);//溢出

}bool EnterQueue(PLINKQUEUE pQ ,int x){


PNODE pNew = (PNODE)malloc(sizeof(NODE));
if(pNew != NULL)
{
pNew->date = x;
pNew->pNext = NULL;
pQ->pRear->pNext = pNew;
pQ->pRear = pNew;
return (true);

}
else
return false;} void traverse(PLINKQUEUE pQ){
PNODE p = pQ->pFront->pNext;//注意这个地方队列和栈的不同
//PNODE p = pS->pTop;   while (p != pS->pBottom)  这是栈的条件

while (p)
{
printf("%d ",p->date);
p = p->pNext;
}
printf("
");

return;} bool DeleteQueue(PLINKQUEUE pQ,int * x)   //出队{
PNODE p;
if (pQ->pRear==NULL)      //队列为空
return false;
p=pQ->pFront;            //p指向第一个数据节点
if (pQ->pFront==pQ->pRear)  //队列中只有一个节点时
pQ->pFront=pQ->pRear=NULL;//必须要更改值，不然指针就会指向他处
else                    //队列中有多个节点时
pQ->pFront=pQ->pFront->pNext;
*x = p->date;
free(p);
return true;}int main(){
LINKQUEUE Q;
int x;
InitQueue(&Q);
EnterQueue(&Q,10);
EnterQueue(&Q,20);
EnterQueue(&Q,30);
EnterQueue(&Q,40);
traverse(&Q);
DeleteQueue(&Q,&x);
traverse(&Q);
return 0; }
运行演示

算法小结
队列的操作和栈的操作基本原理上是差不多的，值得注意的是再对队列进行遍历的话和栈的遍历稍微有点差别。其中需要注意的地方已经在代码块中进行了说明。
基本算法演示（循环队列）

// 实现循环队列 #include #include #define MaxSize 21typedef int ElementType;typedef struct  {
int data[MaxSize];
int rear;      // 队尾指针
int front;     // 队头指针 }Queue,*L;void InitQueue(Queue * Q ){
Q->front = Q->rear = 0;}// 元素入队void AddQ(Queue *PtrQ, int item){
if( (PtrQ->rear+1)%MaxSize == PtrQ->front )
{
printf("队列满.
");
return;
}
PtrQ->rear = (PtrQ->rear+1) % MaxSize;
PtrQ->data[PtrQ->rear] = item; }// 删除队头元素并把队头元素返回int DeleteQ( Queue *PtrQ ){
if( PtrQ->front == PtrQ->rear )
{
printf("队列空.
");
return -1;
}
else {
PtrQ->front = (PtrQ->front+1) % MaxSize;
return PtrQ->data[PtrQ->front];
}}// 队列元素的遍历void print(Queue *PtrQ){
int i = PtrQ->front;
if( PtrQ->front == PtrQ->rear )
{
printf("队列空.");
return;
}
printf("队列存在的元素如下:");
while( i != PtrQ->rear)
{
printf("%d ", PtrQ->data[i+1]);
i++;
i = i % MaxSize;
}
return;}int len(Queue *PtrQ){
return (PtrQ->rear-PtrQ->front+MaxSize)%MaxSize;}int main(){
Queue  Q;    //注意不是Queue * Q; 因为数组本身就是地址吧~（emmmm,应该是，求大佬解答）
int length;
length = len(&Q);             //用Queue * Q 的话会报错
InitQueue(&Q);
AddQ(&Q,1);
AddQ(&Q,2);
AddQ(&Q,3);
AddQ(&Q,4);

print(&Q);
DeleteQ(&Q);//出队一次
print(&Q);
printf("
循环队列的长度为%d",length);
return 0;}
运行演示

算法小结
循环队列和链队列基本是一致的，之所以引入“循环队列”是因为，对于顺序列会存在“假溢出的现象”。相关概念不多做解释，原理主要在数据结构-用C语言描述（第二版）[耿国华] 一书的p101-103。值得注意的是，在main方法中和链队列不同的是Queue Q;个人认为是利用数组模拟的原因，因为数组本身也是利用地址传值嘛。关于循环队列长度计算：当rear大于front时，循环队列的长度：rear-front，当rear小于front时，循环队列的长度:分为两类计算 0+rear和Quesize-front即rear-front+Quesize。总的来说，总长度是(rear-front+Quesize)%Quesize