面試題·棧和隊列的相互實現·詳解

A. 用隊列實現棧

用隊列實現棧
實現代碼如下
看著是隊列，其實實際實現更接近數組模擬

typedef struct {int* queue1;    // 第一個隊列int* queue2;    // 第二個隊列int size;       // 棧的大小int front1, rear1, front2, rear2;  // 兩個隊列的首尾指針
} MyStack;//初始化棧
MyStack* myStackCreate() {MyStack* stack = (MyStack*)malloc(sizeof(MyStack));stack->queue1 = (int*)malloc(sizeof(int) * 100);stack->queue2 = (int*)malloc(sizeof(int) * 100);stack->size = 0;stack->front1 = stack->rear1 = 0;stack->front2 = stack->rear2 = 0;return stack;
}//將元素 x 壓入棧頂 
void myStackPush(MyStack* obj, int x) {obj->queue1[obj->rear1++] = x;  // 將元素加入 queue1 的尾部obj->size++;
}//移除并返回棧頂元素 
int myStackPop(MyStack* obj) {int i;// 將 queue1 中的元素(除了最后一個)轉移到 queue2 中for (i = 0; i < obj->size - 1; i++) {obj->queue2[obj->rear2++] = obj->queue1[obj->front1++];}int top = obj->queue1[obj->front1++];  // 獲取棧頂元素obj->size--;// 交換 queue1 和 queue2,為下次操作做準備int* temp = obj->queue1;obj->queue1 = obj->queue2;obj->queue2 = temp;obj->front1 = 0;obj->rear1 = obj->size;obj->front2 = 0;obj->rear2 = 0;return top;
}//返回棧頂元素 
int myStackTop(MyStack* obj) {int i;// 將 queue1 中的元素轉移到 queue2 中for (i = 0; i < obj->size; i++) {obj->queue2[obj->rear2++] = obj->queue1[obj->front1++];}int top = obj->queue2[obj->rear2 - 1];  // 獲取棧頂元素// 交換 queue1 和 queue2,為下次操作做準備int* temp = obj->queue1;obj->queue1 = obj->queue2;obj->queue2 = temp;obj->front1 = 0;obj->rear1 = obj->size;obj->front2 = 0;obj->rear2 = 0;return top;
}//如果棧是空的,返回 true;否則,返回 false 
bool myStackEmpty(MyStack* obj) {return obj->size == 0;
}void myStackFree(MyStack* obj) {free(obj->queue1);free(obj->queue2);free(obj);
}

雖然注釋已經夠詳細了，但是我們還是來逐步分析一下
代碼實際上并沒有使用鏈式隊列，而是使用了兩個固定大小的數組來模擬棧的行為。

首先，我們定義了一個結構體MyStack，它包含兩個整數數組queue1和queue2（其實在這里，它們更像棧，因為數組是按照后進先出的順序使用的），以及它們的前后端指針和棧的大小。

myStackCreate

這個函數用于初始化棧。它分配了MyStack結構體的內存，并為兩個數組分配了內存。然后，它初始化了所有的指針和大小為0。

myStackPush
這個函數用于將元素壓入棧頂。它簡單地將元素添加到queue1的尾部，并更新rear1指針和棧的大小。

myStackPop
這個函數用于移除并返回棧頂元素。但是，這里有一個問題：它實際上將整個queue1（除了最后一個元素）轉移到了queue2，然后返回了queue1的最后一個元素。之后，它交換了兩個數組，并重置了所有的指針。這樣做在每次pop操作時都非常低效，因為它涉及到大量元素的移動。

一個更高效的方法是，每次pop時，只需要記錄queue1的最后一個元素（即棧頂元素），然后將其余元素（如果有的話）從queue1轉移到queue2，并交換兩個隊列的引用。但是，在交換后，不需要重置所有的指針，因為queue2的front2和rear2已經指向了正確的位置。

myStackTop
這個函數與myStackPop非常相似，但是它返回棧頂元素而不移除它。然而，與myStackPop一樣，它也涉及到了不必要的元素移動和數組交換。

myStackEmpty
這個函數檢查棧是否為空，通過檢查棧的大小是否為0來實現。

myStackFree
這個函數釋放了棧所使用的所有內存。

改進建議

避免不必要的元素移動：在pop和top操作中，只需要移動除了棧頂元素之外的其他元素。
減少指針重置：在交換數組后，不需要總是重置所有的前端和后端指針。
考慮使用真正的鏈式隊列：如果你想要一個鏈式棧，你應該使用鏈式隊列（通過節點連接）而不是數組。鏈式實現會更靈活，并且在處理大量數據時可能更高效。
錯誤處理：在分配內存時，應該檢查malloc是否成功，并在失敗時返回錯誤或進行其他處理。
邊界檢查：在pop和top操作中，應該檢查棧是否為空，以避免訪問空指針或未定義的內存。
優化內存使用：如果你知道棧的大小上限，可以使用固定大小的數組。但是，如果你想要一個可以動態增長的棧，那么鏈式實現可能更合適。

