一：实现一个栈，要求实现Push(出栈)、Pop(入栈)、Min(返回最小值)的时间复杂度为O(1)

方法一：

思路：这里我们栈底层采用的是静态顺序表实现，出栈、入栈我们都很容易实现时间复杂度为O(1)，但是，要返回最小值，按照我们常规的思路，遍历栈，可以得出最小值，但是时间复杂度为O(n),不符合题目要求，我们可以在栈中每次放入两个数据，一个是本来就要放的data,另一个为Mindata，将这两个数据封装为一个结构体，如果栈为空，我们可以将Mindata的值与data相等，若不为空，可以将新元素中的data与栈顶元素中的Mindata比较，若新元素中的data小于等于栈顶的，可以将新元素中的Mindata的值与data相等，若大于栈顶元素中的Mindata，新元素中的data不变，Mindata更新为栈顶元素中的Mindata

假设现在我们向栈中依次放入：5， 2， 3， 1.第一次放5，因为此时栈为空，所以data和Mindata都是5，然后放2，因为2小于等于栈顶元素中的Mindata5，所以新元素中的data与Mindata都为2，接下来放3，因为3大于栈顶元素中的Mindata2，所有新元素中的data为3，Mindata为2，最后放1，过程如下图：

代码实现如下：

StackAndQueueInterview.h

#pragma once #include <stdio.h> #include <assert.h> #define MAX_SIZE 100 //将本来的数据和最小值封装为一个结构体 typedef struct NewData { int data; int Mindata; }Newdata; typedef struct Stack { Newdata _arr[MAX_SIZE];//栈里面放的都是封装好的结构体 int _size; }Stack, *PStack; //初始化栈 void InitStack(PStack s); //给栈顶插入元素 void StackPush(PStack s, int data); void StackPop(PStack s);//出栈 //返回栈最小元素 int StackMindata(PStack s);

StackAndQueueInterview.c

#include "StackAndInterview.h" //初始化栈 void InitStack(PStack s) { assert(s); //初始化只需将有效元素清零 s->_size = 0; } //给栈顶插入元素 void StackPush(PStack s, int data) { assert(s); int size = s->_size; if (size == MAX_SIZE) { printf("栈已满!!!\n"); return; } //如果栈是空的，那么最小data和data都是data if (size == 0) { s->_arr->data = s->_arr->Mindata = data; s->_size++; return; } //如果栈不为空，比较data与栈的最小元素，1.若data小，那么用data更新最小元素 if ((s->_arr + size - 1)->Mindata >= data) { (s->_arr + size)->Mindata = (s->_arr + size)->data = data; s->_size++; return; } //2.若栈的最小元素小，新插入的data还是data，Mindata用原栈中的Mindata更新 else { (s->_arr + size)->Mindata = (s->_arr + size - 1)->Mindata; (s->_arr + size)->data = data; s->_size++; } } //从栈顶出栈 void StackPop(PStack s) { assert(s); if (s->_size == 0) { printf("栈已空!!!\n"); return; } s->_size--; } //返回栈最小元素 int StackMindata(PStack s) { assert(s); if (s->_size == 0) { printf("栈已空，操作失败!!!\n"); return 0; } return (s->_arr + (s->_size - 1))->Mindata; }

test.c

测试环境：vs2031

#include "StackAndInterview.h" #include <Windows.h> int main() { Stack s; InitStack(&s); StackPush(&s, 5); StackPush(&s, 4); StackPush(&s, 2); StackPush(&s, 3); StackPush(&s, 7); StackPush(&s, 9); StackPush(&s, 1); StackPop(&s); printf("Mindata:%d\n",StackMindata(&s)); system("pause"); return 0; }

方法二：

思路：我们可以使用两个栈存储数据，一个栈放data，一个栈放Mindata，放Mindata栈的栈顶元素一定是此时栈中的最小元素，然后将这两个栈封装为一个栈，就可以实现题目中的要求。

假设我们还是在栈中依次放入：5，2，3，1.如果此时data栈为空，那么说明Mindata栈也为空，放5时，两个栈都为空，直接将5都入栈，接下来放2，data栈直接放，如果将要放入的data，2小于等于Mindata栈的栈顶元素，那么也将2入到Mindata栈，否则，不予理会。操作如下图所示：

如果要取最小值，就取Mindata栈的栈顶元素，这样就能实现时间复杂度为O(1)，代码实现如下：

StackAndInterview.h

