栈&队列-OJ

1.给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

(1).左括号必须用相同类型的右括号闭合。

(2).左括号必须以正确的顺序闭合。

(3).每个右括号都有一个对应的相同类型的左括号。

//1.栈和队列OJ题:括号匹配问题  #define _CRT_SECURE_NO_WARNINGS 1  #include  #include  #include  #include    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   #include   #include   #include     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; }