下面是優化后的代碼

在這個版本中，我們使用了一個指針queue和兩個布爾值（但實際上我們只需要一個，因為!isQueue1就等同于isQueue2）來追蹤當前正在使用的隊列。當棧滿時，我們嘗試擴容，并將元素從queue2（如果它包含元素）復制到queue1。我們還添加了一個檢查，以便在queue1使用了超過一半的空間時，將元素從queue1復制到queue2，并切換隊列，以保持兩個隊列之間的負載均衡。

我們還在myStackFree函數中釋放了內存，并處理了malloc和realloc可能返回NULL的情況。

#include <stdlib.h>  
#include <stdbool.h>  #define INITIAL_CAPACITY 100  typedef struct {  int* queue;  int capacity;  int top;  bool isQueue1; // 表示當前正在使用queue1還是queue2  
} MyStack;  MyStack* myStackCreate() {  MyStack* obj = (MyStack*)malloc(sizeof(MyStack));  if (!obj) return NULL;  obj->queue = (int*)malloc(INITIAL_CAPACITY * sizeof(int));  if (!obj->queue) {  free(obj);  return NULL;  }  obj->capacity = INITIAL_CAPACITY;  obj->top = -1; // 棧頂指針初始化為-1，表示空棧  obj->isQueue1 = true; // 初始時使用queue1  return obj;  
}  void myStackPush(MyStack* obj, int x) {  if (obj->top == obj->capacity - 1) { // 棧滿，擴容  int newCapacity = obj->capacity * 2;  int* newQueue = (int*)realloc(obj->isQueue1 ? obj->queue : (obj->queue - INITIAL_CAPACITY), newCapacity * sizeof(int));  if (!newQueue) return; // 擴容失敗  obj->queue = newQueue + (obj->isQueue1 ? 0 : INITIAL_CAPACITY); // 調整指針，確保obj->queue始終指向當前使用的隊列  obj->capacity = newCapacity;  // 如果之前使用queue2，現在切換回queue1，則需要復制數據  if (!obj->isQueue1) {  for (int i = 0; i <= obj->top; i++) {  obj->queue[i] = obj->queue[i + INITIAL_CAPACITY];  }  obj->isQueue1 = true; // 切換回queue1  }  }  obj->queue[++obj->top] = x; // 壓棧  
}  int myStackPop(MyStack* obj) {  if (obj->top == -1) return -1; // 棧空  int x = obj->queue[obj->top--]; // 彈出棧頂元素  // 如果queue1已經使用了超過一半的空間，且queue2是空的，則考慮將queue1的元素移到queue2，并切換隊列  if (obj->isQueue1 && obj->top > obj->capacity / 4) {  for (int i = 0; i <= obj->top; i++) {  obj->queue[i + INITIAL_CAPACITY] = obj->queue[i];  }  obj->isQueue1 = false; // 切換到queue2  obj->top += INITIAL_CAPACITY; // 更新top指針  }  return x;  
}  int myStackTop(MyStack* obj) {  if (obj->top == -1) return -1; // 棧空  return obj->queue[obj->top]; // 返回棧頂元素  
}  bool myStackEmpty(MyStack* obj) {  return obj->top == -1; // 檢查棧是否為空  
}  void myStackFree(MyStack* obj) {  if (obj) {  free(obj->queue - (obj->isQueue1 ? 0 : INITIAL_CAPACITY)); // 釋放隊列內存  free(obj);  }  
}

B. 用棧實現隊列

用棧實現隊列

那用鏈棧來實現一下看看

// 鏈表節點定義  
typedef struct Node {  int data;  struct Node* next;  
} Node;  // 棧結構定義
typedef struct Stack {  Node* top;  int size;  
} Stack;  // MyQueue結構體定義，包含兩個棧  
typedef struct MyQueue {  Stack* stack1;  Stack* stack2;  
} MyQueue;  
// 創建新的節點  
Node* createNode(int data) {  Node* newNode = (Node*)malloc(sizeof(Node));  if (!newNode) {  perror("Memory allocation failed");  exit(EXIT_FAILURE);  }  newNode->data = data;  newNode->next = NULL;  return newNode;  
}  // 初始化棧  
Stack* createStack() {  Stack* stack = (Stack*)malloc(sizeof(Stack));  if (!stack) {  perror("Memory allocation failed");  exit(EXIT_FAILURE);  }  stack->top = NULL;  stack->size = 0;  return stack;  
}  // 壓棧操作  
void push(Stack* stack, int data) {  Node* newNode = createNode(data);  newNode->next = stack->top;  stack->top = newNode;  stack->size++;  
}  // 出棧操作  
int pop(Stack* stack) {  if (stack->size == 0) {  printf("Stack is empty.\n");  exit(EXIT_FAILURE);  }  Node* temp = stack->top;  int data = temp->data;  stack->top = temp->next;  free(temp);  stack->size--;  return data;  
}  // 查看棧頂元素  
int peek(Stack* stack) {  if (stack->size == 0) {  printf("Stack is empty.\n");  exit(EXIT_FAILURE);  }  return stack->top->data;  
}  // 判斷棧是否為空  
int isEmpty(Stack* stack) {  return stack->size == 0;  
}  // 釋放棧內存  
void freeStack(Stack* stack) {  Node* current = stack->top;  Node* temp;  while (current != NULL) {  temp = current;  current = current->next;  free(temp);  }  free(stack);  
}MyQueue* myQueueCreate() {  MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));  if (!queue) {  perror("Memory allocation failed for MyQueue");  exit(EXIT_FAILURE);  }  queue->stack1 = createStack();  queue->stack2 = createStack();  return queue;  
}  void myQueuePush(MyQueue* queue, int data) {  push(queue->stack1, data);  
}  int myQueuePop(MyQueue* queue) {  if (isEmpty(queue->stack2)) {  while (!isEmpty(queue->stack1)) {  push(queue->stack2, pop(queue->stack1));  }  }  if (isEmpty(queue->stack2)) {  return -1; // 隊列為空，無法彈出元素  }  return pop(queue->stack2);  
}  int myQueuePeek(MyQueue* queue) {  if (isEmpty(queue->stack2)) {  while (!isEmpty(queue->stack1)) {  push(queue->stack2, pop(queue->stack1));  }  }  if (isEmpty(queue->stack2)) {  return -1; // 隊列為空，無法查看隊首元素  }  return peek(queue->stack2);  
}  bool myQueueEmpty(MyQueue* queue) {  return isEmpty(queue->stack1) && isEmpty(queue->stack2);  
}  void myQueueFree(MyQueue* queue) {  freeStack(queue->stack1);  freeStack(queue->stack2);  free(queue);  
}

這段代碼實現了一個基于兩個棧的隊列結構 MyQueue。下面我們來逐步解釋這段代碼:

鏈表節點定義：
- Node 結構體定義了鏈表節點, 包含一個整數值 data 和指向下一個節點的指針 next。
棧結構定義：
- Stack 結構體定義了一個棧, 包含指向棧頂元素的指針 top 和棧的大小 size。
MyQueue 結構體定義：
- MyQueue 結構體包含兩個 Stack 指針, stack1 和 stack2, 用于實現隊列的功能。
創建新的節點:
- createNode 函數用于創建一個新的鏈表節點, 并分配內存。如果內存分配失敗, 則輸出錯誤信息并退出程序。
初始化棧:
- createStack 函數用于創建一個新的棧, 將棧頂指針設為 NULL, 并將棧的大小設為 0。如果內存分配失敗, 則輸出錯誤信息并退出程序。
壓棧操作:
- push 函數用于將一個元素壓入棧, 首先創建一個新節點, 然后將新節點的 next 指針指向當前棧頂元素, 最后更新棧頂指針和棧的大小。
出棧操作:
- pop 函數用于從棧中彈出一個元素, 首先檢查棧是否為空, 如果為空則輸出錯誤信息并退出程序。然后獲取棧頂元素的數據, 更新棧頂指針, 釋放棧頂元素的內存, 并更新棧的大小。
查看棧頂元素:
- peek 函數用于查看棧頂元素, 首先檢查棧是否為空, 如果為空則輸出錯誤信息并退出程序。然后返回棧頂元素的數據。
判斷棧是否為空:
- isEmpty 函數用于判斷棧是否為空, 返回棧的大小是否為 0。
釋放棧內存:
- freeStack 函數用于釋放棧占用的內存, 遍歷鏈表并逐個釋放每個節點的內存, 最后釋放棧本身的內存。
創建 MyQueue:
- myQueueCreate 函數用于創建一個新的 MyQueue 對象, 分配內存并初始化兩個 Stack 對象。如果內存分配失敗, 則輸出錯誤信息并退出程序。
入隊操作:
- myQueuePush 函數用于將一個元素入隊, 直接將元素壓入 stack1 即可。
出隊操作:
- myQueuePop 函數用于從隊列中出隊一個元素。首先檢查 stack2 是否為空, 如果為空則將 stack1 中的元素全部彈出并壓入 stack2。然后從 stack2 中彈出并返回隊首元素。如果兩個棧都為空, 則返回 -1 表示隊列為空。
查看隊首元素:
- myQueuePeek 函數用于查看隊首元素。與出隊操作類似, 首先檢查 stack2 是否為空, 如果為空則將 stack1 中的元素全部彈出并壓入 stack2。然后返回 stack2 的棧頂元素。如果兩個棧都為空, 則返回 -1 表示隊列為空。
判斷隊列是否為空:
- myQueueEmpty 函數用于判斷隊列是否為空, 返回 stack1 和 stack2 是否同時為空。
釋放 MyQueue 內存:
- myQueueFree 函數用于釋放 MyQueue 對象占用的內存, 首先釋放 stack1 和 stack2 的內存, 然后釋放 MyQueue 對象本身的內存。