阅读量:0
栈&队列-OJ
1.给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
(1).左括号必须用相同类型的右括号闭合。
(2).左括号必须以正确的顺序闭合。
(3).每个右括号都有一个对应的相同类型的左括号。
//1.栈和队列OJ题:括号匹配问题 #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdbool.h> #include <assert.h> #include <stdlib.h> typedef char STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; void StackInit(ST* ps); void StackDestory(ST* ps); void StackPush(ST* ps, STDataType x);// 入栈 void StackPop(ST* ps);// 出栈 STDataType StackTop(ST* ps); int StackSize(ST* ps); bool StackEmpty(ST* ps); void StackInit(ST* ps) { assert(ps); ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { printf("malloc fail\n"); exit(-1); } ps->capacity = 4; ps->top = 0; } void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } // 入栈 void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity)//判断空间是否够用，不够就要增容 { STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { ps->a = tmp; ps->capacity *= 2; } } ps->a[ps->top] = x; ps->top++; } // 出栈 void StackPop(ST* ps) { assert(ps); // 栈空了，调用Pop，直接中止程序报错 assert(ps->top > 0); //ps->a[ps->top - 1] = 0; ps->top--; } STDataType StackTop(ST* ps) { assert(ps); // 栈空了，调用Top，直接中止程序报错 assert(ps->top > 0); return ps->a[ps->top - 1]; } int StackSize(ST* ps) { assert(ps); return ps->top; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } bool isValid(char* s)//判断符号 { if (*s == ')' || *s == '}' || *s == ']') { return false;//匹配失败 } //struct Stack st; //上面对struct Stack进行了重命名(line11) typedef struct Stack ST ST st;//创建 栈 StackInit(&st); while (*s != '\0') { switch (*s) { case '(': case '{': case '[': { StackPush(&st, *s); s++; break; } case ')': case '}': case ']': { if (StackEmpty(&st)) { StackDestory(&st); return false; } char top = StackTop(&st); StackPop(&st); if (top != '(' && *s == ')' || top != '{' && *s == '}' || top != '[' && *s == ']') { StackDestory(&st); return false;//匹配失败 } else { s++; break; } } default: break; } } bool over = StackEmpty(&st); StackDestory(&st); return over; } bool isValid0(char* s) { ST st; StackInit(&st); while (*s != '\0') { switch (*s) { case '{': case '[': case '(': { StackPush(&st, *s); ++s; break; } case '}': case ']': case ')': { if (StackEmpty(&st)) { StackDestory(&st); return false; } char top = StackTop(&st); StackPop(&st); // 不匹配 if ((*s == '}' && top != '{') || (*s == ']' && top != '[') || (*s == ')' && top != '(')) { StackDestory(&st); return false; } else // 匹配 { ++s; } break; } default: break; } } bool ret = StackEmpty(&st); StackDestory(&st); return ret; } int main() { printf("%d\n", isValid("))")); printf("%d\n", isValid("(){}[]")); return 0; } 2.请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现
MyStack类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
//2.栈和队列OJ题:用队列实现栈 #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue; void QueueInit(Queue* pq)//初始化队列 { assert(pq); pq->head = pq->tail = NULL; } void QueueDestory(Queue* pq)//销毁队列 { assert(pq); QNode *cur= pq->head; while (cur) { QNode* temp = cur->next; free(cur); cur = temp; } pq->head = pq->tail = NULL; } void PrintQueue(Queue* pq)//打印队列数据 { assert(pq); QNode* cur = pq->head; while (cur) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } QNode* Buynode(QDataType x)//申请节点 { QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(1); } newnode->data = x; newnode->next = NULL; } void QueuePush(Queue* pq, QDataType x)//队尾插入数据（队尾进） { assert(pq); if (pq->head == NULL) { pq->head = pq->tail = Buynode(x); } else { pq->tail->next = Buynode(x); pq->tail = pq->tail->next; } } void QueuePop(Queue* pq)//队头删除数据（队头出） { assert(pq); if (pq->head == pq->tail) { free(pq->head); pq->head = pq->tail=NULL; } else { QNode* temp = pq->head->next; free(pq->head); pq->head = temp; } } bool QueueEmpty(Queue* pq)//判断队列是否为空 { assert(pq); return pq->head == NULL; } size_t QueueSize(Queue* pq)//队列的长度 { assert(pq); size_t size = 0; QNode* cur = pq->head; while (cur) { size++; cur = cur->next; } return size; } QDataType QueueFront(Queue* pq)//输出队头的数据值 { assert(pq); assert(pq->head); return pq->head->data; } QDataType QueueBack(Queue* pq)//输出队尾的数据值 { assert(pq); assert(pq->tail); return pq->tail->data; } typedef struct { Queue q1; Queue q2; }MyStack; MyStack* myStackCreate()//创建一个栈 { MyStack* ps = (MyStack*)malloc(sizeof(MyStack)); if (ps == NULL) { perror("malloc fail\n!"); exit(-1); } QueueInit(&ps->q1); QueueInit(&ps->q2); return ps; } void myStackPush(MyStack* obj, QDataType x)//(入栈) { if (!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); } else { QueuePush(&obj->q2, x); } } int myStackPop(MyStack* obj)//删除栈顶数据 (出栈) { //假设obj->q1 指向的队列是空的；obj->q2 指向的队列不是空的；但确定肯定一个是空的，一个非空 Queue* empty = &obj->q1; Queue* noempty = &obj->q2; //如果上方假设失败，进行转换，obj->q2 指向的队列是空的；obj->q1 指向的队列是非空的； if (!QueueEmpty(&obj->q1)) { empty = &obj->q2; noempty = &obj->q1; } //数据倒换 while (QueueSize(noempty)>1) { QDataType head = QueueFront(noempty); QueuePush(empty, head); QueuePop(noempty); } //剩下最后一个数据了 QDataType top = QueueFront(noempty); QueuePop(noempty); return top; } QDataType myStackTop(MyStack* obj)//返回栈顶数据 { if (!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); } } bool myStackEmpty(MyStack* obj)//判断栈是否为空 { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj)//栈销毁 { QueueDestory(&obj->q1); QueueDestory(&obj->q2); free(obj); obj = NULL; } int main() { MyStack* st = myStackCreate(); myStackPush(st, 1); myStackPush(st, 2); myStackPush(st, 3);//入栈 myStackPop(st);//出栈 printf("%d \n", myStackTop(st));//返回栈顶数据 myStackFree(st);//销毁栈 return 0; }