剑指offer学习笔记：2.3 数据结构

2020-06-17 本文已影响0人小逗比儿

2.3 数据结构

数据结构一直都是技术面试的重点，大部分面试都是围绕数组，字符串，链表，树，栈以及队列这几种常见数据结构展开的。
数组和字符串是两种最基本的数据结构，他们用连续的内存存储数字和字符。链表和树是面试中出现频率最高的数据结构。由于操作链表和操作树需要大量的指针，需要留意程序的鲁棒性。栈是一个与递归关系密切的数据结构，队列与广度优先遍历关系密切。理解这两种结构可以帮我们解决很多算法。

2.3.1 数组

数组是一块连续的内存，需要预先分配好，因此空间效率不是很好。但是因为它是连续空间，因此可以在O(1)时间内实现读写元素，时间效率很高。
为了解决数组空间效率不高的问题，人们设计实现了多种动态数组，比如C++的STL中的vector。为避免浪费，我们会先为数组分配较小空间，然后往数组中添加元素，当空间不够时，我们会重新分配一个较大的空间（vector分配为原来的两倍），把之前的数据复制到新空间中。
在c++中，数组和指针是两个相互关联又区别的概念。当我们声明一个数组，其名字也是一个指针，该指针指向数组的第一个元素。但是注意，c++中没有记录数组的大小，因此通过指针访问数组元素时，要确保没有访问越界（一般通过sizeof(数组)/sizeof(数据类型) )来判断数组中元素的个数。

面试题：运行下面代码，判断输出是什么

int GetSize(int data[])
{  
   return sizeof(data); 
}
int _tmain(int argc, _TCHAR* argv[])
{
   int data1[] = {1, 2, 3, 4, 5};
   int size1 = sizeof(data1);
   int* data2 = data1;
   int size2 = sizeof(data2);
   int size3 = GetSize(data1);
   cout << size1 <<  "," << size2 << "," << size3 << endl;
}

答：20,4,4

面试题3：二维数组中查找

在一个二维数组中，每一行都按从左到右的递增顺序排列，每一列都按从上到下的递增顺序排列。请完整一个函数，输入这样的二维数组和一个整数，判断数组中是否含有该整数。例在如下数组中，查找数字7，则返回true。查找数字5，则返回false
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
int main() {
   int arr[][4] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
   int result = 19;
   bool found = false;
   if (sizeof(arr) == 0 || sizeof(arr[0]) == 0)
   {
      return found;
  }
   int row = sizeof(arr) / sizeof(arr[0]);
   int col = sizeof(arr[0]) / sizeof(arr[0][0]);
   int i = row - 1, j = 0;
   while(i >= 0 && j < col)
   {
       if (arr[i][j] == result)
       {
           found = true;
           break;
       }
       if (arr[i][j] > result)
       {
           i--;
           continue;
       }
       if (arr[i][j] < result)
       {
           j++;
           continue;
       }
   }
   cout << found << endl;
   return 0;
}

解题思路：从左下角或右上角出发开始遍历，当当前元素等于目标元素，找到。以左下角为例，当当前元素小于目标元素，因为当前元素为当前列最大元素，因此该列可以舍弃，沿行的方向前进，对当前行下一列元素进行判断。当当前元素大于目标函数，因为当前元素为当前行最小元素，因此该行可以舍弃，沿列的方向，对当前列上一行元素进行判断。注意对空数组容错处理。
注意数组作为参数进行传递一定要带上长度。

2.3.2 字符串

c++中字符串以字符’\0'结尾，这样我们就能方便的找到字符串的尾部。但是因为这个特点，每个字符串会额外多占用一个字节，稍不留神就会造成字符串的越界。比如char str[10]; strcp(str, "0123456789")。在上一节笔记https://www.jianshu.com/p/1cae1e241ac8
中记录过strcp函数特点，这段代码会发生溢出。
为了节约内存，c++会被常量字符串放在单独的一个内存区域（常量存储区）。当几个指针赋值给相同的常量字符串时，他们实际上会指向同一块内存区域。但是用常量内存初始化数组，情况确有所不同。

