数据结构复习1110 栈和队列

栈

知识点

顺序栈的数据结构:

#Define Maxsize 50;
typedef struct 
{
Elemtype data[Maxsize];
int top;
}SqStack;
  • top栈顶，动态；botton栈底，静态。
  • 栈顶元素s.data[s.top]
  • 栈长=top+1，栈空=top为-1，栈满：top=Maxsize-1；
  • 进栈：赋值；出栈：读取
    进栈：先自增top，再赋值
bool Push(SqStack &s,elemtype x)
{
if (s.top==Maxsize-1)return false;
s.data[++s.top]=x;
return ture;
}

出栈：先读取再自减。

bool Pop(SqStack &s,elemtype &x)
{
if (s.top==-1)return false;
x=s.data[s.top--];
改为x=s.data[s.top];即为纯读取栈顶。
return ture;
}
  • 若初始化s.top=0；则进栈：s.data[s.top++]=x;出栈:x=s.data[--s.top]。

王道习题：

  1. 判断操作序列（字符串）正确性
bool CheckList(char A[])
{
  int i=0;
  int count1=count2=0;
  while(char[i]!='\0')
{
  if(char[i]==I)count1++;
  else{count2++};
  if(count1<count2)return false;
}
return count==count2?true:false;
}

4.判断链表是否中心对称
不用栈的算法：快慢指针找到中点，尾部翻转，两个子链同步检查
王道给出了使用字符栈的算法

bool symmetry（L）
int len=len(L);
int i=0
char cstack[len/2];
p=p->next;
while(;i<n/2;i++)
{
cstack[i]=p->data;
p=p->next;
}
n个元素，则i为n；
if(len%2==1)p=p->next;
while(p!=null&&p->data==cstack[--i])
{
p=p->next;
}
return i==0?true:false;

5.共享栈
入栈

bool Push(int i,elemtype x)
{
if(i!=0&&i!=1)return false;
if(s.top[1]-s.top[0]=1)return false;栈满
if(i)s.data[--s.top[1]]=x;
else s.data[++s.top[0]]=x;(top初始化为-1，n的好处：自增自减的先后一样)
return true;
}

出栈

bool Pop(int i,elemtype &e)
{
if(i!=0&&i!=1)return false;
if(s.top[1]-s.top[0]=maxsize+1)return false;栈空
if(i=0)
{
if(s.top[0]=-1)return false;
e=s.data[s.top[0]--];
}
else
{
if(s.top[0]=maxsize)return false;
e=s.data[s.top[1]++];
}
return true;
}

使用if，else的可读性稍弱。王道使用了switch+case：

bool Pop(int i,elemtype &e)
{
if(i!=0&&i!=1)return false;
if(s.top[1]-s.top[0]=maxsize+1)return false;栈空
switch(i)
{
case 0:
{
if(s.top[0]=-1)return false;
e=s.data[s.top[0]--];
return true;
}
}
case 1:
{
if(s.top[0]=maxsize)return false;
e=s.data[s.top[1]++];
return true;
}
}

队列

知识点

  • 队头front出队列，队尾tail入

基本操作

顺序存储

typedef strcut
{
Elemtype data[maxsize];
int front,rear;
}SqQueue;
  • 初始时rear=front=0；（判空）
  • 入队列：rear++指向新加入结点，出：front++，指向新的首结点；
  • 假溢出：rear==maxsize

image.png

循环队列

  • rear=rear+1/maxsize
  • len=(rear+maxsize-front)/maxsize
  • 判满：牺牲一个元素，即rear距离front一个结点，因为是循环，所以写作(Q.rear+1)%maxsize==Q.front

入队

bool EnQueue(SqQueue &Q,elemtype x)
{
if((Q.rear+1)%maxsize==Q.front)return false;
Q.data[Q.rear]=x;
Q.rear=(Q.rear+1)/maxsize;
return true;
}

出队

