栈和队列OJ题

有效括号问题：

题目描述：

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

思路：

解决此类问题，传统的暴力遍历法已经不再适用了，暴力遍历无法保证括号的匹配顺序，仅能通过统计左右括号的数量进行比较判断，但即使是左右括号数量相等，也不一定是有效的，如：“( [ { ] ) }”，虽然左右括号数量相同，但是它们的顺序不对，不能相互匹配，所以也是无效的，因此，暴力遍历的方法是不行的。

此时我们应该从问题本身出发，思考一下括号匹配的本质是什么？

我们知道一个合法的括号包括两部分：左括号和右括号，括号匹配就是匹配左右括号，并且每次匹配时都是相邻最近的两个左右括号进行匹配。因此，我们可以创建一个数组用来储存左括号，依次遍历，每出现一次左括号就存进这个数组中，每次出现右括号时，将它与数组中最后一个左括号进行匹配，若匹配成功，则删除数组最后一个左括号，再从下一个开始遍历；若匹配不成功，则说明是非法括号字符串，直接退出程序……直至遍历完括号字符串或者中间出现不匹配的情况直接退出。若正常遍历完括号字符串，再看数组中是否为空，若为空，说明该括号字符串中所有左右括号都匹配成功，即该括号字符串合法，反之则是非法的。观察这个匹配规律，不难发现与栈“先入后出”的特点相符合，因此我们可以直接创建一个栈进行实现。

具体代码如下：

typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;//栈顶int capacity;//容量
}ST;//判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
//初始化
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
//销毁
void STDestroy(ST* ps)
{free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
//入栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* p = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);ps->a = p;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}
//出栈
void STPop(ST* ps)
{assert(ps);assert(ps->a);assert(!STEmpty(ps));ps->top--;
}
//取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps->a);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}bool isValid(char * s)
{ST ps;STInit(&ps);int i=0;for(i=0;i<strlen(s);i++){if(s[i]=='('||s[i]=='{'||s[i]=='[')//左括号入栈{STPush(&ps,s[i]);}else//右括号与栈顶元素进行匹配{if(STEmpty(&ps))//栈中为空，说明括号数量不匹配{return false;}else if((STTop(&ps)=='('&&s[i]!=')')||(STTop(&ps)=='['&&s[i]!=']')||(STTop(&ps)=='{'&&s[i]!='}'))//栈中不为空，但括号样式不匹配{return false;}else//匹配成功，栈顶元素出栈{STPop(&ps);}}}if(STEmpty(&ps))//全部遍历完之后，栈中为空，说明全部匹配成功{return true;}else//栈中不为空，说明数量不匹配{return false;}STDestroy(&ps);
}

 运行结果：

用栈实现队列：

题目描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

 首先要知道栈的特点是“先入后出”，因为此特点，把栈1中的数据移动到栈2中时，数据的顺序会倒过来，如下：

数据入栈顺序是1、2、3、4，此时再从栈2中执行出栈操作，数据出栈顺序也是1、2、3、4，可以满足队列“先入先出”的功能，因此我们不妨把一个栈专门同来进数据（push），另一个栈专门用来出数据（pop）。 

 每次进数据都压入push栈，出数据都从pop栈出，若pop栈为空，则把push栈的数据都压入pop栈后再出数据。

 代码如下：

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;//栈顶int capacity;//容量
}ST;
typedef struct
{ST push;ST pop;
} MyQueue;//初始化
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
//判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
//销毁
void STDestroy(ST* ps)
{free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
//入栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* p = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);ps->a = p;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}//出栈
void STPop(ST* ps)
{assert(ps);assert(ps->a);assert(!STEmpty(ps));ps->top--;
}
//取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps->a);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}
//创建我的队列
MyQueue* myQueueCreate()
{MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->push);STInit(&obj->pop);return obj;
}
//入队
void myQueuePush(MyQueue* obj, int x)
{STPush(&obj->push, x);
}
//出队
int myQueuePop(MyQueue* obj)
{if (STEmpty(&obj->pop)){while (!STEmpty(&obj->push)){STDataType x = STTop(&obj->push);STPop(&obj->push);STPush(&obj->pop, x);}}STDataType front = STTop(&obj->pop);STPop(&obj->pop);return front;
}
//取队头
int myQueuePeek(MyQueue* obj)
{if (STEmpty(&obj->pop)){while (!STEmpty(&obj->push)){STDataType x = STTop(&obj->push);STPop(&obj->push);STPush(&obj->pop, x);}}STDataType front = STTop(&obj->pop);return front;
}
//我的队列判空
bool myQueueEmpty(MyQueue* obj)
{return (STEmpty(&obj->push) && STEmpty(&obj->pop));
}
//销毁我的队列
void myQueueFree(MyQueue* obj)
{STDestroy(&obj->push);STDestroy(&obj->pop);free(obj);
}

运行结果：

用队列实现栈：

题目描述：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

• 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

首先要知道队列的特点是“先进先出”，因为此特点，将队列1中的数据移动到队列2中时，数据的顺序不会变，如下：

 数据的从队列1进队顺序是1、2、3、4，如直接从队列2出队，则出队顺序也是1、2、3、4，无法满足栈的“先进后出”的特点。因此，想要通过队列实现栈，要始终保证至少一个队列为空（若两个队列都为空，则只能执行判空和压入数据的操作），这样在出数据时，把不为空队列（假设有n个数据）的前n-1个数据移动到空队列中，再出最后一个数据，这样不断在两个队列之间导数据，就能实现把后入的数据先出出去，而想要压入数据时，直接在非空的队列队尾直接插入即可，这样就能实现栈“先进后出”的特点。

 代码如下：

typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;
typedef struct
{Que p1;Que p2;
} MyStack;
//判空 ：空返回1，非空返回0
bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}
//初始化
void QueueInit(Que* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;
}
//销毁
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* p = cur->next;free(cur);cur = p;}pq->head = NULL;pq->tail = NULL;pq->size = 0;
}
//入队
void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc failed");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = newnode;pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
//出队
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));//要有数据if (pq->head->next == NULL)//只有一个节点{free(pq->head);pq->head = NULL;pq->tail = NULL;}else{QNode* cur = pq->head->next;free(pq->head);pq->head = cur;}pq->size--;
}
//取队头
QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}
//取队尾
QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
//有效数据
int QueueSize(Que* pq)
{assert(pq);return pq->size;
}
//创建我的栈
MyStack* myStackCreate()
{MyStack* obj = (MyStack*)malloc(sizeof(MyStack));QueueInit(&obj->p1);QueueInit(&obj->p2);return obj;
}
//入栈
void myStackPush(MyStack* obj, int x)
{if (!QueueEmpty(&obj->p1)){QueuePush(&obj->p1, x);}else{QueuePush(&obj->p2, x);}
}
//出栈
int myStackPop(MyStack* obj)
{QDataType top = 0;if (!QueueEmpty(&obj->p1)){while (QueueSize(&obj->p1) > 1){QDataType a = QueueFront(&obj->p1);QueuePop(&obj->p1);QueuePush(&obj->p2, a);}top = QueueFront(&obj->p1);QueuePop(&obj->p1);}else{while (QueueSize(&obj->p2) > 1){QDataType a = QueueFront(&obj->p2);QueuePop(&obj->p2);QueuePush(&obj->p1, a);}top = QueueFront(&obj->p2);QueuePop(&obj->p2);}return top;
}
//取栈顶
int myStackTop(MyStack* obj)
{if (!QueueEmpty(&obj->p1)){return QueueBack(&obj->p1);}else{return QueueBack(&obj->p2);}
}
//判空
bool myStackEmpty(MyStack* obj)
{return (QueueEmpty(&obj->p1) && QueueEmpty(&obj->p2));
}
//销毁我的栈
void myStackFree(MyStack* obj)
{QueueDestroy(&obj->p1);QueueDestroy(&obj->p2);free(obj);
}

运行结果：