面试题：

int _tmain()
{
   char str1[] = "hello world";
   char str2[] = "hello world";
   char* str3 = "hello world";
   char* str4 = "hello world";
   if(str1 == str2)
     cout << "str1 and str2 are same" << endl;
   else
     cout << "str1 and str2 are not same" << endl;
   if(str3 == str4)
     cout << "str3 and str4 are same" << endl;
   else
     cout << "str3 and str4 are not same" << endl;
   return 0;
}

答：str1 and str2 are not same
str3 and str4 are same

str1和str2是两个字符串数组，我们会为他们分配长度为12个字节的空间，并把“hello world”的内容分别复制到两个数组中去。这是两个初始位置不同的数组，因此str1和str2的值也不相同。str3和str4是两个指针，我们无需为他们分配内存存储字符串内容，他们只需要指向“hello world”所在区域就行了，所以是相同的。

面试题4：替换空格

请实现一个函数，把字符串中的每个空格替换成“%20”。例如“we are happy”替换成“we20%are20%happy”，要求在原字符串上做替换，并且保证输入的字符串后有足够的空间。

int main() {
   char str[] = "test test   test ";
   if(sizeof(str) == 0)
   {
       cout << "";
       return 0;
   }
   int end = sizeof(str) / sizeof(str[0]);
   int newend = end;
   int blank_num = 0;
   for(int i = 0; i < end; i++)
   {
      if(str[i] == ' ')
      {
          blank_num++;
      }
   }
   newend = end + 2 * blank_num;
   while(blank_num >= 0 && newend >= 0 && end >= 0)
   {
       if (str[end] == ' ')
       {
           str[newend--] = '0';   // 一边赋值一边减，代码简洁很多
           str[newend--] = '2';
           str[newend--] = '%';
           end--;
           blank_num--;
       } else
       {
           str[newend--] = str[end];
           end--;
       }
   }
   cout << str << endl;
   return 0;
}

考察思路：合并两个数组（包括字符串），如果从前往后复制每个数字或者字符，需要重复移动数字或字符多次，那么我们可以考虑从后往前复制，减少移动次数，提高效率。

解题思路：先遍历字符串，找出空格的个数，最终字符串长度应该是原字符串长度+空格数*2。确定字符串后有足够空间后，设定新指针指向新字符串尾部，另一个指针指向当前字符串尾部，进行插入替换。注意空串，只有一个空格字符串，多个连续空格字符串和没有空格字符串几种特殊情况。

相关题目
有两个排序的数组A1和A2，内存在A1的末尾有足够的空间容纳A2。请实现一个函数，把A2中所有数字插入A1中，并且所有数组是有序的。

int main() {
   int A1[10] = {1, 3, 5, 7, 19};
   int A2[] = {0, 2, 6, 10, 20};
   if(sizeof(A1) == 0)
   {
       if (sizeof(A2) == 0)
       {
           return 0;
       }
       int n2 = sizeof(A2) / sizeof(A2[0]);
       for(int i = 0; i < n2; i++)
       {
           A1[i] = A2[i];
       }
       return 0;
   }
   if (sizeof(A2) == 0)
   {
       return 0;
   }
   int A1_index = 4;
   int A2_index = sizeof(A2) / sizeof(A2[0]) - 1;
   int newend = A1_index + A2_index + 1;
   while(newend >= 0)
   {
       // cout << A1_index << " " << A2_index << endl;
       if (A1_index <= -1)
       {
           A1[newend--] = A2[A2_index];
           A2_index--;
           continue;
       }
       if (A2_index <= -1)
       {
           A1[newend--] = A1[A1_index];
           A1_index--;
           continue;
       }
       if (A1[A1_index] > A2[A2_index])
       {
           A1[newend--] = A1[A1_index--];
       } else
       {
           A1[newend--] = A2[A2_index--];
       }
   }
   return 0;
}

