数据结构——复习三

栈和队列
栈：仅在表尾进行插入或删除操作的线性表
栈顶：在栈顶操作，是表尾，通常用top表示
栈底：bottom，是表头
空栈：空表
通常栈底固定，栈顶移动，特点是：先进后出（FILO）或后进先出（LIFO）

有顺序栈和链栈
//我们打比赛的时候一般都不会自己构建，都是用现成的，哈哈，只是要学习一下这种思想，思考方式
顺序栈
利用一组地址连续的存储单元依次自栈底到栈顶存放栈的数据元素。在数组上实现时，栈底位置可以设置在数组的任一个端点，而栈顶是随着插入和删除而变化的，可以用一个整形变量top存放栈顶的指针，数据入栈或出栈时使top分别加1或减1。
top=-1，栈空，此时出栈，则下溢
top=M-1，栈满，此时入栈，则上溢
top的初值是-1
链栈
用链式存储结构实现的栈称为链栈。通常链栈可用单链表表示，因此其结点结构与单链表的结构相同。通常我们也不设头结点。
//以前的代码，现在拿来总结一下

//顺序栈
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int MAXN=1000;
typedef struct as{
    int data[1000];
    int top;//栈顶元素的下标
}seqstack;
seqstack s;
void init()
{
    s.top=-1;
}
void push()//入栈
{
 int x;
 if(s.top==MAXN-1)
 printf("栈满\n");
 else
 {
 scanf("%d",&x);
 s.top++;
 s.data[s.top]=x;
 }
}
void pop()//出栈
{
 int y;
 if(s.top==-1)
 printf("栈空\n");
 else
 {
 y=s.data[s.top];
 s.top--;
 printf("%d\n",y);
 }
}
int main()
{
    int n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        push();
    }
    for(i=1;i<=n;i++)
    {
        pop();
    }
    return 0;
}
//链栈
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct as{
    int date;
    struct as *next;
}stacknode,*linkstack;
linkstack s;
void init()
{
  s=NULL;
}
void push()//入栈
{
    int x;
    scanf("%d",&x);
    linkstack p;
    p=(linkstack)malloc(sizeof(stacknode));
    p->date=x;
    p->next=s;//这里是栈与链表的差别
    s=p;
}
void pop()//出栈
{
 if(s==NULL)
 printf("栈空\n");
 else
 {
     printf("%d\n",s->date);
     s=s->next;
 }
}
int main()
{
    int n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        push();
    }
    for(i=1;i<=n;i++)
    {
        pop();
    }

    return 0;
}

两种方式的比较：
顺序栈需预先定义栈的长度，浪费空间，链栈长度可变但需增加结构性开销。
程序中用多个顺序栈时，为减少栈的溢出，提高空间利用率，通常用一个数组空间存放多个顺序栈。
双向栈
两个栈共享一个向量空间，栈底分别设在两端。

在这里插入代码片

栈的应用：
1.数制转换
2.括号匹配
3.栈与递归过程


队列：队列是一种只允许在表的一端插入，在另一端删除的存取受限的线性表。
队尾rear：插入端，线性表的表尾。
队头front：删除端，线性表的表头。
空队列：队列没有任何元素。

顺序和链式存储结构
队列的顺序存储结构
跟栈不同队列用数组存在一些问题，设数组维数为M，则：
当f=0，r=M时，再有元素入队发生溢出——真溢出
当f不等于0，r=M时，再有元素入队发生溢出——假溢出
解决方法：
循环队列：
入队：q[r]=x;r=(r+1)%M;
出队：x=q[f];f=(f+1)%M;
还有一个问题
空队列条件：Q.rear==Q.front

满队列条件：Q.rear==Q.front
我们要区分队空和队满，有三种方法：
1.少用一个存储空间
2.引入一个标志变量区别空和满
3.使用计数器
链队列：需要指示队头和队尾的两个指针。