bool DeQueue(SqQueue &Q,elemtype &x)
{
if(Q.rear==Q.front)return false;
x=Q.data[Q.top];
Q.top=(Q.top+1)/maxsize;
return true;
}

链式

  • 带有头指针和尾指针的单链表
  • 判空：和链表一样，分有无头结点的情况。
    初始化
Void InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
Q.front->next=null;
}

判空

bool Empty(Q)
{
if(Q.front==Q.rear)return true;
if(Q.rear->next==null)也可以。
return false;
}

入队

void EnQueue(&Q,x)
{
不需要判断满
LinkNode* s=(LinkNode*)malloc(sizeof(LinkNode));
s->data=x;
s->next=null;
Q.rear->next=s;
Q.rear=s;
}

出队

bool DeQueue(&Q,&x)
{
if(Q.rear==Q.front)return false;判空
x=Q->front->next->data;
Lnode* p=Q.front->next;
Q.front->next=p->next;
free(p);
注意当链表将被删空时，要对rear处理:
if(Q.rear==p){Q.rear=Q.front;}
return true;
}

王道习题

  1. tag判空满
    思想：入队操作将tag置为1，出队0；因为当队满时，上一步一定是出队。
    入
bool EnQueue(&Q,x)
{
if(Q.rear=Q.front&&Q.tag==1)return false;
Q.data[Q.rear]=x;
Q.rear=(Q.rear+1)/maxsize;
Q.tag=1;
return true
}

出

bool DeQueue(&Q,&x)
{
if(Q.rear=Q.front&&Q.tag==0)return false;
Q.data[Q.front]=x;
Q.front=(Q.front+1)/maxsize;
Q.tag=0;
return true
}

2.队列逆序

void Reverse(Q,S)
{
elemtype x;
while(!Q.Empty()){
x=DeQueue(Q);
S.push(S,x);
}
while(!S.Empty()){
x=Pop(S);
EnQueue(Q,x);
}
}
  1. 两个栈模拟队列
    一个容易漏掉的点：栈A满后，再加入数据，若栈B为空，可以先放入栈B。
    出队时，先pop空栈B，再push栈A到栈B，再pop
bool Enqueue(&S1,&S2,x)
{
if(!StackOverFlow(S1)){push(S1,x);return true;}
else if(StackOverFlow(S1)&&!Empty(S2))return false;
else{
  while(!Empty(S1))
  {
  pop(S1,e);
  push(S2,e);
  }
  push(S1,x);
} 
}

bool Dequeue(&S1,&S2,x)
{
if(!Empty(S2)){pop(S2,x);return true;}
else if(Empty(S1)&&Empty(S2))return false;
else{
  while(!Empty(S1))
  {
  pop(S1,e);
  push(S2,e);
  }
  pop(S2,x);
} 
}

核心代码段：

else{
  while(!Empty(S1))
  {
  pop(S1,e);
  push(S2,e);
  }
  pop(S2,x);
}

循环单链表即可
插入的代码:

bool Circle_EnQueue(&Q,x)
{
Lnode* p= (Lnode*)malloc(size(Lnode));
p>data=x;
Q.rear->next=p;
Q.rear=p;
Q.rear->next=Q.front->next;
}

栈和队列的应用

知识点：

  • 栈的应用：表达式求值，中缀表达式，后缀表达式，递归，迷宫（DFS），进制转换。
  • 队列： 层次遍历（数的层次遍历），宽度遍历BFS,缓冲区，页面替换算法。

王道习题

1.括号匹配

bool OperatorCheck(char *a)
{
IniStack(S);
int i=0;
while(str[i]!='\0')
{
  switch(str[i])
  {
  case '(' :Push(S,'(') break;
  case '[' :Push(S,'[') break;
  case '{' :Push(S,'{') break;
  case ')':Pop(S,e); if(e!='(')return false;
  case ']':Pop(S,e); if(e!='[')return false;
  case '}':Pop(S,e); if(e!='{')return false;
  }
i++;
}
return Empty(S)?true:false;
}

2.没看懂题什么意思。
太抽象了，应该可以等价于字符串排序。

