栈和队列都是最基础的数据结构，栈的思想是“先进后出”，队列的思想是“先进先出”。怎么说呢，栈和队列其实都是对于单链表或者数组的一些特殊操作。在后边很多算法中经常用到（比如BFS， SPFA。。。）
栈主要操作有：
入栈Push；
取栈顶Get_Top;
出栈（删除栈顶元素）Pop；
栈的数组实现（代码非常简单，关键是思想）：
//数组实现#include#include #define maxsize 10typedef struct{ int data[maxsize]; int top; int base;}seqstack;seqstack * s;void initstack(seqstack * s){ s->top = 0; s->base = 0;}int empty(seqstack * s){ if(s->top == s->base) return 1; else return 0;}void push(seqstack * s, int x){ if(s->top >= maxsize-1) { printf("ERROR!\n"); } else { s->data[s->top] = x; s->top++; }}void pop(seqstack * s){ if(empty(s)) { printf("ERROR!\n"); } else { s->top--; printf("%d\n",s->data[s->top]); }}int main(){ seqstack * s; s = (seqstack *)malloc(sizeof(seqstack)); initstack(s); push(s,1); push(s,3); pop(s); push(s,2); pop(s); pop(s); pop(s); return 0;}
单链表实现：
//链式#include#include #include typedef struct node{ int data; struct node *next;}node,linkstack;void InitStack(linkstack * top){ top->next = NULL;}int IsEmpty(linkstack * top){ if(top->next == NULL) return 1; return 0;}int Push(linkstack * top, int x){ node * p; p = (node *)malloc(sizeof(node)); if(p == NULL) return 0; p->data = x; p->next = top->next; top->next = p; return 1;}int Pop(linkstack * top, int *x){ node * p; if(IsEmpty(top)) { printf("ERROE!\n"); return 0; } p = top->next; *x = p->data; top->next = p->next; free(p); return 1;}int main(){ int x; linkstack * s; s = (linkstack *)malloc(sizeof(linkstack)); InitStack(s); Push(s,1); Push(s,3); Pop(s,&x); printf("%d\n",x); Push(s,2); Pop(s,&x); printf("%d\n",x); Pop(s,&x); printf("%d\n",x); Pop(s,&x); return 0;}
队列的操作与栈类似，这里不赘述了，且看代码实现：
//数组实现#include#include #define maxsize 66typedef struct{ int data[maxsize]; int front,rear;}sequeue;sequeue * q;void initqueue(sequeue *q){ q->front = -1; q->rear = -1;}int del(sequeue *q){ if(q->front == q->rear) return NULL; else { q->front++; return q->data[q->front]; }}int insertqueue(sequeue *q,int x){ if(q->rear >= maxsize-1) return NULL; else { (q->rear)++; q->data[q->rear] = x; return 1; }}int empty(sequeue * q){ if(q->front == q->rear) return 0; else return 1;}void print(sequeue * q){ if(q->front == q->rear) printf("ERROR!\n"); else { while(empty(q)) { q->front++; printf("%d\n",q->data[q->front]); } }}int main(){ int i; sequeue * q; q = (sequeue *)malloc(sizeof(sequeue)); initqueue(q); for(i = 0; i < 6; i++) insertqueue(q,i); printf("front is %d\n\n",del(q)); printf("Then the last data is:\n"); print(q); return 0;}//链表实现#include #include typedef struct node{ int data; struct node * next;}linklist;typedef struct{ linklist * front, * rear;}linkqueue;linkqueue * q;//建立队列void initqueue(linkqueue * q){ q->front = (linkqueue *)malloc(sizeof(linklist)); q->front->next = NULL; q->rear = q->front;}//判断队列空否int empty(linkqueue * q){ if(q->front == q->rear) return 1; else return 0;}//入队列void inqueue(linkqueue * q, int x){ q->rear->next = (linklist *)malloc(sizeof(linklist)); q->rear->next->data = x; q->rear = q->rear->next; q->rear->next = NULL;}//出队列int outqueue(linkqueue * q){ linklist * s; if(empty(q)) return NULL; else { s = q->front->next; printf("%d\n",s->data); if(s == q->rear) q->front = q->rear; else q->front->next = s->next; free(s); return 1; }}//mainint main(){ int i; linkqueue * l; l = (linkqueue *)malloc(sizeof(linkqueue)); initqueue(l); for(i = 0; i < 10; i++) inqueue(l,i); for(i = 0; i < 10; i++) outqueue(l); return 0;}
ps:转自