2.3.3 链表

链表结构简单，他是由指针把若干节点连接在一起的链状结构。链表不需要额外分配内存，每添加一个新节点，则重新分配内存，并将前一个节点的指针指向新分配的内存。

面试题：实现两个函数 1.在链表尾添加一个节点的函数 2.在链表中找到含有该值的节点，并删除

//
// Created by Xue,Lin on 2020/6/13.
//
#ifndef UNTITLED_LIST_OFFER_H
#define UNTITLED_LIST_OFFER_H
// 剑指offer上关于链表的题目
// 先定义一个链表结构
struct ListNode
{
   int val;
   ListNode* next;
   ListNode(int val) {this->val = val; next = NULL;}
};
// 定义一个传入数组，构建链表的函数，返回链表的头节点
ListNode* CreateList(int* arr, int n)
{
   if (arr == NULL)
   {
       return NULL;
   }
   ListNode* head = new ListNode(arr[0]);
   ListNode* p = head;
   for(int i = 1; i < n; i++)
   {
       ListNode* node = new ListNode(arr[i]);
       head->next = node;
       head = node;
   }
   head->next = NULL;
   return p;
}
void PrintList(ListNode* pHead)
{
   if(pHead == NULL)
   {
       return;
   }
   while(pHead != NULL)
   {
       cout << pHead->val << " ";
       pHead = pHead->next;
   }
   cout << endl;
   return;
}
// 在链表尾部增加新节点
void AddToTail(ListNode** pHead, int val)
{
   ListNode* node = new ListNode(val);
   if (*pHead == NULL)
   {
       *pHead = node;
   } else
   {
       ListNode* head = *pHead;
       while(head->next != NULL)
       {
           head = head->next;
       }
       head->next = node;
   }
}
// 在链表中找到元素，并删除的代码
void RemoveNode(ListNode** pHead, int val)
{
   if (pHead == NULL )
   {
       return;
   }
   ListNode* head = *pHead;
   if (head->val == val)
   {
       *pHead = (*pHead)->next;
       delete head;
       head = NULL;
       return;
   }
   bool found = false;
   while(head->next != NULL)
   {
       if (head->next->val == val)
       {
           found = true;
           break;
       }
       head = head->next;
   }
   if (found == false)
   {
       return;
   } else
   {
       ListNode* deletenode = head->next;
       head->next = head->next->next;
       delete deletenode;
       deletenode = NULL;
   }
   return;
}
#endif //UNTITLED_LIST_OFFER_H
// main
   int arr[] = {1, 3, 5, 7, 19};
   ListNode* head = CreateList(arr, 5);
   AddToTail(&head, 20);
   PrintList(head);
   AddToTail(&head, 30);
   PrintList(head);
   RemoveNode(&head, 5);
   PrintList(head);
   RemoveNode(&head, 1);
   PrintList(head);

面试题5：从头到尾打印链表

输入一个链表的头节点，从尾到头打印每个节点的值

#include<stack>
void PrintReverse(ListNode* pHead)
{
   // 循环，栈
   if (pHead == NULL)
   {
       return;
   }
   stack<int> list_val;
   while(pHead != NULL)
   {
       list_val.push(pHead->val);
       pHead = pHead->next;
   }
   while(!list_val.empty())
   {
       cout << list_val.top() << " ";
       list_val.pop();
   }
   cout << endl;
}
void main(){
   int arr[] = {1, 3, 5, 7, 19};
   ListNode* head = CreateList(arr, 5);
   AddToTail(&head, 20);
   PrintReverse(head);
   AddToTail(&head, 30);
   PrintReverse(head);
   RemoveNode(&head, 5);
   PrintReverse(head);
   RemoveNode(&head, 1);
   PrintReverse(head);
}