#pragma once #include <stdio.h> #include <assert.h> #define MAX_SIZE 100 typedef int DataType; //存放平常数据的栈 typedef struct Stack1 { DataType _arr[MAX_SIZE]; int _size; }Stack1; //存放最小数据的栈 typedef struct Stack2 { DataType _arr[MAX_SIZE]; int _size; }Stack2; //将两个栈封装为1个 typedef struct Stack { Stack1 s1; Stack2 s2; }Stack, *PStack; //初始化栈 void InitStack(PStack s); //入栈 void StackPush(PStack s, DataType data); //获取栈顶元素 DataType StackTop(Stack2* s2); //出栈 void StackPop(PStack s); //获取最小值 DataType StackMindata(PStack s);

StackAndInterview.c

#include "StackAndInterview.h" //初始化栈 void InitStack(PStack s) { assert(s); //将两个栈分别初始化 s->s1._size = 0; s->s2._size = 0; } //入栈 void StackPush(PStack s, DataType data) { assert(s); if (s->s1._size == MAX_SIZE) { printf("栈已满!!!\n"); return; } //若栈为空，直接入栈 if (s->s1._size == 0) { s->s1._arr[0] = data; s->s2._arr[0] = data; s->s1._size++; s->s2._size++; } else { //如果data小于，s2栈中的栈顶元素，将data入栈到S2 if (data <= StackTop(&(s->s2))) { s->s2._arr[s->s2._size] = data; s->s2._size++; } s->s1._arr[s->s1._size] = data; s->s1._size++; } } //获取栈顶元素 DataType StackTop(Stack2* s2) { assert(s2); if (s2->_size == 0) { printf("栈已空!!!\n"); return 0; } return s2->_arr[s2->_size - 1]; } //出栈 void StackPop(PStack s) { assert(s); if (s->s1._size == 0) { printf("栈已空!\n"); return; } //如果两个栈栈顶元素相等，都出栈 if (s->s1._arr[s->s1._size - 1] == StackTop(&(s->s2))) { s->s1._size--; s->s2._size--; } else s->s1._size--; } //获取最小值 DataType StackMindata(PStack s) { assert(s); if (s->s1._size == 0) { printf("栈已空!!!\n"); return 0; } return StackTop(&(s->s2)); }

test.c

#include "StackAndInterview.h" #include <Windows.h> int main() { Stack s; InitStack(&s); StackPop(&s); StackPush(&s, 5); StackPush(&s, 4); StackPush(&s, 2); StackPush(&s, 3); StackPush(&s, 7); StackPush(&s, 9); StackPush(&s, 1); StackPop(&s); printf("Mindata:%d\n", StackMindata(&s)); system("pause"); return 0; }

二：使用两个栈实现一个队列

思路：首先，我们必须要搞清楚栈和队列分别有什么特性，栈，先进后出，只能从栈顶进行入栈和出栈操作；而对于队列，先进先出，从队尾进行入队列操作，从队头进行出队列操作。假设我们有两个栈s1和s2，s1用来入队列操作，s2用来进行出队列操作，如下图所示我们依次要向队列中插入元素5， 4，9，因为我们将元素依次入到栈s1，如果是队列我们出队列首先是元素5，但由于元素在栈s1中，不能直接对栈底元素进行出栈操作，所以我们可以将s1中的元素，依次入栈到s2 入栈后如下图： 此时，队头元素就是栈s2的栈顶元素，要出队列，我们可以直接对s2进行出栈操作。假设我们现在又要向队列中依次插入元素2，4，如下图： 从上面三幅图我们可得出：假设s1不为空，s2为空，那么队头为s1的栈底，队尾为s1的栈顶；假设s1为空，s2不为空，那么队头为s2的栈顶，队尾为s2的栈底；假设s1、s2都不为空，那么队头为s2的栈顶，队尾为s1的栈顶。具体代码实现如下：

StackAndInterview.h

#pragma once #include <stdio.h> #include <assert.h> typedef int DataType; #define MAX_SIZE 3 typedef struct Stack { DataType _arr[MAX_SIZE]; int _size; }Stack; typedef struct Queue { Stack s1; Stack s2; }Queue, *PQueue; //初始化队列 void QueueInit(PQueue q); //入栈 void StackPush(Stack* s, DataType data); //入队列,入到栈s1 void QueuePush(PQueue q, DataType data); //返回栈顶元素 DataType StackTop(Stack* s); //出栈 void StackPop(Stack* s); //出队列 void QueuePop(PQueue q); //获取队头元素 DataType QueueFront(PQueue q); //获取队尾元素 DataType QueueBack(PQueue q);

StackAndInterview.c

