栈的基本操作
如何通过栈这个后进先出的线性表，来实现增删查呢？初始时，栈内没有数据，即空栈。此时栈顶就是栈底。当存入数据时，最先放入的数据会进入栈底。接着加入的数据都会放入到栈顶的位置。如果要删除数据，也只能通过访问栈顶的数据并删除。对于栈的新增操作，通常也叫作 push 或压栈。对于栈的删除操作，通常也叫作 pop 或出栈。对于压栈和出栈，我们分别基于顺序栈和链栈进行讨论。
顺序栈
栈的顺序存储可以借助数组来实现。一般来说，会把数组的首元素存在栈底，最后一个元素放在栈顶。然后定义一个 top 指针来指示栈顶元素在数组中的位置。假设栈中只有一个数据元素，则 top = 0。一般以 top 是否为 -1 来判定是否为空栈。当定义了栈的最大容量为 StackSize 时，则栈顶 top 必须小于 StackSize。
链栈
关于链式栈，就是用链表的方式对栈的表示。通常，可以把栈顶放在单链表的头部，如下图所示。由于链栈的后进先出，原来的头指针就显得毫无作用了。因此，对于链栈来说，是不需要头指针的。相反，它需要增加指向栈顶的 top 指针，这是压栈和出栈操作的重要支持。
栈的案例
例 1，给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须与相同类型的右括号匹配，左括号必须以正确的顺序匹配。例如，{ [ ( ) ( ) ] } 是合法的，而 { ( [ ) ] } 是非法的。
具体为，从左到右顺序遍历字符串。当出现左括号时，压栈。当出现右括号时，出栈。并且判断当前右括号，和被出栈的左括号是否是互相匹配的一对。如果不是，则字符串非法。当遍历完成之后，如果栈为空。则合法。如下图所示：
public static void main(String[] args) {
String s = "{[()()]}";
System.out.println(isLegal(s));
}
private static int isLeft(char c) {
if (c == '{' || c == '(' || c == '[') {
return 1;
} else {
return 2;
}
}
private static int isPair(char p, char curr) {
if ((p == '{' && curr == '}') || (p == '[' && curr == ']') || (p == '(' && curr == ')')) {
return 1;
} else {
return 0;
}
}
private static String isLegal(String s) {
Stack stack = new Stack();
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
if (isLeft(curr) == 1) {
stack.push(curr);
} else {
if (stack.empty()) {
return "非法";
}
char p = (char) stack.pop();
if (isPair(p, curr) == 0) {
return "非法";
}
}
}
if (stack.empty()) {
return "合法";
} else {
return "非法";
}
}例 2，浏览器的页面访问都包含了后退和前进功能，利用栈如何实现？
我们利用浏览器上网时，都会高频使用后退和前进的功能。比如，你按照顺序先后访问了 5 个页面，分别标记为 1、2、3、4、5。现在你不确定网页 5 是不是你要看的网页，需要回退到网页 3，则需要使用到两次后退的功能。假设回退后，你发现网页 4 有你需要的信息，那么就还需要再执行一次前进的操作。
为了支持前进、后退的功能，利用栈来记录用户历史访问网页的顺序信息是一个不错的选择。此时需要维护两个栈，分别用来支持后退和前进。当用户访问了一个新的页面，则对后退栈进行压栈操作。当用户后退了一个页面，则后退栈进行出栈，同时前进栈执行压栈。当用户前进了一个页面，则前进栈出栈，同时后退栈压栈。我们以用户按照 1、2、3、4、5、4、3、4 的浏览顺序为例，两个栈的数据存储过程，如下图所示：
队列
与线性表、栈一样，队列也存在这两种存储方式，即顺序队列和链式队列：
1) 顺序队列，依赖数组来实现，其中的数据在内存中也是顺序存储。
2) 而链式队列，则依赖链表来实现，其中的数据依赖每个结点的指针互联，在内存中并不是顺序存储。链式队列，实际上就是只能尾进头出的线性表的单链表。
为了实现一个有 k 个元素的顺序存储的队列，我们需要建立一个长度比 k 大的数组，以便把所有的队列元素存储在数组中。队列新增数据的操作，就是利用 rear 指针在队尾新增一个数据元素。这个过程不会影响其他数据，时间复杂度为 O(1)，状态如下图所示：当队列为空时，front 和 rear 都指向头结点，如下图所示：
循环队列的数据操作
此时，又会产生新的问题，即当队列为空时，有 front 指针和 rear 指针相等。而现在的队列是满的，同样有 front 指针和 rear 指针相等。那么怎样判断队列到底是空还是满呢？常用的方法是，设置一个标志变量 flag 来区别队列是空还是满。
链式队列的数据操作
我们再看一下链式队列的数据操作。链式队列就是一个单链表，同时增加了 front 指针和 rear 指针。链式队列和单链表一样，通常会增加一个头结点，并另 front 指针指向头结点。头结点不存储数据，只是用来辅助标识。
链式队列进行新增数据操作时，将拥有数值 X 的新结点 s 赋值给原队尾结点的后继，即 rear.next。然后把当前的 s 设置为队尾结点，指针 rear 指向 s。如下图所示：
队列的案例
我们来看一个关于用队列解决约瑟夫环问题。约瑟夫环是一个数学的应用问题，具体为，已知 n 个人（以编号 1，2，3...n 分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出列；他的下一个人又从 1 开始报数，数到 m 的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。这个问题的输入变量就是 n 和 m，即 n 个人和数到 m 的出列的人。输出的结果，就是 n 个人出列的顺序。
这个问题，用队列的方法实现是个不错的选择。它的结果就是出列的顺序，恰好满足队列对处理顺序敏感的前提。因此，求解方式也是基于队列的先进先出原则。解法如下：
先把所有人都放入循环队列中。注意这个循环队列的长度要大于或者等于 n。
从第一个人开始依次出队列，出队列一次则计数变量 i 自增。如果 i 比 m 小，则还需要再入队列。
直到i等于 m 的人出队列时，就不用再让这个人进队列了。而是放入一个用来记录出队列顺序的数组中。
直到数完 n 个人为止。当队列为空时，则表示队列中的 n 个人都出队列了，这时结束队列循环，输出数组内记录的元素。
至此，我们就通过循环队列解决了约瑟夫环问题。代码如下：
public static void main(String[] args) {
ring(10, 5);
}
public static void ring(int n, int m) {
LinkedList<Integer> q = new LinkedList<Integer>();
for (int i = 1; i <= n; i++) {
q.add(i);
}
int k = 2;
int element = 0;
int i = 0;
for (; i<k; i++) {
element = q.poll();
q.add(element);
}
i = 1;
while (q.size() > 0) {
element = q.poll();
if (i < m) {
q.add(element);
i++;
} else {
i = 1;
System.out.println(element);
}
}
}
参考了《拉钩网视频-重学数据结构》，仅供学习，如有侵权，请联系我
