考研笔记整理~🥝🥝
之前的博文链接在此：数据结构03：栈、队列和数组_-CSDN博客~🥝🥝
本篇作为链表的代码补充，供小伙伴们参考~🥝🥝
- 第1版：王道书的课后习题~🧩🧩
编辑：梅头脑🌸
参考用书：王道考研《2025年 数据结构考研复习指导》
目录
🧵01 出栈序列
🧵02 出栈序列
🧵03 出栈序列
🧵04 判断单链表对称
🧵05 共享栈
🔚结语
🧵01 出栈序列
🧩题目
有5个元素，其入栈次序为A,B,C,D,E，在各种可能的出栈次序中，第一个出栈元素.为C且第二个出栈元素为 D的出栈序列有哪几个?
📇解题思路
ABC 已在栈中，C出栈，D入栈再出栈满足要求。
此时，E未入栈，AB已在栈中。
1 BA出栈，E入栈出栈，CDBAE；
2 B出栈，E入栈出栈，A出栈，CDBEA；
3 E入栈，BA出栈，CDEBA。
共3种出栈序列。
🧵02 出栈序列
🧩题目
若元素的进栈序列为 A,B,C,D,E,运用栈操作,能否得到出栈序列 B,C,A,E,D和 D,B,A,C,E?为什么?
📇解题思路
BCAED：
1 ABC入栈，BCA出栈；
2 DE入栈，ED出栈；
可以得到出栈序列。
DBACE：
1 ABCD入栈，D出栈；
2 接下来，只可能是C出栈或者E入栈出栈，不可能以B出栈；
不能得到出栈序列。
🧵03 出栈序列
🧩题目
栈的初态和终态均为空，以I和0分别表示入栈和出栈，则出入栈的操作序列可表示为由I和O组成的序列，可以操作的序列称为合法序列，否则称为非法序列。
1)下面所示的序列中哪些是合法的?
A.IOIIOIOO B.IOOIOIOC.IIOIOIOD.IIOOIOO
2)通过对 1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回 false(假定被判定的操作序列已存入一维数组中)。
📇解题思路
A 合法；
B 非法，执行到第2个O时，栈内并没有可以出栈的元素；
C 非法，可以正常完成入栈和出栈操作，但是最后一步完成后栈内还剩2个元素；
D 合法；
⌨️解题代码
- 时间复杂度：O(n)：每次判断序列，遍历1轮单链表；
- 空间复杂度：O(1)：仅使用常数个指针；
#include <iostream>
#include <vector>
using namespace std;
bool Legal_Sequences(vector<char>& seq) {
if (seq.size() == 0) {
cout << "栈是空的哟~";
return false;
}
int input = 0;
int output = 0;
for (char c : seq) {
if (c != 'I' && c != 'O') {
cout << "奇怪的操作增加了~";
return false;
}
if (c == 'I') input++;
if (c == 'O') {
output++;
if (input < output) {
cout << "栈里面一个元素也没有啦~";
return false;
}
}
}
if (input != output) {
cout << "栈里面还有元素没出栈哟~";
return false;
}
cout << "这是一个合法序列~";
return true;
}
int main() {
vector<char> seq1 = { 'I', 'O', 'I', 'I', 'O', 'I', 'O', 'O' };
vector<char> seq2 = { 'I', 'O', 'O', 'I', 'O', 'I', 'I', 'O' };
vector<char> seq3 = { 'I', 'I', 'I', 'O', 'I', 'O', 'I', 'O' };
vector<char> seq4 = { 'I', 'I', 'I', 'O', 'O', 'I', 'O', 'O' };
cout << "sq1的判断结果:";
cout << Legal_Sequences(seq1) << endl;
cout << "sq2的判断结果:";
cout << Legal_Sequences(seq2) << endl;
cout << "sq3的判断结果:";
cout << Legal_Sequences(seq3) << endl;
cout << "sq4的判断结果:";
cout << Legal_Sequences(seq4) << endl;
return 0;
}
🧵04 判断单链表对称
🧩题目
设单链表的表头指针为L，结点结构由 data和 next 两个域构成，其中 dala域为字符型试设计算法判断该链表的全部n个字符是否中心对称。例如 xyx，xyyx 都是中心对称。
📇算法思路
- 算法思想：
- 创建栈，指针从前向后逐个遍历链表节点，依次入栈；
- 指针回到原点，并且与栈顶元素比较；
- 如果，该节点的绝对值与栈顶元素相同，指针后移，栈顶元素出栈；
- 否则，该链表的不是对称链表；
- 时间复杂度：O(n)，其中 n 为链表的长度。遍历链表2次，栈1次；
- 空间复杂度：O(n)，其中 n 为链表的长度。使用了一个栈记录链表的逆序遍历。
⌨️算法代码
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
typedef struct LNode {
char data;
struct LNode* next;
LNode(char x) : data(x), next(nullptr) {}
}LNode, * LinkList;
LinkList Create_List(vector<char>& vec) {
LinkList L = new LNode(vec[0]);
LNode* p = L;
for (int i = 1; i < vec.size(); i++) {
p->next = new LNode(vec[i]);
p = p->next;
}
return L;
}
bool Symmetrical_linked_lists(LinkList L) {
stack<char> s;
LNode* p = L;
while (p) {
s.push(p->data);
p = p->next;
}
p = L;
while (p) {
if (p->data != s.top()) {
return false;
}
s.pop();
p = p->next;
}
return true;
}
int main() {
vector<char> vec = { 'x', 'y', 'x' };
//vector<char> vec = { 'x', 'y', 'y', 'x'};
//vector<char> vec = { 'x', 'y', 'z' };
//vector<char> vec = { 'x', 'y', 'z', 'x' };
LinkList L = Create_List(vec);
bool result = Symmetrical_linked_lists(L);
if (result == true) {
cout << "这个单链表是对称的~" << endl;
}
else {
cout << "这个单链表不是对称的~" << endl;
}
return 0;
}
🧵05 共享栈
🧩题目
设有两个栈S1、S2 都采用顺序栈方式，并共享一个存储区[0,.,maxsize-1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式。试设计 S1、S2有关入栈和出栈的操作算法。
📇解题思路
既然已经决定使用同一个数组存储区了，可以把两个栈存在同一个数组中。除去通过指针的移动判断栈空栈满外，也要注意两个栈指针不要相互重叠...呃，除此之外其实也没别的了吧...
⌨️算法代码
#include <iostream>
#include <stack>
using namespace std;
const int MAXSIZE = 5;
class SharedStacks {
private:
int data[MAXSIZE];
int top1;
int top2;
public:
SharedStacks() {
top1 = -1;
top2 = MAXSIZE;
}
bool s_restspace();
bool s_empty(int stacklist);
bool s_push(int stacklist, int inputnumber);
bool s_pop(int stacklist);
bool s_top(int stacklist);
};
bool SharedStacks::s_restspace() {
if (top2 - top1 > MAXSIZE + 1 || top2 <= top1 + 1) {
cout << "共享栈已满，无法入栈" << endl;
return false;
}
if (top1 == MAXSIZE - 1) {
cout << "栈1已满" << endl;
return false;
}
if (top2 == 0) {
cout << "栈2已满" << endl;
return false;
}
return true;
}
bool SharedStacks::s_empty(int stacklist) {
if (stacklist == 1) {
if (top1 == -1) {
cout << "栈1为空" << endl;
return true;
}
cout << "栈1不为空" << endl;
return false;
}
if (stacklist == 2) {
if (top2 == MAXSIZE) {
cout << "栈2为空" << endl;
return true;
}
cout << "栈2不为空" << endl;
return false;
}
cout << "栈号输入错误" << endl;
return false;
}
bool SharedStacks::s_push(int stacklist, int inputnumber) {
if (s_restspace() == false) return false;
if (stacklist == 1) {
data[++top1] = inputnumber;
cout << "栈1入栈元素：" << inputnumber << endl;
return true;
}
if (stacklist == 2) {
data[--top2] = inputnumber;
cout << "栈2入栈元素：" << inputnumber << endl;
return true;
}
cout << "栈号输入错误" << endl;
return false;
}
bool SharedStacks::s_pop(int stacklist) {
if (s_top(stacklist) == false) return false;
if (stacklist == 1) {
top1--;
cout << "栈1栈顶元素已出栈" << endl;
return true;
}
if (stacklist == 2) {
top2++;
cout << "栈2栈顶元素已出栈" << endl;
return true;
}
cout << "栈号输入错误" << endl;
return false;
}
bool SharedStacks::s_top(int stacklist) {
if (s_empty(stacklist) == true) {
return false;
}
if (stacklist == 1) {
cout << "栈1栈顶元素：" << data[top1] << endl;
return true;
}
if (stacklist == 2) {
cout << "栈2栈顶元素：" << data[top2] << endl;
return true;
}
cout << "栈号输入错误" << endl;
return false;
}
int main() {
SharedStacks ss;
ss.s_empty(1);
ss.s_empty(2);
ss.s_push(1, 1);
ss.s_push(1, 2);
ss.s_push(1, 3);
ss.s_push(1, 4);
ss.s_push(1, 5);
ss.s_push(1, 6); // 此处共享栈已满，无法入栈
ss.s_pop(1);
ss.s_pop(1);
ss.s_push(2, 7);
ss.s_push(2, 8);
ss.s_push(2, 9); // 此处共享栈已满，无法入栈
ss.s_pop(1);
ss.s_pop(1);
ss.s_pop(1);
ss.s_pop(2);
ss.s_pop(2);
ss.s_top(1);
ss.s_top(2);
return 0;
}
📇备注
因为又又审错了题，我还写出过这样一个代码...如果仅固定空间大小，题目未声明使用同一个数组，两个栈各自操作我觉得也是极好的...
虽然没什么用，但是鉴于我这么菜想了很久的逻辑一些众所周知的原因，所以也厚脸皮地贴在这里留着自己看了...
#include <iostream>
#include <stack>
using namespace std;
const int MAXSIZE = 5;
class SharedStacks {
private:
stack<int> s1;
stack<int> s2;
int stacksize = MAXSIZE;
public:
SharedStacks() {
s1 = stack<int>();
s2 = stack<int>();
}
bool currentsize();
bool s1_empty() { return s1.empty(); }
bool s2_empty() { return s2.empty(); }
bool s1_push(int x);
bool s2_push(int x);
bool s1_pop();
bool s2_pop();
bool s1_top();
bool s2_top();
};
bool SharedStacks::currentsize() {
if (s1.size() + s2.size() >= stacksize) {
cout << "共享栈已满，无法入栈" << endl;
return false;
}
return true;
}
bool SharedStacks::s1_push(int x) {
if (currentsize() == false) return false;
s1.push(x);
cout << "栈1入栈元素：" << x << endl;
return true;
}
bool SharedStacks::s2_push(int x) {
if (currentsize() == false) return false;
s2.push(x);
cout << "栈2入栈元素：" << x << endl;
return true;
}
bool SharedStacks::s1_pop() {
if (s1_top() == false) return false;
s1.pop();
cout << "栈1栈顶元素已出栈" << endl;
return true;
}
bool SharedStacks::s2_pop() {
if (s2_top() == false) return false;
s2.pop();
cout << "栈2栈顶元素已出栈" << endl;
return true;
}
bool SharedStacks::s1_top() {
if (s1.empty() == true) {
cout << "栈1为空，无法取栈顶元素" << endl;
return false;
}
cout << "栈1栈顶元素：" << s1.top() << endl;
return true;
}
bool SharedStacks::s2_top() {
if (s2.empty() == true) {
cout << "栈2为空，无法取栈顶元素" << endl;
return false;
}
cout << "栈2栈顶元素：" << s2.top() << endl;
return true;
}
int main() {
SharedStacks ss;
ss.s1_empty();
ss.s2_empty();
ss.s1_push(1);
ss.s1_push(2);
ss.s1_push(3);
ss.s1_push(4);
ss.s1_push(5);
ss.s1_push(6); // 此处共享栈已满，无法入栈
ss.s1_pop();
ss.s1_pop();
ss.s2_push(7);
ss.s2_push(8);
ss.s2_push(9); // 此处共享栈已满，无法入栈
ss.s1_pop();
ss.s1_pop();
ss.s1_pop();
ss.s2_pop();
ss.s2_pop();
ss.s1_top();
ss.s2_top();
return 0;
}
🔚结语
博文到此结束，写得模糊或者有误之处，欢迎小伙伴留言讨论与批评，督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等，博主会顶锅前来修改~😶🌫️
我是梅头脑，本片博文若有帮助，欢迎小伙伴动动可爱的小手默默给个赞支持一下，收到点赞的话，博主肝文的动力++~🌟🌟
同系列的博文：🌸数据结构_梅头脑_的博客-CSDN博客
同博主的博文：🌸随笔03 笔记整理-CSDN博客