解题思路：遍历链表的时候，一定是从头到尾的。实现从尾到头输出，可以想到借用其余数据结构。栈作为先进后出的数据结构，是很好的选择。而能使用栈，一般情况下也就可以用递归来实现。因此本题也有递归解法。但是当链表很长，函数调用层次较深，递归容易造成函数调用栈溢出，因此比较推荐基于栈的循环。
递归写法：

void PrintReverseRec(ListNode* pHead)
{
    // 递归
    if (pHead == NULL)
    {
        return;
    }
    PrintReverseRec(pHead->next);
    cout << pHead->val << " ";
    return;
}

【c++拾遗】 c++值传递，指针传递和引用传递
参考链接 https://www.cnblogs.com/dingxiaoqiang/p/8012578.html

值传递：形参是实参的拷贝。改变形参并将不会影响实参的值。
指针传递：形参为指向实参地址的指针，当改变形参指向内存的内容时，即相当于对实参进行操作
引用传递：形参相当于实参的别名，任何对形参的操作都相当于是对实参进行操作。在引用传递过程中，尽管被调函数的形参被作为局部变量被放到栈中，但是这时候放进来的是主函数传递实参的地址。被调函数对形参的操作都被处理成间接寻址，即通过存储在栈中实参的地址找到实参进行操作。

2.3.4 树

前序遍历，中序遍历，后序遍历（递归和非递归），层次遍历。
二叉检索树的中序遍历，为递增序列。
二叉树的另外两个特例为堆和红黑树。堆分为最大堆和最小堆。在最大堆中根节点的值最大，在最小堆中根节点的值最小。很多找最大值和最小值的问题都可以用堆来解决。
红黑树就是把树中节点定义为红，黑两种颜色，并通过规则确保从根节点到叶节点的最长路径不超过最短路径的两倍。在c++的stl中，set、multiset、map、multimap等数据结构都是基于红黑树实现的。

面试题：树的前中后序遍历（递归与非递归），层次遍历 https://www.cnblogs.com/bigsai/p/11393609.html

