栈&队列-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 STST 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;
}
