初階數據結構：棧與隊列的擴展補充

1. 棧與隊列練習題

1.1 棧的括號匹配問題

題目信息：

題目鏈接：
括號匹配問題

思路：利用棧的后進先出特性來實現括號的匹配

當遇到 ‘(’，‘{’，‘[’，這三種括號時進行壓棧
當遇到’)‘，’}‘，’]'，這三種括號時將括號中的元素進行出棧匹配

過程演示：

在這里插入圖片描述

typedef char STDataType;
typedef struct Stack
{STDataType* _a;int _top; // 棧頂int _capacity; // 容量
}Stack;void CheckCapacity(Stack* ps)
{if (ps->_capacity == ps->_top){int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;STDataType* data = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));if (data == NULL){perror("realloc failed");exit(-1);}ps->_a = data;ps->_capacity = newcapacity;}
}void StackInit(Stack* ps)
{ps->_capacity = 0;ps->_top = 0;ps->_a = NULL;CheckCapacity(ps);
}void StackPush(Stack* ps, STDataType data)
{assert(ps);CheckCapacity(ps);ps->_a[ps->_top] = data;ps->_top++;
}int StackEmpty(Stack* ps)
{assert(ps);return ps->_top == 0;
}void StackPop(Stack* ps)
{assert(!StackEmpty(ps));ps->_top--;
}STDataType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->_a[ps->_top - 1];
}int StackSize(Stack* ps)
{assert(ps);return ps->_top;
}void StackDestroy(Stack* ps)
{assert(ps);free(ps->_a);ps->_capacity = ps->_top = 0;
}bool isValid(char* s) 
{Stack st1;StackInit(&st1);int i = 0;for(i = 0; s[i] != '\0'; i++){if(s[i] == '(' || s[i] == '[' || s[i] == '{'){StackPush(&st1, s[i]);}else if(s[i] == ')' || s[i] == ']' || s[i] == '}'){if(StackEmpty(&st1)){return false;}char tmp = StackTop(&st1);if(s[i] == ')' && tmp == '('){StackPop(&st1);}else if(s[i] == ']' && tmp == '['){StackPop(&st1);}else if(s[i] == '}' && tmp == '{'){StackPop(&st1);}else{break;}}}if(StackEmpty(&st1)){return true;}return false;      
}

1.2 用隊列來實現棧

題目信息：

題目鏈接：
用兩個隊列實現棧

在這里插入圖片描述

myStack結構：
在這里插入圖片描述

typedef int QDataType;typedef struct QListNode
{struct QListNode* _pNext;QDataType _data;
}QNode;typedef struct Queue
{QNode* _front;QNode* _rear;
}Queue;void QueueInit(Queue* q)
{assert(q);q->_front = q->_rear = NULL;
}QNode* BuyNewNode2(QDataType data)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc failed");exit(-1);}newnode->_data = data;newnode->_pNext = NULL;return newnode;
}void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* newnode = BuyNewNode2(data);if (q->_front == NULL){q->_front = q->_rear = newnode;}else{q->_rear->_pNext = newnode;q->_rear = q->_rear->_pNext;}
}int QueueEmpty(Queue* q)
{assert(q);return q->_front == NULL;
}void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));QNode* cur = q->_front->_pNext;free(q->_front);q->_front = cur;if (q->_front == NULL){q->_rear = NULL;}
}QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->_front->_data;
}QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->_rear->_data;
}int QueueSize(Queue* q)
{assert(q);int count = 0;QNode* cur = q->_front;while (cur){cur = cur->_pNext;count++;}return count;
}void QueueDestroy(Queue* q)
{assert(q);while (q->_front){QueuePop(q);}
}typedef struct MyStack
{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);Queue* no_empty = &obj->q1;if (QueueEmpty(&obj->q1)){no_empty = &obj->q2;}QueuePush(no_empty, x);
}bool myStackEmpty(MyStack* obj)
{assert(obj);return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}int myStackTop(MyStack* obj)
{assert(obj);assert(!myStackEmpty(obj));Queue* no_empty = &obj->q1;if (QueueEmpty(&obj->q1)){no_empty = &obj->q2;}return QueueBack(no_empty);
}int myStackPop(MyStack* obj)
{Queue* no_empty = &obj->q1;Queue* empty = &obj->q2;if (QueueEmpty(&obj->q1)){no_empty = &obj->q2;empty = &obj->q1;}while (QueueSize(no_empty) > 1){QueuePush(empty, QueueFront(no_empty));QueuePop(no_empty);}int val = QueueFront(no_empty);QueuePop(no_empty);return val;
}void myStackFree(MyStack* obj)
{assert(obj);Queue* no_empty = &obj->q1;if (QueueEmpty(&obj->q1)){no_empty = &obj->q2;}QueueDestroy(no_empty);free(obj);
}