//
// Created by Xue,Lin on 2020/6/14.
//
#ifndef UNTITLED_TREE_OFFER_H
#define UNTITLED_TREE_OFFER_H
#include<queue>
using namespace std;
// 剑指offer 树
// 想定义一个节点结构
struct TreeNode{
   int val;
   TreeNode* left;
   TreeNode* right;
   TreeNode(int val) {this->val = val; this->left = NULL; this->right = NULL;}
};
// 定义一个根据数组构建树的函数，传递数组空节点用NULL
TreeNode* createTree(char* arr, int n)
{
   if (arr == NULL || n == 0)
   {
       return NULL;
   }
   TreeNode* root = new TreeNode(arr[0] - '0');
   queue<TreeNode*> tree;
   tree.push(root);
   int i = 1;
   while(!tree.empty() && i < n)
   {
       TreeNode* head = tree.front();
       if (arr[i] == '#')
       {
           i++;
       } else {
           TreeNode* tmp = new TreeNode(arr[i++] - '0');
           head->left = tmp;
           tree.push(tmp);
       }
       if (i < n) {
           if (arr[i] == '#')
           {
               i++;
           } else{
               TreeNode* tmp = new TreeNode(arr[i++] - '0');
               head->right = tmp;
               tree.push(tmp);
           }
       }
       tree.pop();
   }
   return root;
}
// 前序遍历，非递归
void preOrder(TreeNode* root)
{
   if (root == NULL)
   {
       return;
   }
   stack<TreeNode*> tree;
   tree.push(root);
   while(!tree.empty())
   {
       TreeNode* tmp = tree.top();
       tree.pop();
       cout << tmp->val << " ";
       if(tmp->right)
       {
           tree.push(tmp->right);
       }
       if(tmp->left)
       {
           tree.push(tmp->left);
       }
   }
}
// 前序遍历，递归
void preOrderRec(TreeNode* root)
{
   if (root == NULL)
   {
       return;
   }
   cout << root->val << " ";
   preOrderRec(root->left);
   preOrderRec(root->right);
   return;
}
// 中序遍历，非递归
// 入所有左节点，当没有左节点可入，出栈栈顶，输出值，同时，入栈顶元素的右节点
void midOrder(TreeNode* root)
{
   if (root == NULL)
   {
       return;
   }
   stack<TreeNode*> tree;
   while(!tree.empty() || root != NULL)
   {
       if(root != NULL)
       {
           tree.push(root);
           root = root->left;
       } else {
           TreeNode* tmp = tree.top();
           tree.pop();
           cout << tmp->val << " ";
           root = tmp->right;
       }
   }
   return;
}
// 中序遍历，递归
void midOrderRec(TreeNode* root)
{
   if (root == NULL)
   {
       return;
   }
   midOrderRec(root->left);
   cout << root->val << " ";
   midOrderRec(root->right);
   return;
}
// 后序遍历，非递归
// 同样，先一直访问左节点，直到左节点为空。
// 判断栈顶元素是否有右节点，如果没有右孩子，pop
// 如果有右孩子，右孩子入栈
// 当节点被第二次访问，则直接pop
// 与前序和中序相比，后续遍历还需要记录栈中节点被访问次数
void afterOrder(TreeNode* root)
{
   if (root == NULL)
   {
       return;
   }
   stack<pair<TreeNode*, int>> tree;
   while(!tree.empty() || root != NULL)
   {
       if (root != NULL)
       {
           tree.push(make_pair(root, 0));
           root = root->left;
       } else {
           pair<TreeNode*, int> tmp = tree.top();
           if (tmp.first->right == NULL || tmp.second == 1)
           {
               tree.pop();
               cout << tmp.first->val << " ";
           } else {
               tmp.second = 1;
               tree.pop();
               tree.push(tmp);
               root = tmp.first->right;
           }
       }
   }
   return;
}
// 后序遍历，递归
void afterOrderRec(TreeNode* root)
{
   if (root == NULL)
   {
       return;
   }
   afterOrderRec(root->left);
   afterOrderRec(root->right);
   cout << root->val << " ";
   return;
}
// 层次遍历
void levelOrder(TreeNode* root)
{
   if (root == NULL)
   {
       return;
   }
   queue<TreeNode*> tree;
   tree.push(root);
   while(!tree.empty())
   {
       TreeNode* tmp = tree.front();
       cout << tmp->val << " ";
       if (tmp->left)
       {
           tree.push(tmp->left);
       }
       if (tmp->right)
       {
           tree.push(tmp->right);
       }
       tree.pop();
   }
   return;
}
#endif //UNTITLED_TREE_OFFER_H
int main() {
   char arr[] = {'1', '3', '5', '#', '7', '#', '6'};
   TreeNode* root = createTree(arr, 7);
   preOrder(root);
   cout << "\t";
   preOrderRec(root);
   cout << endl;
   midOrder(root);
   cout << "\t";
   midOrderRec(root);
   cout << endl;
   afterOrder(root);
   cout << "\t";
   afterOrderRec(root);
   cout << endl;
   levelOrder(root);
}

