目錄
鏈接. - 力扣（LeetCode）
描述
思路
push
pop
peek
empty
代碼
鏈接
. - 力扣（LeetCode）
描述
思路
push
例如我們將10個元素放入棧中，假設最左邊為棧頂，最右側為棧底
則為10,9,8,7,6,5,4,3,2,1
pop
從隊列的開頭移除并返回元素，隊列的開頭為最右側的1
我們先將前面的元素放入空棧中
空棧中元素順序為2,3,4,5,6,7,8,9,10
我們發現元素順序反了，說明等下要反轉回來
此時原棧中只剩最后一個元素1，我們將1拷貝下來并踢出去即可
此時原棧成為空棧，我們將元素全部放回去即可，原棧順序改為10,9,8,7,6,5,4,3,2
通過反轉我們就順利的將隊列中的第一個元素1給刪除了
peek
返回隊列開頭元素與pop思路基本一致，唯一的不同點為原棧中不需要再將元素1刪去，拷貝后直接將元素全部取回來即可。
empty
兩個棧均不為空指針即可
代碼
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top; // 棧頂int _capacity; // 容量
}Stack;
// 初始化棧
void StackInit(Stack* ps);
// 入棧
void StackPush(Stack* ps, STDataType data);
// 出棧
void StackPop(Stack* ps);
// 獲取棧頂元素
STDataType StackTop(Stack* ps);
// 獲取棧中有效元素個數
int StackSize(Stack* ps);
// 檢測棧是否為空，如果為空返回非零結果，如果不為空返回0
int StackEmpty(Stack* ps);
// 銷毀棧
void StackDestroy(Stack* ps);
void StackInit(Stack* ps) {ps->_a = NULL;ps->_capacity = 0;ps->_top = -1;
}
void StackPush(Stack* ps, STDataType data) {if (ps->_capacity == ps->_top + 1) {int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));if (tmp == NULL) {perror("realloc error");return;}ps->_a = tmp;ps->_capacity = newcapacity;}ps->_top++;ps->_a[ps->_top] = data;
}
void StackPop(Stack* ps) {if (ps->_top == -1) {return;}ps->_top--;
}
STDataType StackTop(Stack* ps) {return ps->_a[ps->_top];
}
int StackSize(Stack* ps) {return ps->_top + 1;
}
int StackEmpty(Stack* ps) {if (ps->_top == -1)return 1;return 0;
}
void StackDestroy(Stack* ps) {ps->_capacity = 0;ps->_top = -1;free(ps->_a);ps->_a = NULL;
}
typedef struct {Stack s1;Stack s2;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* mn = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&(mn->s1));StackInit(&(mn->s2));return mn;
}void myQueuePush(MyQueue* obj, int x) {Stack* nonempty = &(obj->s1), * empty = &(obj->s2);if (StackEmpty(nonempty)) {nonempty = &(obj->s2);empty = &(obj->s1);}StackPush(nonempty, x);
}int myQueuePop(MyQueue* obj) {Stack* nonempty = &(obj->s1), * empty = &(obj->s2);int a;if (StackEmpty(nonempty)) {nonempty = &(obj->s2);empty = &(obj->s1);}while (StackSize(nonempty) != 1) {StackPush(empty, StackTop(nonempty));StackPop(nonempty);}a = StackTop(nonempty);StackPop(nonempty);while (StackSize(empty) != 0) {StackPush(nonempty, StackTop(empty));StackPop(empty);}return a;
}int myQueuePeek(MyQueue* obj) {Stack* nonempty = &(obj->s1), * empty = &(obj->s2);if (StackEmpty(nonempty)) {nonempty = &(obj->s2);empty = &(obj->s1);}while (StackSize(nonempty) != 1) {StackPush(empty, StackTop(nonempty));StackPop(nonempty);}int a = StackTop(nonempty);while (StackSize(empty) != 0) {StackPush(nonempty, StackTop(empty));StackPop(empty);}return a;
}bool myQueueEmpty(MyQueue* obj) {if (StackEmpty(&(obj->s2)) && StackEmpty(&(obj->s1)))return true;return false;
}void myQueueFree(MyQueue* obj) {StackDestroy(&(obj->s1));StackDestroy(&(obj->s2));free(obj);
}
)
?)
)
)
