数据结构栈和队列的基本算法实现 限定性线性表——栈 栈的定义
栈作为一种限定性的线性表，是将线性表的插入和删除操作限制为仅在表的一端进行。
基本算法演示 /* 栈的常见操作： 1.初始化栈 2.元素进栈 3.元素出栈 4.栈的遍历 5.判断栈是否为空栈 6.清空整个栈 */ # include <stdio.h> # include <stdlib.h> 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("\n"); 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\n",val); } else { printf("出栈失败!\n"); } traverse(&S); return 0; } 运行演示所有的算法已经给出，值得注意的是在clear()算法中 PNODE p = pS->pTop;PNODE q = NULL; 定义了两个指针，以为一个被free掉后就无法进行操作了，对于pop()函数就没有这个问题，因为它只执行了一次 ，也就是说，只进行了一次出栈操作，然后操作完成之后才把r指针给free掉的，所以一个指针就可以完成这个操作。
队列是另外一种限定性的线性表，它只允许在表的一端插入元素，在另外一端删除元素。
基本算法演示（链队列） /* 队列的常见操作： 1.初始化队列 2.元素进队列 3.元素出队列 4.队列的遍历 */ #include <stdio.h> #include <stdlib.h> typedef struct Node { int date; struct Node * pNext; }NODE, * PNODE;//LInkQueueNode typedef 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("\n"); 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; } 运行演示