bool Train(char*str)
{
char *p=str,q=str;
InitStack(S);
while(p!=null)
{
  if(*p=='H')Push(S,p);
  else if(P=='S') {*(q++)=p;}
  else{return false;}
  p++;
}
while(!Empty(S))
{
  Pop(S,c);
  *q++=c;
}
return true;
}
  1. 递归函数
    不用栈（利用系统开的函数栈）
int fun1(int n,int x)
{
if(n==0)return 0;
if(n==1)return  2*x;
return 2*x(fun1(n-1,x))-2*(n-1,x);
}

用栈实现：

#Define Maxsize 1024；

typedef strct
{
int no;
float val;
}mystack[Maxsize];

float funP(int n,float x)
{
int top=0；
float out1=1,out2=2*x;
while(n-top>=2) { mystack[top].no=n-stack;top++; }
while(top>=0)
{
  mystack[top].val=2*x*out2-2*(mastack[top.no]*out1);
  out1=out2;
  out2=mystack[top].val;
  top--;
}
if(n==0)return out1;
else return out2;
}

上述代码的思路为：

  • 输入一个n阶函数，放入最底层，依次加上n-1阶，n-2阶。
  • 到了2阶和1阶时计算出结果，向下返回结果。
while(n-top>=2) { mystack[top].no=n-stack;top++; }

改为

for(int i=n;n>=2;i--){mystack[top++].no=i;}

更好理解

  1. 汽车轮渡口问题。
    该题无任何意义，条件讲的也不清楚，复习时千万不要看这破题浪费时间。
    题目要求：
  • 有一个进程A需要等待进程B和进程C
  • BC累计运行10次，A运行一次
  • BC分优先级
  • 若BC等待队列足够，B运行4次后进程C运行1次
  • 若B运行队列不足，用进程B代替
    代码:
qa,qc,qb 三个队列
void Manager()
{
  int i=0,j=0;
  while(j<=10)
{
    if(!Empty(qb)&&i++<4)
    {
      DeQueue(qb,x);
      EnQueue(qa,x);
    }
  if(!Empty(qc)&&i==4)
    {
      DeQueue(qc,x);
      EnQueue(qc,x);
      i=0;
      j++;
    }
  else if(Empty(qc)&&i==4)
    {
      while(!Empty(qb))
      {
        DeQueue(qb,x);
        EnQueue(qa,x);
        j++:
      }
  else if(Empty(qb)&&i++<4)
  {     
    DeQueue(qc,x);
    EnQueue(qa,x);
    j++:
  }
  else if(Empty(qb)&&Empty(qc)) { j=11; }
  }
}
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • [数据结构3.1]栈
    本章总览 栈（Stack）只允许在一端进行插入或删除操作的线性表。 栈的相关名词：入栈、出栈、栈顶、栈底、后进先出...
    魔术师_4146阅读 1,807评论 0赞 0
  • 数据结构-其他线性结构（栈和队列）
    大纲：*掌握栈的定义、栈的存贮结构及基本操作的实现。理解用栈实现表达式的求值，递归过程及实现。掌握队列的定义、存贮...
    堂前雪半阅读 3,973评论 0赞 0
  • 数据结构第四章 栈与队列
    4.2.1 栈的定义 栈是限定仅在表尾进行插入和删除操作的线性表 我们把允许插入和删除的一端称为栈顶，另一端称为栈...
    镜花水月阅读 1,826评论 0赞 0
  • 数据结构和算法三（栈和队列）
    栈 定义：栈是限定在表尾进行进行插入和删除操作的线性表 特点：允许插入和删除的一端叫做栈顶，另一端叫做栈底，不含任...
    小窦子阅读 3,427评论 0赞 1
  • 数据结构(三)栈和队列
    3.1 栈 3.1.1 栈的基本概念 栈是只允许在一端进行插入或删除的数据表 栈顶：允许插入和删除的一端 栈底：不...
    AdRainty阅读 3,003评论 0赞 1