数据结构-知识点栈和队列

点击查看python实现栈和队列单靠代码

1 栈

1.1 栈的基本概念

栈：受约束的线性表，只允许栈顶元素入栈和出栈。

1.2 栈的实现

存储：顺序栈 链式栈

操作： 入栈:先判栈满，elements[++top] = x; 出栈:先判栈空，x = elements[top—]; 判栈空：top=-1; 判栈满：top = maxsize - 1;

双栈共享一个栈空间

两个栈共享一个数组空间V[maxSize]设立栈顶指针数组 t[2] 和栈底指针数组 b[2]初始 t[0] = b[0] = -1, t[1] = b[1] = maxSize 栈满条件：t[0]+1 == t[1] //栈顶指针相遇栈空条件：t[0] = b[0]或t[1] = b[1] //退到栈底 t[i]和b[i]分别指示第 i个栈的栈顶与栈底

1.3 栈的应用

1.3.1 括号匹配

1.3.2 表达式求值

算术表达式的3种形式：前缀式、中缀式、后缀式 后缀表达式求值：可用栈解决。 具体执行过程： 当遇到数值的时候入栈，当遇到运算符的时候，连续两次出栈，将两个出栈元素结合运算符进行运算，先出栈的是第二个操作数（因为第二个操作数后入栈），将结果当成新遇到的数值入栈。如此往复，直到终止。此时栈底元素即为表达式的值。中缀表达式转后缀表达式

1.3.3 递归

三类递归：

定义递归数据结构递归问题解法是递归的

2.队列

2.1 基本概念

队列：受约束的线性表，只允许队尾进队，队头出队

2.2 实现

顺序队列

入队：q[rear++] = x; 出队:x = q[front++] 判队空:front == rear; 判队满:front - rear = maxsize

循环队列

队空：front == rear 队满：(rear+1)%maxsize == front

链式队列

2.3 队列应用

2.3.1 打印杨辉三角

2.3.2 优先级队列