#include "StackAndInterview.h" //初始化队列 void QueueInit(PQueue q) { assert(q); //对两个栈进行初始化 q->s1._size = 0; q->s2._size = 0; } //入栈 void StackPush(Stack* s, DataType data) { assert(s); if (s->_size == MAX_SIZE) { printf("栈已满!!!\n"); return; } s->_arr[s->_size] = data; s->_size++; } //入队列,入到栈s1 void QueuePush(PQueue q, DataType data) { assert(q); if (q->s1._size == MAX_SIZE) { //如果s2为空，才能将s1中的元素搬移到s2否则，队头和就找不到了 if (q->s2._size == 0) { while (q->s1._size != 0) { DataType data = StackTop(&(q->s1)); StackPop(&(q->s1)); StackPush(&(q->s2), data); } } else { printf("队列已满!!!\n"); return; } } //对s1进行入栈操作 StackPush(&(q->s1), data); } //返回栈顶元素 DataType StackTop(Stack* s) { assert(s); if (s->_size == 0) { printf("栈已空！\n"); return 0; } return s->_arr[s->_size - 1]; } //出栈 void StackPop(Stack* s) { assert(s); if (s->_size == 0) { printf("栈为空，操作失败!!!\n"); return; } s->_size--; } //出队列 void QueuePop(PQueue q) { assert(q); //如果s2不为空，那么s2的栈顶元素就是队头，直接出队列 if (q->s2._size > 0) { StackPop(&(q->s2)); return; } //如果s2为空 else { //如果s1也为空，队列为空 if (q->s1._size == 0) { printf("队列为空，操作失败!!!\n"); return; } //如果s1不为空，将s1的数据倒过来 else { while (q->s1._size != 0) { DataType data = StackTop(&(q->s1)); StackPop(&(q->s1)); StackPush(&(q->s2), data); } //此时，s2的栈顶就是队头 StackPop(&(q->s2)); } } } //获取队头元素 DataType QueueFront(PQueue q) { assert(q); //如果s1和s2都为空，说明队列为空 if (q->s1._size == 0 && q->s2._size == 0) { printf("队列为空，操作失败!!!\n"); return 0; } //如果s2不为空，那么队头就是s2的栈顶，否则，就是s1的栈底 if (q->s2._size != 0) return StackTop(&(q->s2)); else return q->s1._arr[0]; } //获取队尾元素 DataType QueueBack(PQueue q) { assert(q); //如果s1和s2都为空，说明队列为空 if (q->s1._size == 0 && q->s2._size == 0) { printf("队列为空，操作失败!!!\n"); return 0; } //如果s1不为空，那么队尾就是s1的栈顶，否则，就是s2的栈底 if (q->s1._size != 0) return StackTop(&(q->s1)); else return q->s2._arr[0]; }

test.c

#include "StackAndInterview.h" #include <Windows.h> void Test3() { Queue q; QueueInit(&q); QueuePush(&q, 5); QueuePush(&q, 4); QueuePush(&q, 1); QueuePush(&q, 3); printf("Front:%d\n", QueueFront(&q)); QueuePop(&q); //获取队头元素 printf("Front:%d\n",QueueFront(&q)); //获取队尾元素 printf("Back:%d\n",QueueBack(&q)); QueuePush(&q, 1); QueuePush(&q, 2); printf("Front:%d\n", QueueFront(&q)); printf("Back:%d\n", QueueBack(&q)); } int main() { //Test1();//面试题1方法1 //Test();//面试题方法2 Test3();//面试题2 system("pause"); return 0; }

三：使用两个队列实现一个栈

思路：这里我们很容易就联想到上道题的方法，如下图：我们将5，4，3依次入栈，3为栈顶，5为栈底，假设有两个队列q1、q2，先将5，4，3依次入队列，5为队头，3为队尾，如果要进行出栈操作，由于队列只能从队头进行出队列操作，所以q1不能完成要求，但如果向上题一样，将q1中的元素依次倒如q2，会发现，元素排列还是一样，不能完成要求。 但是如果我们这样做呢，入队列时向q1入，出队列时将q1中的元素导入到q2中只剩一个，那么就可以将栈顶元素变成队头元素，就可以完成要求，如下图； 具体代码实现如下：

StackAndInterview.h

#pragma once #include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int DataType; typedef struct Node { DataType _data; struct Node* _pNext; }Node; typedef struct Queue { Node* _pHead; Node* _pTail; }Queue; typedef struct Stack { Queue* q1; Queue* q2; }Stack, *PStack; //初始化栈 void StackInit(PStack s); //创建新节点 Node* BuyNewNode(DataType data); //入栈 void StackPush(PStack s, DataType data); //入队列 void QueuePush(Queue* q, DataType data); //出队列 void QueuePop(Queue* q); //队列判空 int QueueEmpty(Queue* q); //出栈 void StackPop(PStack s); //获取栈顶元素 DataType StackTop(PStack s);

StackAndInterview.c