面试题6：重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，重建该二叉树。假设前序遍历和中序遍历结果中不包含重复数字。假设输入前序遍历{1,2,4,7,3,5,6,8}，中序遍历{4,7,2,1,5,3,8,6}，重建该二叉树，并输出其头结点。
leetcode链接 https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 递归调用函数
TreeNode* buildTree(vector<int>& preorder, int prebegin, int preend, vector<int>& inorder, int inbegin, int inend)
{
   // 通过重载写递归调用函数，preorder为完整前序遍历vector，
   // prebegin为本次构建树前序遍历队列起始，preend为本次构建树前序遍历队列终止
   // inorder为完整中序遍历vector
   // inpre为本次构建树中序遍历起始，inend为本次构建树中序遍历终止>

   // 这里需要终止条件
   if (prebegin >= preend  || preend > preorder.size() || prebegin >= preorder.size())
   {
       // cout << "prebegin:" << prebegin << "preend: "
       return NULL;
   }
   TreeNode* root = new TreeNode(preorder[prebegin]);
   // 定义左子树长度和右子树长度，由于根节点已经建立，总长度减1
   int left_length = inbegin;
   for(; left_length < inend; left_length++)
   {
       if (inorder[left_length] == preorder[prebegin])
       {
           break;
       }
   }
   left_length = left_length - inbegin;
   // cout << left_length << endl;
   root->left = buildTree(preorder, prebegin + 1, prebegin + 1 + left_length, inorder, inbegin, inbegin + left_length);
   root->right = buildTree(preorder, prebegin + 1 + left_length, preend, inorder, inbegin + left_length + 1, inend);
   return root;
}
// 根据中序遍历和前序遍历重建二叉树
// 前序遍历为根左右，中序遍历为左右根。
// 前序遍历当前节点为树的根节点，找到该节点在中序遍历中的位置，就可以将中序遍历分为左子树的中序遍历和右子树的中序遍历
// 根据中序遍历切割长度，又可以将前序遍历切割成左子树的前序遍历和右子树的前序遍历
// 进而用递归完成整棵树的重建
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
   if(preorder.size() == 0 || inorder.size() == 0)
   {
       return NULL;
   }
   // 注意这里的参数传递是左区间值有效，右区间值无效【 ）
   TreeNode* root = buildTree(preorder, 0, preorder.size(), inorder, 0, inorder.size());
   return root;
}
};

二叉树根据前序和中序或根据后序和中序可以重建，根据前序和后序构建不唯一。

相关题目：根据后序遍历和中序遍历重建二叉树
leetcode链接 https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

>/**
> * Definition for a binary tree node.
> * struct TreeNode {
> *     int val;
> *     TreeNode *left;
> *     TreeNode *right;
> *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
> * };
> */
>class Solution {
>public:
>    // 重建递归函数
>    // 跟前序遍历相反，后序遍历为左右根，因此后序遍历最后一个元素为当前根结点，找到中序遍历中根结点位置，可以将后序遍历和中序遍历分为左右两个子树对应的数组
>    TreeNode* buildTree(vector<int>& inorder, int inbegin, int inend, vector<int>& postorder, int postbegin, int postend)
>    {
>        // cout << postbegin << "\t" << postend << "\t" << inbegin << "\t" << inend << endl;
>        if (postbegin >= postend || postbegin < 0 || postbegin >= postorder.size() || postend > postorder.size() || postend < 1)
>        {
>            return NULL;
>        }
>        TreeNode* root = new TreeNode(postorder[postend - 1]);
>        int left_length = 0;
>        for(int i = inbegin; i < inend; i++)
>        {  
>            if (inorder[i] == postorder[postend - 1])
>            {
>                break;
>            }
>            left_length++;
>        }
>        cout << left_length << endl;
>        root->left = buildTree(inorder, inbegin, inbegin + left_length, postorder, postbegin, postbegin + left_length);
>        root->right = buildTree(inorder, inbegin + left_length + 1, inend, postorder, postbegin + left_length, postend -1);
>        return root;
>    }
>    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
>        cout << inorder.size() << "\t" << postorder.size() << endl;
>        TreeNode* root = buildTree(inorder, 0, inorder.size(), postorder, 0, postorder.size());
>        return root;
>    }
>};

根据前序遍历和后序遍历重建一棵可能的二叉树
leetcode链接 https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/

思路：由于前序和后序遍历不能确定节点的左右关系，因此构建树不唯一。每次递归，前序遍历的第一个元素为当前根节点，假设前序遍历的第二个节点为左子树，找到这个节点在后序遍历中的位置，长度即为左子树长度。其余思路和上面两种重建相同。

2.3.5 栈和队列

