栈和队列习题精选（持续更新中）

第一题（括号匹配）

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

有效字符串需满足：

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

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

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

char pairs(char* ch)
{if(*ch=='}')return '{';if(*ch==')')return '(';if(*ch==']')return '[';return 0;
}
bool isValid(char * s){char stack[10000]={0};int top=0,i=0;while(*(s+i)){char ch=pairs(s+i);if(ch){if(top==0||ch!=stack[top-1])//这里需要判断栈是否为空的原因是没有左括号还在匹配会造成越界{return false;}else{top--;}}else{stack[top++]=*(s+i);}i++;}return top==0;}

第二题（用队列模拟栈）

这里需要判断栈是否为空的原因是没有左括号还在匹配会造成越界

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

typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* obj = (MyStack*)malloc(sizeof(MyStack));QueueInit(&obj->q1);QueueInit(&obj->q2);return obj;
}void myStackPush(MyStack* obj, int x) {assert(obj);if (!QueueEmpty(&obj->q1)){QueuePush(&obj->q1);}else{QueuePush(&obj->q2);}return;
}int myStackPop(MyStack* obj) {Queue* pEmpty = &obj->q1;//注意左右两边的类型要匹配Queue* pNonEmpty = &obj->q2;if (!QueueEmpty(pEmpty)){Queue* pEmpty = &obj->q2;Queue* pNonEmpty = &obj->q1;}while (QueueSize(pNonEmpty) > 1){QueuePush(pNonEmpty, QueueFront(pNonEmpty));QueuePop(pNonEmpty);}int top = QueueFront(pNonEmpty);QueuePop(pNonEmpty);return top;
}int myStackTop(MyStack* obj) {Queue* pEmpty = &obj->q1;Queue* pNonEmpty = &obj->q2;if (!QueueEmpty(pEmpty)){Queue* pEmpty = &obj->q2;Queue* pNonEmpty = &obj->q1;}return QueueBack(pNonEmpty);
}bool myStackEmpty(MyStack* obj) {if (!(QueueEmpty(&obj->q2)) && !(QueueEmpty(&obj->q1))){return false;}return true;
}void myStackFree(MyStack* obj) {QueueDestory(&obj->q1);//free可能会free不干净，万一是链式结构呢？QueueDestory(&obj->q2);free(obj);
}

第三题（用栈模拟队列）

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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 操作是合法的。

你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

解题思路

可以用两个栈实现，一个栈进行入队操作，我们称为入队栈，另一个栈进行出队操作，我们称为出队栈

出队操作： 当出队栈不为空是，直接进行出栈操作，如果为空，需要把入队栈元素全部导入到出队的栈，然后再进行出栈操作。

#define maxSize 100
typedef struct {//入队栈Stack pushST;//出队栈Stack popST;
} MyQueue;/** Initialize your data structure here. */
MyQueue* myQueueCreate(int maxSize) {MyQueue* pqueue = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&pqueue->pushST, maxSize);StackInit(&pqueue->popST, maxSize);return pqueue;
}/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {//入队栈进行入栈操作StackPush(&obj->pushST, x);
}/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {//如果出队栈为空，导入入队栈的元素if(StackEmpty(&obj->popST) == 0){while(StackEmpty(&obj->pushST) != 0){StackPush(&obj->popST, StackTop(&obj->pushST));StackPop(&obj->pushST);}}int front = StackTop(&obj->popST);//出队栈进行出队操作StackPop(&obj->popST);return front;
}/** Get the front element. */
int myQueuePeek(MyQueue* obj) {//类似于出队操作if(StackEmpty(&obj->popST) == 0){while(StackEmpty(&obj->pushST) != 0){StackPush(&obj->popST, StackTop(&obj->pushST));StackPop(&obj->pushST);}}return StackTop(&obj->popST);
}//判断栈是否为空
bool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->pushST) == 0&&  StackEmpty(&obj->popST) == 0;
}void myQueueFree(MyQueue* obj) {StackDestroy(&obj->pushST);//与上题一样不能直接free，要交给栈的销毁函数来做StackDestroy(&obj->popST);free(obj);
}

第四题（设计循环队列）

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。

Front: 从队首获取元素。如果队列为空，返回 -1 。

Rear: 获取队尾元素。如果队列为空，返回 -1 。

enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

isEmpty(): 检查循环队列是否为空。

isFull(): 检查循环队列是否已满。

#define dataType int typedef struct {dataType* arr;int front;int rear;int size;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* ret = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (ret == NULL){perror("malloc::fail");}ret->arr = (dataType*)malloc(sizeof(dataType) * (k + 1));ret->front = ret->rear = 0;ret->size =k+1;return ret;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (((obj->rear + 1) %obj->size) == obj->front)//判断循环队列是否为满,%不是/{return false;}obj->arr[obj->rear] = value;obj->rear=(obj->rear+1)%obj->size;//不需要加MaxSizereturn true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (obj->rear == obj->front){return false;}obj->front= (obj->front +1) % obj->size;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (obj->rear == obj->front){return -1;}return obj->arr[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if (obj->rear==obj->front){return -1;}//因为是先存数据在加加，所以rear实际上是指向队尾的下一个元素//故最好在此处进行分类讨论if(obj->rear==0){return obj->arr[obj->size-1];}else{return obj->arr[obj->rear-1];}}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {if (obj->front == (obj->rear + 1 + obj->size) % obj->size){return true;}return false;
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);//双层释放free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/