数据结构--栈与队列

专题--栈与队列

　　栈：先入后出。
　　队列：先入先出。
  1 #include <iostream>
  2 #include <cstdlib>
  3 
  4 using namespace std;
  5 
  6 const int MAXSIZE=100;
  7 //顺序存储
  8 struct Stack
  9 {
 10     int data[MAXSIZE];
 11     int top;
 12 };
 13 //两栈共享空间结构
 14 struct DStack
 15 {
 16     int data[MAXSIZE];
 17     int top1;
 18     int top2;
 19 };
 20 
 21 //链式存储(不需要头结点)
 22 struct StackNode
 23 {
 24     int data;        //数据域
 25     StackNode *next; //指针域
 26 };
 27 typedef StackNode *LinkStackPtr;
 28 struct LinkStack
 29 {
 30     LinkStackPtr top; //头指针
 31     int count;        //存储元素个数，用来判断链栈是否为空
 32 };
 33 //入栈
 34 bool Push(LinkStack *S,int e)
 35 {
 36     StackNode *s=new StackNode;
 37     s->data=e;
 38     s->next=S->top;
 39 
 40     S->top=s;
 41     ++S->count;
 42     return true;
 43 
 44 }
 45 //出栈
 46 bool Pop(LinkStack *S,int *e)
 47 {
 48     if(S->count==0)
 49         return false;
 50 
 51     *e=S->top->data;
 52 
 53     StackNode *p=S->top;
 54     S->top=S->top->next;
 55     delete p;
 56 
 57     --S->count;
 58     return true;
 59 }
 60 /*****************/
 61 //队列(先进先出)，有头结点
 62 struct QNode
 63 {
 64     int data;
 65     QNode *next;
 66 };
 67 typedef QNode *QueuePtr;
 68 struct LinkQueue
 69 {
 70     QueuePtr front,rear; //头指针和尾指针
 71 };
 72 //入队列
 73 bool EnQueue(LinkQueue *Q,int e)
 74 {
 75     QNode *s=new QNode;
 76     if(!s)
 77         exit(-1);
 78     s->data=e;
 79     s->next=nullptr;
 80 
 81     Q->rear->next=s;
 82     Q->rear=s;
 83 }
 84 //出队列
 85 bool DeQueue(LinkQueue *Q,int *e)
 86 {
 87     if(Q->front==Q->rear)
 88         return false;
 89 
 90     QNode *p;
 91     p=Q->front->next;
 92     *e=p->data;
 93     Q->front->next=p->next;
 94 
 95     if(Q->rear==p)          //注意：若队头是队尾，则删除后将rear指向头结点
 96         Q->rear=Q->front;
 97     delete p;
 98 
 99     return true;
100 }