【数据结构】栈和队列经典题目

2024-10-21 09:25:38

1.有效的括号【链接】

代码实现

2.用队列实现栈【链接】

代码实现

3.用栈实现队列

编辑

代码实现

4.循环队列（数组实现）【链接】

代码实现

1.有效的括号【链接】

题目描述：

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

有效字符串需满足：

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

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

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

思路：

栈后进先出的特点与本题括号排序特点一致，如果遇到左括号就入栈，一旦遇到右括号，就去找与它最近的左括号匹配（即找栈顶元素），如果匹配，弹出栈顶元素，去找下一个,如果不匹配，返回false。

例如：( ) { [ } ]

' ( '入栈，++s, 遇到 ')' , 与栈顶元素' ( ' 相匹配，把' ( '弹出栈，++s，遇到 ' { '入栈，++s, 遇到 ' [ '入栈 ,++s,遇到 ' } ' , 与栈顶元素 ' [ ' 进行匹配，不配对，返回false，字符串无效。

代码实现

typedef char SLDataType;
typedef struct Stack 
{
    SLDataType* a;
    int top;
    int capacity;
} ST;

// 初始化
void STInit(ST* pst)
{
    assert(pst);
    pst->a = NULL;
    // top指向栈顶数据的下一个位置
    pst->top = 0;
    pst->capacity = 0;
}

// 销毁栈
void STDestroy(ST* pst) 
{
    assert(pst);
    free(pst->a);
    pst->a = NULL;
    pst->top = pst->capacity = 0;
}

// 入栈
void STPush(ST* pst, SLDataType x) 
{
    assert(pst);
    // 扩容
    if (pst->top == pst->capacity) 
    {
        int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
        SLDataType* tmp =(SLDataType*)realloc(pst->a, newcapacity * sizeof(SLDataType));
        if (tmp == NULL) 
        {
            perror("realloc fail");
            return;
        }
        pst->a = tmp;
        pst->capacity = newcapacity;
    }   
    pst->a[pst->top] = x;
    pst->top++;
}

// 出栈
void STPop(ST* pst) 
{
    assert(pst);
    assert(pst->top > 0);
    pst->top--;
}

// 获取栈顶数据
SLDataType STTop(ST* pst) 
{
    assert(pst);
    assert(pst->top > 0);
    return pst->a[pst->top - 1];
}

// 判空
bool STEmpty(ST* pst) 
{
    assert(pst);
    return pst->top == 0;
}

bool isValid(char* s) 
{
    ST st;
    STInit(&st);
    while (*s) 
    {
        // 遇到左括号入栈
        if (*s == '(' || *s == '{' || *s == '[') 
        {
            STPush(&st, *s);
        } 
        else // 遇到右括号就取栈顶的左括号尝试进行匹配
        {
            //如果字符串就给了一个右括号，就无法取栈顶元素，所以要判断栈是否为空
            if(STEmpty(&st))
            {
                STDestroy(&st);
                return false;
            }
            char top = STTop(&st);//取栈顶元素
            STPop(&st); // 弹出栈顶元素
            // 判断不匹配
            if ((top == '(' && *s != ')') 
            || (top == '{' && *s != '}') 
            ||(top == '[' && *s != ']')) 
            {
                STDestroy(&st);
                return false;
            }
        }
        ++s;
    }
    //判空，如果栈为空，就都匹配了，栈不为空，说明还有没匹配的左括号，数量不匹配
    bool ret=STEmpty(&st);

    STDestroy(&st);

    return ret;
}

2.用队列实现栈【链接】

题目描述：

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

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

思路：

构造两个队列，空队列用来导数据，非空队列用来插入数据，达到后进先出的效果。

例如：如果想将栈顶元素5拿走，而队列只能在队头删除元素，只能把1拿走，就再构造一个空队列导数据，将非空队列中前size-1个元素导入导空队列中，这时非空队列就只剩一个队头元素5，把它返回，然后pop掉它，此时又变成空队列了。

代码实现

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;


void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

//队尾插入
void QueuePush(Queue* pq, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->next = NULL;
	newnode->val = x;
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail= newnode;		 
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

//队头删除
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->size != 0);	
	//一个节点
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else//多个节点
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}

	pq->size--;		
}

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);

	return pq->phead->val;
}

//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);

	return pq->ptail->val;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

//销毁
void QueueDesTroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;

	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

