栈和队列的共同特点是 （ ）
栈：是限制在表的一端进行插入和删除运算的线性表。
栈又称后进先出简称：表队列：也是一种运算受限的线性表。
它只允许在标的一端进行插入，而在另一端进行删除。
队列亦称：先进先出表所以：共同点是：C
栈和队列数据结构的特点,什么情况下用到栈,什么情况下用到队列(各举3个例子)
栈：特点就是一个先进后出的结构。
队列：特点就是一个先进先出的结构。
\\\/\\\/一般只要你满足这个特点就可以称之为栈或队列。
栈的应用：非常广泛，在CPU内部就有提供栈这个机制。
主要用途：函数调用和返回，数字转字符，表达式求值，走迷宫等等。
在CPU内部栈主要是用来进行子程序调用和返回，中断时数据保存和返回。
在编程语言中：主要用来进行函数的调用和返回。
可以说在计算机中，只要数据的保存满足先进后出的原理，都优先考虑使用栈，所以栈是计算机中不可缺的机制。
队列的应用：队列主要用在和时间有关的地方，特别是操作系统中，队列是实现多任务的重要机制。
windows中的消息机制就是通过队列来实现的。
进程调度也是使用队列来实现，所以队列也是一个重要的机制。
只要满足数据的先进先出原理就可以使用队列。
栈和队列的作用是什么?它们主要可以应用在哪些方面?
栈和队列的作用是排队作用，可以应用在排队类型的数据处理上，例如网络请求回复之类的
用两个栈实现一个队列的功能
要求给出算法和思路
举例说明，假设我们进行以下4步：push 1, 2pop \\\/\\\/此时应pop 1push 3pop \\\/\\\/此时应pop 2在运行第一个pop时，把A中的1,2全push到B中去，然后再pop得到1，此时B中还剩一个2下一步push 3，是push到A中最后一步pop，把B中的2给pop出去关键点：(2)如果不为空，则将栈A中所有元素依次pop出并push到栈B；这里隐含了一点，如果为空，就直接从B中pop，不对A进行任何操作。
很显然，需要if..else语句。
弹栈和一般的出栈不同，需要多一部检测B是否为空。
如果B不为空，则直接从B出栈，这时与一般的出栈相同。
如果B为空，则需要把A中所有的元素出栈并压栈到B中去，然后再对B进行一般的出栈操作。
求救：栈和队列在程序设计中的作用
栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。
栈和队列被广泛应用于各种程序设计中。
栈的定义及基本运算1、栈的定义栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
(2)当表中没有元素时称为空栈。
(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO 表。
栈的修改是按后进先出的原则进行。
每次删除（退栈）的总是当前栈中最新的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。
【示例】元素是以a1，a2，…，an 的顺序进栈，退栈的次序却是an，an-1，…，a1。
2、栈的基本运算（1）InitStack（S）构造一个空栈S。
（2）StackEmpty（S）判栈空。
若S 为空栈，则返回TRUE，否则返回FALSE。
（3）StackFull（S）判栈满。
若S 为满栈，则返回TRUE，否则返回FALSE。
注意：该运算只适用于栈的顺序存储结构。
（4）Push（S，x）进栈。
若栈S 不满，则将元素x 插入S 的栈顶。
（5）Pop（S）退栈。
若栈S 非空，则将S 的栈顶元素删去，并返回该元素。
（6）StackTop（S）取栈顶元素。
若栈S 非空，则返回栈顶元素，但不改变栈的状态。
顺序栈栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
1、顺序栈的类型定义#define StackSize 100 \\\/\\\/假定预分配的栈空间最多为100 个元素typedef char DataType;\\\/\\\/假定栈元素的数据类型为字符typedef struct{DataType data[StackSize];int top;}SeqStack;注意：①顺序栈中元素用向量存放②栈底位置是固定不变的，可设置在向量两端的任意一个端点③栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top 为栈顶指针）来指示当前栈顶位置2、顺序栈的基本操作前提条件：设S 是SeqStack 类型的指针变量。
若栈底位置在向量的低端，即S-＞data[0]是栈底元素。
（1） 进栈操作进栈时，需要将S-＞top 加1注意：①S-＞top==StackSize-1 表示栈满②上溢现象--当栈满时，再做进栈运算产生空间溢出的现象。
上溢是一种出错状态，应设法避免。
（2） 退栈操作退栈时，需将S-＞top 减1注意：①S-＞top<0 表示空栈②下溢现象——当栈空时，做退栈运算产生的溢出现象。
下溢是正常现象，常用作程序控制转移的条件。
顺序栈在进栈和退栈操作时的具体变化情况【参见动画演示】3、顺序栈的基本运算（1） 置栈空void InitStack（SeqStack *S）{\\\/\\\/将顺序栈置空S->top=-1;}（2） 判栈空int StackEmpty（SeqStack *S）{return S->top==-1;}（3） 判栈满int StackFull（SeqStack *SS）{return S->top==StackSize-1;}（4） 进栈void Push（S，x）{if (StackFull(S))Error(Stack overflow); \\\/\\\/上溢，退出运行S->data[++S->top]=x;\\\/\\\/栈顶指针加1 后将x 入栈}（5） 退栈DataType Pop（S）{if(StackEmpty(S))Error(Stack underflow); \\\/\\\/下溢，退出运行return S->data[S->top--];\\\/\\\/栈顶元素返回后将栈顶指针减1}（6） 取栈顶元素DataType StackTop（S）{if(StackEmpty(S))Error(Stack is empty);return S->data[S->top];}4、两个栈共享同一存储空间当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。
当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。
只有当整个向量空间被两个栈占满（即两个栈顶相遇）时，才会发生上溢。
因此，两个栈共享一个长度为m 的向量空间和两个栈分别占用两个长度为└ m\\\/2┘和┌m\\\/2┐的向量空间比较，前者发生上溢的概率比后者要小得多。
链栈栈的链式存储结构称为链栈。
1、链栈的类型定义链栈是没有附加头结点的运算受限的单链表。
栈顶指针就是链表的头指针。
链栈的类型说明如下：typedef struct stacknode{DataType datastruct stacknode *next}StackNode;typedef struct{StackNode *top; \\\/\\\/栈顶指针}LinkStack;注意：①LinkStack 结构类型的定义是为了方便在函数体中修改top 指针本身②若要记录栈中元素个数，可将元素个数属性放在LinkStack 类型中定义。
2、链栈的基本运算（1） 置栈空Void InitStack(LinkStack *S){S->top=NULL;}（2） 判栈空int StackEmpty(LinkStack *S){return S->top==NULL;}（3） 进栈void Push(LinkStack *S,DataType x){\\\/\\\/将元素x 插入链栈头部StackNode *p=(StackNode *)malloc(sizeof(StackNode));p->data=x;p->next=S->top;\\\/\\\/将新结点*p 插入链栈头部S->top=p;}（4） 退栈DataType Pop(LinkStack *S){DataType x;StackNode *p=S->top;\\\/\\\/保存栈顶指针if(StackEmpty(S))Error(Stack underflow.); \\\/\\\/下溢x=p->data; \\\/\\\/保存栈顶结点数据S->top=p->next; \\\/\\\/将栈顶结点从链上摘下free(p);return x;}（5） 取栈顶元素DataType StackTop(LinkStack *S){if(StackEmpty(S))Error(Stack is empty.)return S->top->data;}注意：链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义StackFull 运算。
-------------------------------------------------------------------------------------------------------------队列的定义及基本运算1、定义队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表（1）允许删除的一端称为队头（Front）。
（2）允许插入的一端称为队尾（Rear）。
（3）当队列中没有元素时称为空队列。
（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO 表。
队列的修改是依先进先出的原则进行的。
新来的成员总是加入队尾（即不允许加塞），每次离开的成员总是队列头上的（不允许中途离队），即当前最老的成员离队。
【例】在队列中依次加入元素a1，a2，… ，an 之后，a1 是队头元素，an 是队尾元素。
退出队列的次序只能是a1，a2，… ，an。
2、队列的基本逻辑运算（1）InitQueue（Q）置空队。
构造一个空队列Q。
（2）QueueEmpty（Q）判队空。
若队列Q 为空，则返回真值，否则返回假值。
（3） QueueFull（Q）判队满。
若队列Q 为满，则返回真值，否则返回假值。
注意：此操作只适用于队列的顺序存储结构。
（4） EnQueue（Q，x）若队列Q 非满，则将元素x 插入Q 的队尾。
此操作简称入队。
（5） DeQueue（Q）若队列Q 非空，则删去Q 的队头元素，并返回该元素。
此操作简称出队。
（6） QueueFront（Q）若队列Q 非空，则返回队头元素，但不改变队列Q 的状态。
顺序队列1、顺序队列（1）顺序队列的定义队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
（2） 顺序队列的表示①和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。
②由于队列的队头和队尾的位置是变化的，设置两个指针front 和rear 分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为0。
（3） 顺序队列的基本操作①入队时：将新元素插入rear 所指的位置，然后将rear 加1。
②出队时：删去front 所指的元素，然后将front 加1 并返回被删元素。
注意：①当头尾指针相等时，队列为空。
②在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。
顺序队列基本操作【参见动画演示】（4）顺序队列中的溢出现象① 下溢现象当队列为空时，做出队运算产生的溢出现象。
“下溢”是正常现象，常用作程序控制转移的条件。
② 真上溢现象当队列满时，做进栈运算产生空间溢出的现象。
“真上溢”是一种出错状态，应设法避免。
③ 假上溢现象由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。
当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。
该现象称为假上溢现象。
【例】假设下述操作序列作用在初始为空的顺序队列上：EnQueue，DeQueue，EnQueue，DeQueue，…尽管在任何时刻，队列元素的个数均不超过1，但是只要该序列足够长，事先定义的向量空间无论多大均会产生指针越界错误。
链队列1、链队列的定义队列的链式存储结构简称为链队列。
它是限制仅在表头删除和表尾插入的单链表。
2、链队列的结构类型说明注意：增加指向链表上的最后一个结点的尾指针，便于在表尾做插入操作。
链队列示意图见上图，图中Q 为LinkQueue 型的指针。
3、链队列的基本运算（1） 置空队void InitQueue(LinkQueue *Q){Q->front=Q->rear=NULL;}（2） 判队空intQueueEmpty(LinkQueue *Q){return Q->front==NULL&&Q->rear==Null;\\\/\\\/实际上只须判断队头指针是否为空即可}（3） 入队void EnQueue(LinkQueue *Q,DataType x){\\\/\\\/将元素x 插入链队列尾部QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));\\\/\\\/申请新结点p->data=x; p->next=NULL;if(QueueEmpty(Q))Q->front=Q->rear=p; \\\/\\\/将x 插入空队列else { \\\/\\\/x 插入非空队列的尾Q->rear->next=p; \\\/\\\/*p 链到原队尾结点后Q->rear=p; \\\/\\\/队尾指针指向新的尾}}（4） 出队DataType DeQueue (LinkQueue *Q){DataType x;QueueNode *p;if(QueueEmpty(Q))Error(Queue underflow);\\\/\\\/下溢p=Q->front; \\\/\\\/指向对头结点x=p->data; \\\/\\\/保存对头结点的数据Q->front=p->next; \\\/\\\/将对头结点从链上摘下if(Q->rear==p)\\\/\\\/原队中只有一个结点，删去后队列变空，此时队头指针已为空Q->rear=NULL;free(p); \\\/\\\/释放被删队头结点return x; \\\/\\\/返回原队头数据}（5） 取队头元素DataType QueueFront(LinkQueue *Q){if(QueueEmpty(Q))Error(Queue if empty.);return Q->front->data;}注意：①和链栈类似，无须考虑判队满的运算及上溢。
②在出队算法中，一般只需修改队头指针。
但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。
③以上讨论的是无头结点链队列的基本运算。
和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，增加头结点的链队列的基本运算【参见练习】循环队列为充分利用向量空间，克服假上溢现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。
存储在其中的队列称为循环队列（Circular Queue）。
（1） 循环队列的基本操作循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。
只不过当头尾指针指向向量上界（QueueSize-1）时，其加1 操作的结果是指向向量的下界0。
这种循环意义下的加1 操作可以描述为：① 方法一：if(i+1==QueueSize) \\\/\\\/i 表示front 或reari=0;elsei++;② 方法二--利用模运算i=(i+1)%QueueSize；（2） 循环队列边界条件处理循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。
因此，无法通过条件front==rear 来判别队列是空还是满。
【参见动画演示】解决这个问题的方法至少有三种：① 另设一布尔变量以区别队列的空和满；② 少用一个元素的空间。
约定入队前，测试尾指针在循环意义下加1 后是否等于头指针，若相等则认为队满（注意：rear 所指的单元始终为空）；③使用一个计数器记录队列中元素的总数（即队列长度）。
（3） 循环队列的类型定义#define Queur Size 100 \\\/\\\/应根据具体情况定义该值typedef char Queue DataType; \\\/\\\/DataType 的类型依赖于具体的应用typedef Sturet{ \\\/\\\/头指针，队非空时指向队头元素int front; \\\/\\\/尾指针，队非空时指向队尾元素的下一位置int rear; \\\/\\\/计数器，记录队中元素总数DataType data[QueueSize]}CirQueue;（4） 循环队列的基本运算用第三种方法，循环队列的六种基本运算：① 置队空void InitQueue(CirQueue *Q){Q->front=Q->rear=0;Q->count=0; \\\/\\\/计数器置0}② 判队空int QueueEmpty(CirQueue *Q){return Q->count==0; \\\/\\\/队列无元素为空}③ 判队满int QueueFull(CirQueue *Q){return Q->count==QueueSize; \\\/\\\/队中元素个数等于QueueSize 时队满}④ 入队void EnQueue(CirQueuq *Q,DataType x){if(QueueFull((Q))Error(Queue overflow); \\\/\\\/队满上溢Q->count ++; \\\/\\\/队列元素个数加1Q->data[Q->rear]=x; \\\/\\\/新元素插入队尾Q->rear=(Q->rear+1)%QueueSize; \\\/\\\/循环意义下将尾指针加1⑤ 出队DataType DeQueue(CirQueue *Q){DataType temp;if(QueueEmpty((Q))Error(Queue underflow); \\\/\\\/队空下溢temp=Q->data[Q->front];Q->count--; \\\/\\\/队列元素个数减1Q->front=(Q->front+1)&QueueSize; \\\/\\\/循环意义下的头指针加1return temp;}⑥取队头元素DataType QueueFront(CirQueue *Q){if(QueueEmpty(Q))Error(Queue if empty.);return Q->data[Q->front];}
栈和队列的操作特点分别是什么
1.队列先出，栈先进后出 2.对插入和删除操限定。
栈是限能在表的一端进行插入和删除操作的线性表。
队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。
从数据结构的角度看，它们都是线性结构，即数据元素之间的关系相同。
但它们是完全不同的数据类型。
除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的限定。
栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按后进先出的规则进行操作，而队列必须按先进先出的规则进行操作。
和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。
3.遍历数据速度不同。
栈只能从头部取数据 也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性队列怎不同，他基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像数据结构，速度要快的多栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。
队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。
从数据结构的角度看，它们都是线性结构，即数据元素之间的关系相同。
但它们是完全不同的数据类型。
除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的限定。
栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按后进先出的规则进行操作，而队列必须按先进先出的规则进行操作。
和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。
可将线性表和栈及队列的插入和删除操作对比如下：栈 Insert(L,n+1,x) Delete(L,n) 而栈只允许在表尾一端进行插入和删除队列 Insert(L,n+1,x) Delete(L,1) 队列只允许在表尾一端进行插入，在表头一端进行删除
栈和队列的区别，以及如何区分是先进先出还是先进后出
队列的操作主要有：入队，出队，返回队列长度，返回队首元素，判断队列是否为空。
代码实现如下所示： #include