1.3 用棧來實現隊列

題目信息：

題目鏈接：
用棧實現隊列

過程演示：
在這里插入圖片描述

typedef char STDataType;
typedef struct Stack
{STDataType* _a;int _top; // 棧頂int _capacity; // 容量
}Stack;void CheckCapacity(Stack* ps)
{if (ps->_capacity == ps->_top){int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;STDataType* data = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));if (data == NULL){perror("realloc failed");exit(-1);}ps->_a = data;ps->_capacity = newcapacity;}
}void StackInit(Stack* ps)
{ps->_capacity = 0;ps->_top = 0;ps->_a = NULL;CheckCapacity(ps);
}void StackPush(Stack* ps, STDataType data)
{assert(ps);CheckCapacity(ps);ps->_a[ps->_top] = data;ps->_top++;
}int StackEmpty(Stack* ps)
{assert(ps);return ps->_top == 0;
}void StackPop(Stack* ps)
{assert(!StackEmpty(ps));ps->_top--;
}STDataType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->_a[ps->_top - 1];
}int StackSize(Stack* ps)
{assert(ps);return ps->_top;
}void StackDestroy(Stack* ps)
{assert(ps);free(ps->_a);ps->_capacity = ps->_top = 0;
}typedef struct 
{Stack push_stack;Stack pop_stack;    
} MyQueue;MyQueue* myQueueCreate() 
{MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&obj->push_stack);StackInit(&obj->pop_stack);return obj;    
}void myQueuePush(MyQueue* obj, int x) 
{assert(obj);StackPush(&obj->push_stack, x);    
}bool myQueueEmpty(MyQueue* obj) 
{assert(obj);return StackEmpty(&obj->push_stack) && StackEmpty(&obj->pop_stack);
}int myQueuePeek(MyQueue* obj) 
{assert(obj);assert(!myQueueEmpty(obj));if(StackEmpty(&obj->pop_stack)){while(!StackEmpty(&obj->push_stack)){StackPush(&obj->pop_stack, StackTop(&obj->push_stack));StackPop(&obj->push_stack);}}return StackTop(&obj->pop_stack);
}int myQueuePop(MyQueue* obj) 
{assert(obj);assert(!myQueueEmpty(obj));int data = myQueuePeek(obj);StackPop(&obj->pop_stack);return data;
}void myQueueFree(MyQueue* obj) 
{assert(obj);StackDestroy(&obj->push_stack);StackDestroy(&obj->pop_stack);free(obj);    
}

1.4 擴展：循環隊列

題目信息：

題目鏈接：
循環鏈表

過程演示：
在這里插入圖片描述

typedef struct
{int* data;int c_front;int c_rear;int capacity_k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//k + 1為構建循環鏈表所需的空間大小obj->data = (int*)malloc((k + 1) * sizeof(int));//注：k為能夠存儲的元素個數，即鏈表存儲數據的容量obj->capacity_k = k;obj->c_front = obj->c_rear = 0;return obj;
}bool myCircularQueueIsFull(MyCircularQueue* obj)
{assert(obj);int k = obj->capacity_k;return obj->c_front % (k + 1) == (obj->c_rear + 1) % (k + 1);
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{assert(obj);int k = obj->capacity_k;if (!myCircularQueueIsFull(obj)){int rear = obj->c_rear % (k + 1);obj->data[rear] = value;obj->c_rear++;return true;}return false;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{assert(obj);int k = obj->capacity_k;return obj->c_front % (k + 1) == obj->c_rear % (k + 1);
}bool myCircularQueueDeQueue(MyCircularQueue* obj)
{assert(obj);if (!myCircularQueueIsEmpty(obj)){obj->c_front++;return true;}return false;
}int myCircularQueueFront(MyCircularQueue* obj)
{assert(obj);int k = obj->capacity_k;if (!myCircularQueueIsEmpty(obj)){int front = obj->c_front % (k + 1);return obj->data[front];}return -1;
}int myCircularQueueRear(MyCircularQueue* obj)
{assert(obj);int k = obj->capacity_k;if (!myCircularQueueIsEmpty(obj)){int pre_rear = (obj->c_rear - 1) % (k + 1);return obj->data[pre_rear];}return -1;
}void myCircularQueueFree(MyCircularQueue* obj)
{assert(obj);free(obj->data);free(obj);
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/712214.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/712214.shtml
英文地址，請注明出處：http://en.pswp.cn/news/712214.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！