//定义2个队列
typedef struct {  //匿名结构体
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack*pst=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&(pst->q1));
    QueueInit(&(pst->q2));
    return pst;
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&(obj->q1)))
    {
        QueuePush(&(obj->q1),x);
    }
    else
    {
        QueuePush(&(obj->q2),x);
    }
    
}


//移除并返回栈顶元素
int myStackPop(MyStack* obj) {
    //把不为空的队列的前size-1个数据导走到空队列并pop掉，剩下最后一个就是栈顶数据
    //假设法
    Queue*empty=&(obj->q1);
    Queue*nonempty=&(obj->q2);
    if(!QueueEmpty(&(obj->q1)))
    {
        nonempty=&(obj->q1);
        empty=&(obj->q2);
    }
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueFront(nonempty));
        QueuePop(nonempty);
    }

    int top=QueueFront(nonempty);
    QueuePop(nonempty);

    return top;
}


//取栈顶元素
int 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) {
    QueueDesTroy(&(obj->q1));//从里向外释放，先释放队列，再释放栈空间
    QueueDesTroy(&(obj->q2));
    free(obj);
}

3.用栈实现队列

题目描述：

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

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾

int pop() 从队列的开头移除并返回元素

int peek() 返回队列开头的元素

boolean empty() 如果队列为空，返回 true ；否则，返回 false

思路：

将一个栈当作输入栈用来入数据，一个栈当作输出栈用来出数据，由于栈具有后进先出的特性，若输出栈为空，则将输入栈中的数据全部导入到输出栈，这样输出栈从栈顶到栈底的顺序就是队列的输出顺序。

代码实现

typedef int SLDataType;
typedef struct Stack
{
	SLDataType* a;//指向动态开辟的数组
	int top;//确定栈顶位置
	int capacity;//栈的容量
}ST;

//初始化
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	//top指向栈顶数据的下一个位置
	pst->top = 0;	
	pst->capacity = 0;
}
//销毁栈
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

//入栈
void STPush(ST* pst, SLDataType x)
{
	assert(pst);
	//扩容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(pst->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//top指向栈顶数据的下一个位置
	pst->a[pst->top] = x;
	pst->top++;	
}
//出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

//获取栈顶数据
SLDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top - 1];
}

//判空
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}
//获取栈里数据个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}


//定义两个栈
typedef struct {
    ST pushst;
    ST popst;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));

    STInit(&(obj->pushst));
    STInit(&(obj->popst));
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    STPush(&(obj->pushst),x);    
}

int myQueuePop(MyQueue* obj) {
   int front = myQueuePeek(obj);
   STPop(&(obj->popst));
   return front;
}

//取poopst的栈顶元素
int myQueuePeek(MyQueue* obj) {
     if(STEmpty(&(obj->popst)))
    {
        //导数据
        while(!STEmpty(&(obj->pushst)))
        {
            int top=STTop(&(obj->pushst));
            STPush(&(obj->popst),top);
            STPop(&(obj->pushst));
        }
    }

    return STTop(&(obj->popst));
}

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&(obj->pushst)) && STEmpty(&(obj->popst));
}

void myQueueFree(MyQueue* obj) {      
    STDestroy(&(obj->pushst));
    STDestroy(&(obj->popst));
    free(obj);
}

4.循环队列（数组实现）【链接】

代码实现

//循环队列结构
typedef struct {
    int* a;
    int front;//队头指针
    int rear;//队尾指针 指向尾的下一个元素
    int k;//队列长度
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //多开一个空间
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    obj->front = 0;
    obj->rear = 0;
    obj->k = k;

    return obj;
}

//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}

//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}

//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
        return false;

    obj->a[obj->rear] = value;
    obj->rear++;
    obj->rear %= (obj->k + 1);//解决rear下标值回绕的问题
    return true;
}

//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return false;
    obj->front++;
    obj->front %= (obj->k + 1);//解决front下标值回绕的问题
    return true;
}

//获取队首元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[obj->front];
}

//获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->rear == 0 ? obj->a[obj->k] : obj->a[obj->rear - 1];//与下面代码等价
       /*return obj->a[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];取模解决回绕问题*/       
}

//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

码农公寓

1.有效的括号【链接】

代码实现

2.用队列实现栈【链接】

代码实现

3.用栈实现队列

代码实现

4.循环队列（数组实现）【链接】

代码实现

相关文章