数据结构栈和队列总结（数据结构-栈和队列）
数据结构栈和队列总结（数据结构-栈和队列）2.1压栈栈的基本运算顺序栈的基本运算的实现判栈空，置空栈，求元素个数算法容易实现，只要判断或改变s.top的值即可。下面仅给出进栈，出栈，取栈顶元素等函 数的算法实现。
任一表达式都可看成是由操作数，运算符和界限符组成的 一个串。其中，操作数可以是常数也可以是变量或常量的标识 符，运算符可以是算术运算符，关系运算符和逻辑运算符等，界限符包括左右括号和表达式结束符等，例表达式7 4*(8-3)。 计算机要完成表达式的求值，必须正确的解释表达式，将其翻译成正确的机器指令序列。要了解计算机的求值过程，必须先研究栈的性质。
1：栈的定义和基本运算
栈是限定只能在表尾进行插入和删除的线性表，并将表尾 称为栈顶，表头称为栈底。给出了非空栈s=(A B C D)的示意图。
由于限定只能在栈顶进行操作 所以栈中元素必按A B C D 次序进栈 按D C B A次序出栈 即按"后进先出"(或“先进后出") 的原则进行操作的。这一特点可用生活中的实例形象说明。例如每次只能容一个人进出的死胡同就相当一个栈，胡同口相当于栈顶，而胡同的另一端则为栈底。
栈的基本运算
顺序栈的基本运算的实现
判栈空，置空栈，求元素个数算法容易实现，只要判断或改变s.top的值即可。下面仅给出进栈，出栈，取栈顶元素等函 数的算法实现。
压栈
2.1
/*算法描述2-1*/
int Push(Stack S Datatype x)
{if (S.top==maxsize) {printf("overflow\n"); return(0);}
S.data[ S.top]=x; return(1);
2.2 出栈
/*算法描述2-2*/
int Pop(Stack s Datatype x) {if(S.top==0){printf("nudertflow\n");return(0)};
x=S.data[S.top]; S.top--; return(1);
}
2.3 取栈顶元素
/*算法描述2-3*/
int Gettop(Stack S Datatype x) {if(S.top==0){printf("nodata\N");return(0);}
x=S.data[top]; return(1); }
3 队列
队列的定义和运算
和栈相反，队列是一种“先进先出”的线性表。他只允许再表的一端(称表尾)插入元素，在表的另一端(表头)删除元素。队列和日常生活中的排队是一致的，最早进入队列的元素最早得到服务。
给出可队列示意图。
队列的操作与栈的操作类似，不同的是删除运算是在表头进行。
(1)判队空 EmptyQueue(Q) 若队列为空则返回“真“，否则返 回”假“;
入队将新元素插入到队尾。
(2) InQueue(Q x) x ;
(3)出队OutQueue(Q x) 若队列不空则返回队首的第一个元素元素，并从队列中删除该元素，否则返回NULL;
(4)置空队列InitQueue(Q) 将当队列设定为空队列;
(5)求元素个数 CurrentSize(Q) 返回当前队列中元素的个数 。
队列的存储结构及其算法实现
和栈类似，队列的顺序存储结构用一个向量来存储队列中 的元素，不过还需两个指针来指示队头元素和对尾元素在队列 中的当前位置。C语言描述如下:
# define maxsize N
typedef stuct
{Datatype adta[maxsize 1];
int front rear; } Queue;
3.1 顺序队列的基本运算
(1)判队空
/*算法描述3-1*/
int EmptyQueue(Queue Q)
{if (Q.front==Q.rear) return(1); else return(0);}
3.2
入队 /*算法描述3.2*/
int InQueue(Queue Q Datatype x)
{if (Q.rear==maxsize) {printf("overflow!"); return(0);}
Q.rear ;
Q.data[Q.rear]=x; return(1);}
3.3 出队
/*算法描述3-3*/
int OutQueue(Queue Q Datatype x) {if(EmptyQueue(Q)){printf("underflow!"); return(0);}
x=Q.data[Q.front 1];
Q.front ; if(EmptyQueue(Q)){Q.front=0; Q.rear=0} return(1);}
了解以上基本简单运算即可，具体事例可以是计算一个数学公式即可，根据计算优先级依次用栈实现，详细代码这里不列入。
以上，了解数据结构语法～