栈先进后出，队列先进先出。宽度优先遍历用队列，深度优先遍历用栈。

面试题7：用两个栈实现队列

用两个栈实现一个队列，并实现它的两个函数appendTail和deleteHead，分别为完成在队列尾部插入节点和在队列头部删除节点的功能。
leetcode链接 https://leetcode-cn.com/problems/implement-queue-using-stacks/
使用两个栈入队 - O(1)O(1)，出队 - 摊还复杂度 O(1)O(1)

//
// Created by Xue,Lin on 2020/6/16.
//>
#ifndef UNTITLED_STACK_TO_QUEUE_H
#define UNTITLED_STACK_TO_QUEUE_H
#include<iostream>
#include<stack>
using namespace std;
class MyQueue {
public:
   // 用两个栈实现一个队列，栈是后进先出，队列是先进先出
   // 主要操作在存的时候，把新存进来的数据放在栈尾
   stack<int> s1, s2;
   int front;
   /** Initialize your data structure here. */
   MyQueue() {
   }>
   /** Push element x to the back of queue. */
   void push(int x) {
       // s1是一个正常的栈结构，新来的数据在s1的栈顶，
       // 如果s1中没数据，这个时候s2应该也是没数据的
       if (s1.empty())
       {
           front = x;
       }
       s1.push(x);
   }>
   /** Removes the element from in front of queue and returns that element. */
   int pop() {
       if (s2.empty())
       {
           while(!s1.empty())
           {
               s2.push(s1.top());
               s1.pop();
           }
       }
       int tmp = s2.top();
       s2.pop();
       return tmp;
   }>
   /** Get the front element. */
   int peek() {
       if (s2.empty())
       {
           return front;
       }
       return s2.top();
   }>
   /** Returns whether the queue is empty. */
   bool empty() {
       return s1.empty() && s2.empty();
   }
};>
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
#endif //UNTITLED_STACK_TO_QUEUE_H

解题思路：两个栈，并不是在入栈的时候直接倒，而是在出栈的时候，判断模拟队列的那个栈空了，再倒。这样可以避免不必要的数据导入。这个方法可以使用的原因是队列是先进先出的，因此可以每次只保存已小部分。队列实现栈的时候，因为栈是先进先出的，不可以用这种方法来优化。

基本思路：队列和栈主要区别是一个是先进先出，一个是后进先出。因此第一想法是在存储的时候用两个栈导一下。相当于将s1中的元素存入s2中，再将新元素存入s2中。然后再将s2中元素导入s1中，这样新元素就在最后弹出了。这样相当于在插入过程中，时间复杂度是n。

//
// Created by Xue,Lin on 2020/6/16.
//

#ifndef UNTITLED_STACK_TO_QUEUE_H
#define UNTITLED_STACK_TO_QUEUE_H
#include<iostream>
#include<stack>
using namespace std;
class MyQueue {
public:
   // 用两个栈实现一个队列，栈是后进先出，队列是先进先出
   // 主要操作在存的时候，把新存进来的数据放在栈尾
   stack<int> s1, s2;
   /** Initialize your data structure here. */
   MyQueue() {
   }

   /** Push element x to the back of queue. */
   void push(int x) {
       // 简单思路，在插入元素的时候倒一下
       while(!s1.empty())
       {
           s2.push(s1.top());
           s1.pop();
       }
       s2.push(x);
       while(!s2.empty())
       {
           s1.push(s2.top());
           s2.pop();
       }
   }

   /** Removes the element from in front of queue and returns that element. */
   int pop() {
       int tmp = s1.top();
       s1.pop();
       return tmp;
   }

   /** Get the front element. */
   int peek() {
       return s1.top();
   }

   /** Returns whether the queue is empty. */
   bool empty() {
       return s1.empty();
   }
};

