栈部分
判断栈的操作序列是否合法 (栈的初始状态和终止状态均为空) 若合法, 返回 true, 反之返回 false, 操作序列存入一维数组中 I 为入栈, O 为出栈
- bool validate(const char * a) {
- int Icnt = 0,
- Ocnt = 0;
- int i = 0;
- while (a[i] != '\0') {
- if (a[i] == 'I') {
- Icnt++;
- } else if (a[i] == 'O') {
- Ocnt++;
- }
- if (Ocnt > Icnt) return 0;
- i++;
- }
- if (Icnt != Ocnt) return 0;
- else return 1;
- }
判断单链表的前 n 个数字是否中心对称例如 121,1221 都是中心对称
- bool isSymetric(linkList l, int n) {
- stack < int > s;
- linkList p = l - >pNext;
- for (int i = 0; i < n / 2; i++) {
- s.push(p - >data);
- p = p - >pNext;
- }
- if (n % 2) p = p - >pNext;
- while (p && s.top() == p - >data && !s.empty()) {
- s.pop();
- if (s.empty()) break;
- p = p - >pNext;
- }
- if (s.empty()) return true;
- else return false;
- }
设有两个栈都采用顺序栈方式, 共享一个存储区,[0,maxsize - 1], 采用栈顶相向, 迎面增长的存储方式, 设计出栈和入栈等操作算法(为了验证, 把几乎所有操作都写了, 貌似代码不够鲁棒, 还希望大佬能看看哪里不太好)
- #define MAXSIZE 100 typedef struct {
- int data[MAXSIZE];
- int top1,
- top2;
- }
- Stack;
- void initStack(Stack & s) {
- s.top1 = -1;
- s.top2 = MAXSIZE;
- }
- bool isEmpty(int i, Stack & s) {
- if (i == 0 && s.top1 == -1) return true;
- else if (i == 1 && s.top2 == MAXSIZE) return true;
- else return false;
- }
- int top(int i, Stack & s) {
- if (isEmpty(i, s)) {
- cout << "栈为空" << endl;
- return 0;
- }
- if (i == 0) return s.data[s.top1];
- else if (i == 1) return s.data[s.top2];
- }
- void pop(int i, Stack & s) {
- if (isEmpty(i, s)) {
- cout << "栈为空, 无法弹出" << endl;
- return;
- }
- if (i == 0) {
- cout << "弹出值为" << s.data[s.top1] << endl;
- s.top1--;
- } else {
- cout << "弹出值为" << s.data[s.top2] << endl;
- s.top2++;
- }
- }
- void push(Stack & s, int i, int x) {
- if (i != 0 && i != 1) {
- cout << "栈号输入错误" << endl;
- }
- if (s.top2 - s.top1 == 1) {
- cout << "栈已满" << endl;
- return;
- }
- if (i == 0) {
- s.data[++s.top1] = x;
- return;
- } else {
- s.data[--s.top2] = x;
- return;
- }
- }
队列部分
自己实现一个循环队列, 支持队尾的 push 和 pop, 队头的 push 和 pop(双端队列)
- #include < iostream > #include < cstdio > #include < cstdlib > #include < algorithm > using namespace std;#define MAXSIZE 3 typedef struct {
- int data[MAXSIZE];
- int front,
- rear;
- }
- queue; // 做成循环队列那是相当好的 队空条件 front = rear 队满 (rear+1) % maxsize = front
- void initQueue(queue & q) {
- q.rear = q.front = 0;
- }
- bool isEmpty(queue & q) {
- if (q.rear == q.front) return true;
- return false;
- }
- void push_front(queue & q, int x) {
- if ((q.front - 1) % MAXSIZE == q.rear) {
- cout << "队列已满, 不可加入" << endl;
- return;
- }
- q.data[q.front] = x;
- q.front = (q.front - 1 + MAXSIZE) % MAXSIZE;
- cout << "加入元素 \"x=" << x << "\"成功!" << endl;
- }
- void push_back(queue & q, int x) {
- if ((q.rear + 1) % MAXSIZE == q.front) {
- cout << "队列已满, 不可加入" << endl;
- return;
- }
- q.data[q.rear] = x;
- q.rear = (q.rear + 1) % MAXSIZE;
- cout << "加入元素 \"x=" << x << "\"成功!" << endl;
- }
- void pop_back(queue & q) {
- //cout << q.rear <<" "<< q.front << endl;
- if (isEmpty(q)) {
- cout << "队列为空, 不可弹出" << endl;
- return;
- }
- //cout << q.rear << " " << q.front << endl;
- int x = q.data[q.rear - 1];
- //cout << "debug1:" << q.rear << endl;
- q.rear = (q.rear - 1 + MAXSIZE) % MAXSIZE;
- //cout << "debug2:" << q.rear << endl;
- cout << "弹出元素为" << x << "!" << endl;
- }
- void pop_front(queue & q) {
- if (isEmpty(q)) {
- cout << "队列为空, 不可弹出" << endl;
- return;
- }
- int x = q.data[(q.front + 1) % MAXSIZE];
- cout << "弹出元素为" << x << "!" << endl;
- q.front = (q.front + 1) % MAXSIZE;
- }
- int main() {
- ios: :sync_with_stdio(false);
- queue q;
- initQueue(q);
- push_back(q, 10);
- push_back(q, 10);
- pop_back(q);
- pop_back(q);
- cout << "front" << q.front << endl;
- cout << "rear" << q.rear << endl;
- push_front(q, 10);
- // cout << "front" << q.front << endl;
- //cout << "rear" << q.rear << endl;
- push_front(q, 2);
- pop_front(q);
- pop_front(q);
- system("pause");
- return 0;
- }
实现队列的链式存储结构
- #include < iostream > #include < cstdio > #include < cstdlib > #include < algorithm > using namespace std;
- typedef int elemType;
- typedef struct node {
- int data;
- struct node * next;
- }
- LinkNode;
- // 设置为带头结点的单链表
- typedef struct {
- LinkNode * front,
- *rear;
- }
- queue;
- void initQueue(queue & q) {
- q.front = (LinkNode * ) malloc(sizeof(LinkNode));
- q.rear = q.front;
- q.front - >next = nullptr;
- }
- bool isEmpty(queue q) {
- if (q.front == q.rear) return true;
- return false;
- }
- void enQueue(queue & q, elemType x) {
- LinkNode * temp = (LinkNode * ) malloc(sizeof(LinkNode));
- temp - >data = x;
- temp - >next = nullptr;
- q.rear - >next = temp;
- q.rear = temp;
- }
- elemType deQueue(queue & q) {
- if (isEmpty(q)) {
- cout << "队列为空" << endl;
- return 0;
- }
- LinkNode * temp = (LinkNode * ) malloc(sizeof(LinkNode));
- temp = q.front - >next;
- int x = temp - >data;
- q.front - >next = temp - >next;
- if (q.rear == temp) q.rear = q.front;
- free(temp);
- return x;
- }
- int main() {
- queue q;
- initQueue(q);
- enQueue(q, 10);
- enQueue(q, 9);
- enQueue(q, 11);
- enQueue(q, 12);
- cout << deQueue(q) << endl;
- cout << deQueue(q) << endl;
- cout << deQueue(q) << endl;
- cout << deQueue(q) << endl;
- system("pause");
- return 0;
- }
最适合做链队的链表是: 带队首指针和队尾指针的循环单链表
最不适合的: 只带队首指针的非循环链表
用链式存储方式的队列, 进行存储操作时, 头尾指针可能都要进行修改
利用一个栈, 将队列中的元素逆置
- void reverseQueue(queue < int > &q) {
- stack < int > s;
- while (!q.empty()) {
- s.push(q.front());
- q.pop();
- }
- while (!s.empty()) {
- q.push(s.top());
- s.pop();
- }
- }
利用两个栈来模拟一个队列
- class Solution
- {
- public:
- void push(int node) {
- while (!stack2.empty())
- {
- stack1.push(stack2.top());
- stack2.pop();
- }
- stack1.push(node);
- }
- int pop() {
- while (!stack1.empty())
- {
- stack2.push(stack1.top());
- stack1.pop();
- }
- int result = stack2.top();
- stack2.pop();
- return result;
- }
- private:
- stack<int> stack1;
- stack<int> stack2;
- };
来源: http://www.jianshu.com/p/e000badb5d0c