//用链表
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node{//头是空的头结点，尾是正好指向最后一个数
    int data;
    struct node *next;
}Node,*queueptr;
typedef struct
{
    queueptr front;
    queueptr rear;
}LinkQueue;
void init(LinkQueue &q)
{
 q.rear=q.front=(queueptr)malloc(sizeof(Node));
 q.front->next=NULL;
}
int ans=0;
void push(LinkQueue &q)
{
int x;
queueptr p;
  while(1)
  {
    scanf("%d",&x);
    if(x==0)
    break;
    ans++;
    p=(queueptr)malloc(sizeof(Node));
    p->data=x;
    q.rear->next=p;
    q.rear=p;
  }
}
void put(LinkQueue &q)
{
    queueptr p;
    if(q.front==q.rear)
    return;
    p=q.front->next;
    printf("%d ",p->data);
    q.front->next=p->next;//改变头指针的位置
    if(q.rear==p)
    {
     q.rear=q.front;
    }

}
int main()
{
     LinkQueue q;
     int i;
     init(q);
     push(q);
     for(i=1;i<=ans;i++)
     {
         put(q);
     }

    return 0;
}
//用顺序结构
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//顺序表存储队列（循环），要判断是否为满和空，一般有两种方法，头在第一个元素的下标，尾在最后一个元素的后一个元素的下标
const int maxnsize=100;
typedef struct
{
 int data[maxnsize];
 int front;
 int rear;
}sequeue;
void init(sequeue &q)
{
    q.front=q.rear=0;
}

void enqueue(sequeue &q,int x)
{
 if((q.rear+1)%maxnsize==q.front)
 {printf("队满\n");return;}
 q.data[q.rear]=x;
 q.rear=(q.rear+1)%maxnsize;
}
void dequeue(sequeue &q)
{
    if(q.rear==q.front)
    {
        printf("队空\n");
        return;
    }
    printf("%d ",q.data[q.front]);
    q.front=(q.front+1)%maxnsize;
}
int main()
{
    int x,i;
    int ans=0;
    sequeue q;
    init(q);
    while(1)
    {
        scanf("%d",&x);
        if(x==0)
       break;
        enqueue(q,x);
        ans++;
    }
    for(i=1;i<=ans;i++)
    {
        dequeue(q);
    }
    printf("\n");
    return 0;
}

顺序链表中还有一种判断队列空满的方法。

typedef struct
{
    ElemType Q[m];
    int rear,front;  //队尾和队头指针
    int tag;    //标记, 0为空,1为非空
} CycQueue;
CycQueue  QueueIn(CycQueue cq,ElemType x)//入队
{
    if(cq.tag==1&&cq.front==cq.rear)
    {
        printf("队满\n");
        exit(0);
    }
    else
    {
        cq.rear=(cq.rear+1)%m;
        cq.Q[cq.rear]=x;//入队一个数，一定不空
        if(cq.tag==0)//这句删掉也行
        cq.tag=1;
        //由空变不空标记
    }
    return cq;
}
CycQueue  QueueOut(CycQueue cq)//出队
{
    if (cq.tag==0)
    {
        printf("队空\n");
        exit(0);
    }
    else
    {
        cq.front=(cq.front+1)%m;
        if(cq.front==cq.rear)//出队的时候只会造成队空
            cq.tag=0;    //队列由不空变空
    }
    return cq;
}

队列链表也可以用带头结点的循环链表实现，只用一个尾指针。

typedef struct Lqueue
{
    ElemType data;
    struct Lqueue *next;
} Lqueue,*Queueptr;
void QueueIn(Queueptr rear, ElemType x)
{
    //入队列
    s=(Queueptr)malloc(sizeof(LQueue));
    s->data=x;
    s->next=rear->next;       //元素插入队尾//必须要这样，因为尾后面连了头结点
    rear->next=s;
    rear=s;         //求得新的队尾
}
ElemType QueueOut(Queueptr rear)
{
    //出队列
    if(rear->next==rear)
        printf("队列为空\n");
    else
    {
        p=rear->next;
        q=p->next;
        p->next=q->next;
        x=q->data;
        //删除队头元素
        if(q==rear) rear=p;
        free(q);
        return(x);
    }
}