/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
#endif //UNTITLED_STACK_TO_QUEUE_H
// main文件中
   MyQueue* queue = new MyQueue();
   queue->push(1);
   queue->push(2);
   queue->push(3);
   cout << queue->peek() << endl;
   cout << queue->pop() << endl;
   cout << queue->pop() << endl;
   cout << "is empty?" << queue->empty() << endl;
   cout << queue->pop() << endl;
   cout << "is empty?" << queue->empty() << endl;

进阶思路：（使用两个栈入队 - O(1)O(1)，出队 - 摊还复杂度 O(1)O(1)）

//
// Created by Xue,Lin on 2020/6/16.
//>
#ifndef UNTITLED_STACK_TO_QUEUE_H
#define UNTITLED_STACK_TO_QUEUE_H
#include<iostream>
#include<stack>
using namespace std;
class MyQueue {
public:
   // 用两个栈实现一个队列，栈是后进先出，队列是先进先出
   // 主要操作在存的时候，把新存进来的数据放在栈尾
   stack<int> s1, s2;
   int front;
   /** Initialize your data structure here. */
   MyQueue() {
   }>
   /** Push element x to the back of queue. */
   void push(int x) {
       // s1是一个正常的栈结构，新来的数据在s1的栈顶，
       // 如果s1中没数据，这个时候s2应该也是没数据的
       if (s1.empty())
       {
           front = x;
       }
       s1.push(x);
   }>
   /** Removes the element from in front of queue and returns that element. */
   int pop() {
       if (s2.empty())
       {
           while(!s1.empty())
           {
               s2.push(s1.top());
               s1.pop();
           }
       }
       int tmp = s2.top();
       s2.pop();
       return tmp;
   }>
   /** Get the front element. */
   int peek() {
       if (s2.empty())
       {
           return front;
       }
       return s2.top();
   }>
   /** Returns whether the queue is empty. */
   bool empty() {
       return s1.empty() && s2.empty();
   }
};>
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
#endif //UNTITLED_STACK_TO_QUEUE_H

相关题目：用两个队列实现一个栈。
leetcode链接 https://leetcode-cn.com/problems/implement-stack-using-queues/

>class MyStack {
>public:
>    queue<int> q1, q2;
>    int front;
>    /** Initialize your data structure here. */
>    MyStack() {
>    }
>    /** Push element x onto stack. */
>    void push(int x) {
>        q2.push(x);
>        while(!q1.empty())
>        {
>            q2.push(q1.front());
>            q1.pop();
>        }  
>        while(!q2.empty())
>        {
>            cout << q2.front() << endl;
>            q1.push(q2.front());
>            q2.pop();
>        }
>    }   
>    /** Removes the element on top of the stack and returns that element. */
>    int pop() {
>        int tmp = q1.front();
>        q1.pop();
>        return tmp;
>    }  
>    /** Get the top element. */
>    int top() {
>        return q1.front();
>    }   
>    /** Returns whether the stack is empty. */
>    bool empty() {
>        return q1.empty();
>    }
>};
>/**
> * Your MyStack object will be instantiated and called as such:
> * MyStack* obj = new MyStack();
> * obj->push(x);
> * int param_2 = obj->pop();
> * int param_3 = obj->top();
> * bool param_4 = obj->empty();
> */

剑指offer学习笔记：2.3 数据结构

2.3 数据结构

2.3.1 数组

面试题3：二维数组中查找

2.3.2 字符串

面试题4：替换空格

2.3.3 链表

面试题5：从头到尾打印链表

2.3.4 树

面试题6：重建二叉树

2.3.5 栈和队列

面试题7：用两个栈实现队列

猜你喜欢

热点阅读

剑指offer学习笔记：2.3 数据结构

2.3 数据结构

2.3.1 数组

面试题3：二维数组中查找

2.3.2 字符串

面试题4： 替换空格

2.3.3 链表

面试题5：从头到尾打印链表

2.3.4 树

面试题6：重建二叉树

2.3.5 栈和队列

面试题7：用两个栈实现队列

猜你喜欢

热点阅读

面试题4：替换空格