首页 > 代码库 > 栈和队列的总结
栈和队列的总结
栈和队列的总结：
（有时候感觉自己掌握了，栈和队列，可是在写的时候会遇到不同的情况，就不会处理了，因此在这里进行总结下）。
栈：
栈是一端受限，一段允许进行操作的线性表。我自己理解时，会将它理解成一个装书的盒子。放书，取书，就是进行的操作。这个的特点就是，你放了一踏书，现在你想取书，你只能先把上面的书一个个取出来，即：先放的后取，后放的先取。放在栈上说，就是先进后出。
明白了栈的定义，现在要实际的实际，首先是它的逻辑结构：线性表。它是线性的。
现在是它的存储结构：最常采用的是顺序存储和链式存储（见好多书或资料都说的最常采用的是顺序存储和链式存储，百度了下不常见的没有找到）。其中顺序存储用数组，链式存储用链表。
顺序存储：
先进行分析下：首先要分配一个足够大的数组（这里就出现了一个问题，要是分配的空间小，就会出现溢出的情况，这是一个潜在的隐患，但是要是分配的太过大，又会出现浪费空间，这里要做好一个估计，所以呢，我还是喜欢链式存储，要多少就给多少，不用担心空间太小或浪费），现在有了这个数组，需要的还有，必须有个东西能一个控制一端不让操作(数组的前端从下标为0开始)，一端要进行增删，这样就可以说是具备了栈有的特点，不让操作的叫栈底，进行操作的是栈顶
栈的定义：(用的是顺序存储)
#define Max 100;
typedef int Datetype;
typedef struct
{
Datetype date[Max];
Int top; //控制栈顶
}SeqStack,*PseqStack;
完成了定义，就要进行对栈的各种操作：初始化，判空，进栈，出栈，得到栈顶元素，销毁栈…….
初始化：
PseqStack Init-SeqStack( )
{
PseqStack S;
S=(PseqStack)malloc(sizeof(SeqStack)); //头文件要包括stdilb.h
S->top=-1;
return S;
}
判空：
Int IsEmpyt(PseqStack S)
{
if(S->top==-1)
return 1;
else
return 0;
}
进栈：
int Push(PseqStack S,Datetype x)
{
If(S->top==Max-1)
return 0;
else
S->top++;
S->date[S->top]=x;
return 1;
}
出栈：
int Pop(PseqStack S,int *x)
{
if(isEmpty(PseqStack S)==1)
return 0;
else
{
*x=S->date[S->top];
S->top--;
return 1;
}
}
int GetTopdate(PseqStack S)
{
if(isEmpty(PseqStack S)==1)
return 0;
else
return S->date[s->top]
}
int Destroy(PseqStack *S)
{
if(*S)
{ free(s);
*S=NULL;
return 1;
}
return 0;
}
下面来看下链式存储：
控制入栈出栈的端口，栈顶一般是链表的头，第一个节点，栈底一般是最后一个节点。（可以避免顺序存储的溢出），同时节省空间，要多少，申请多少。链表的运用中同时要注意一旦申请了，最后要记得释放，不然会带来不可预计的后果。下面是链式存储的一些操作。
typedef struct Stacknode
{
int date;
struct Stacknode *next;
}slStacktype;
入栈：
Int push(slStacktype *top,int x)
{
slStacktype *p;
if((p=( slStacktype *)malloc(sizeof(slStacktype )))==NULL) //申请节点
return 0;
p->date=x;
p->next=top->next; //用的是头插法，top始终是栈顶。
top->next =p;
return 1;
}
出栈：
int pop(slStacktype *top)
{
slStacktype *p;
int x;
if(top->next==NULL)
return NULL;
p=top->next;
top->next=p->next; //删除节点，用x记录要删除的元素。
x=p->date;
free(p);
return x;
}
对我来说，栈和队列，其实很相似，只不过是控制的位置不同。
队列：是一种限定性的线性表。这样理解比较好，学生排队买饭。有什么特点呢？当然，你先来，就先打饭，先吃饭。抽象到队列上说，有队头，队尾，要想加入（入队），只能从队尾加，想走（出队），只能从队头走。即：先进先出。
和栈一样，它常见的两种存储是顺序存储和链式存储。
用顺序存储时，会遇到这样的情况，数组并没有满，却入不了队（假溢出），原因在于队头没有在数组的0下标处。
说下循环队列的操作吧。（理解取余）
定义：
typedef struct
{
int date[Max];
int rear; //控制队尾
int front；//控制队头
}CirQueue;
① 置队空
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==Max; //队中元素个数等于max时队满
}
④ 入队
void EnQueue(CirQueuq *Q,int x)
{
if(QueueFull((Q))
Error("Queue overflow"); //队满上溢
Q->count ++; //队列元素个数加1
Q->data[Q->rear]=x; //新元素插入队尾
Q->rear=(Q->rear+1)%Max; //循环意义下将尾指针加1
⑤ 出队
DataType DeQueue(CirQueue *Q)
{
int temp;
if(QueueEmpty((Q))
Error("Queue underflow"); //队空下溢
temp=Q->data[Q->front];
Q->count--; //队列元素个数减1
Q->front=(Q->front+1)%Max; //循环意义下的头指针加1
return temp;
}
⑥取队头元素
DataType QueueFront(CirQueue *Q)
{
if(QueueEmpty(Q))
Error("Queue if empty.");
return Q->data[Q->front];
}
By:暖暖
2014.11.19
栈和队列的总结