#include "StackAndInterview.h" //创建新节点 Node* BuyNewNode(DataType data) { Node* ptr; ptr = (Node*)malloc(sizeof(Node)); if (NULL == ptr) { printf("节点申请失败!!!\n"); return NULL; } ptr->_data = data; ptr->_pNext = NULL; return ptr; } //初始化栈 void StackInit(PStack s) { assert(s); //分别将两个队列初始化 s->q1->_pHead = s->q1->_pTail = BuyNewNode(0); s->q2->_pHead = s->q2->_pTail = BuyNewNode(0); } //入队列 void QueuePush(Queue* q, DataType data) { assert(q); //从队尾插入，不用考虑队列为空时，因为刚开始头节点和尾节点指向同一个节点 q->_pTail->_pNext = BuyNewNode(data); q->_pTail = q->_pTail->_pNext; } //入栈 void StackPush(PStack s, DataType data) { assert(s); //直接对q1进行入队列 QueuePush(s->q1, data); } //出队列 void QueuePop(Queue* q) { assert(q); Node* pDelete = q->_pHead->_pNext; if (q->_pHead->_pNext == NULL) { printf("队列为空，操作失败!!!\n"); return; } //从队头出队列 //如果只剩一个节点，按照小面这样做，_pHead就指向NULL，而_pTail还是指向最后一个节点 q->_pHead->_pNext = q->_pHead->_pNext->_pNext; if (pDelete->_pNext == NULL) q->_pTail = q->_pHead; free(pDelete); } //队列判空 int QueueEmpty(Queue* q) { assert(q); if (q->_pHead->_pNext == NULL) return 1; return 0; } //获取队头元素 DataType QueueFront(Queue* q) { assert(q); if (q->_pHead->_pNext == NULL) { printf("队列为空，操作失败！\n"); return 0; } return q->_pHead->_pNext->_data; } //出栈 void StackPop(PStack s) { assert(s); Node* ptr2 = NULL; //如果q1不为空，q2为空，将q1元素搬移到q2只剩一个，q1队头就是栈的栈顶 if (!QueueEmpty(s->q1) && QueueEmpty(s->q2)) { Node* ptr = s->q1->_pHead->_pNext;//q1的第一个有效节点 while (ptr->_pNext) { DataType data = QueueFront(s->q1); QueuePop(s->q1); QueuePush(s->q2, data); ptr = s->q1->_pHead->_pNext;//必须加，否则因为释放了ptr，ptr下次就进不来了 } //此时，q1中仅剩一个元素，且为栈顶元素 QueuePop(s->q1); } ptr2 = s->q2->_pHead->_pNext;//q2的第一个有效节点 //出完之后将q2中的元素再移回去保证，q2始终为空 while (ptr2) { DataType data = QueueFront(s->q2); QueuePop(s->q2); QueuePush(s->q1, data); ptr2 = s->q2->_pHead->_pNext;//必须加，否则因为释放了ptr，ptr下次就进不来了 } } //获取栈顶元素 DataType StackTop(PStack s) { assert(s); DataType Top = 0; Node* ptr2 = NULL; if (QueueEmpty(s->q1) && QueueEmpty(s->q2)) { printf("栈已空!!!\n"); return 0; } //如果q1不为空，q2为空，将q1元素搬移到q2只剩一个，q1队头就是栈的栈顶 if (!QueueEmpty(s->q1) && QueueEmpty(s->q2)) { Node* ptr = s->q1->_pHead->_pNext;//q1的第一个有效节点 while (ptr->_pNext) { DataType data = QueueFront(s->q1); QueuePop(s->q1); QueuePush(s->q2, data); ptr = s->q1->_pHead->_pNext;//必须加，否则因为释放了ptr，ptr下次就进不来了 } //此时，q1中仅剩一个元素，且为栈顶元素 Top = QueueFront(s->q1); QueuePop(s->q1); QueuePush(s->q2, Top); } ptr2 = s->q2->_pHead->_pNext;//q2的第一个有效节点 //出完之后将q2中的元素再移回去保证，q2始终为空 while (ptr2) { DataType data = QueueFront(s->q2); QueuePop(s->q2); QueuePush(s->q1, data); ptr2 = s->q2->_pHead->_pNext;//必须加，否则因为释放了ptr，ptr下次就进不来了 } return Top; }

test.c

#include "StackAndInterview.h" #include <Windows.h> void Test4() { Stack s; Queue q1;//先给两个队列 Queue q2; s.q1 = &q1; s.q2 = &q2; StackInit(&s); printf("Top:%d\n",StackTop(&s)); StackPush(&s, 5); StackPush(&s, 4); StackPush(&s, 3); printf("Top:%d\n", StackTop(&s)); StackPop(&s); printf("Top:%d\n", StackTop(&s)); StackPush(&s, 7); StackPush(&s, 8); StackPush(&s, 9); printf("Top:%d\n", StackTop(&s)); } int main() { //Test1();//面试题1方法1 //Test2();//面试题方法2 //Test3();//面试题2 Test4();//面试题3 system("pause"); return 0; }