AI 助理
备案控制台
开发者社区 人工智能 文章 正文

代码面试之栈和队列(转载)

2015-09-30 678
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 1.1 栈的定义 栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示： 结论：后进先出（Last In First Out），简称为LIFO线性表。   栈的基本运算有六种： 构造空栈：InitStack(S)、 判栈空: StackEmpty(S)、 判栈满： StackFull(S)、 进栈： Push(S,x)、可形象地理解为压入，这时栈中会多一个元素 退栈： Pop(S) 、 可形象地理解为弹出，弹出后栈中就无此元素了。

1.1 栈的定义

栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：

结论：后进先出（Last In First Out），简称为LIFO线性表。

 

栈的基本运算有六种：

构造空栈：InitStack(S)、

判栈空: StackEmpty(S)、

判栈满： StackFull(S)、

进栈： Push(S,x)、可形象地理解为压入，这时栈中会多一个元素

退栈： Pop(S) 、 可形象地理解为弹出，弹出后栈中就无此元素了。

取栈顶元素：StackTop(S),不同与弹出，只是使用栈顶元素的值，该元素仍在栈顶不会改变。

    由于栈也是线性表，因此线性表的存储结构对栈也适用，通常栈有顺序栈和链栈两种存储结构，这两种存储结构的不同，则使得实现栈的基本运算的算法也有所不同。

 

我们要了解的是，在顺序栈中有"上溢"和"下溢"的概念。顺序栈好比一个盒子，我们在里头放了一叠书，当我们要用书的话只能从第一本开始拿(你会把盒子翻过来吗?真聪明^^)，那么当我们把书本放到这个栈中超过盒子的顶部时就放不下了(叠上去的不算，哼哼)，这时就是"上溢","上溢"也就是栈顶指针指出栈的外面，显然是出错了。反之，当栈中已没有书时，我们再去拿，看看没书，把盒子拎起来看看盒底，还是没有，这就是"下溢"。"下溢"本身可以表示栈为空栈,因此可以用它来作为控制转移的条件。

链栈则没有上溢的限制，它就象是一条一头固定的链子，可以在活动的一头自由地增加链环(结点)而不会溢出，链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要在头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。

 

1.2 栈的顺序存储

使用c++的面向对象封装：

 

  1. // Test.cpp : Defines the entry point for the console application.  
  2. //  
  3. #include "stdafx.h"    
  4. #include <iostream>  
  5. using namespace std;  
  6. #define MAX 10 // MAXIMUM STACK CONTENT  
  7. class stack     
  8. {     
  9. private:     
  10.     int arr[MAX];   
  11.     int top;   
  12. public:     
  13.     stack()   
  14.     {     
  15.         inItStack();   
  16.     }  
  17.     /************************************************************************/  
  18.     /* 初始化栈                                                                     */  
  19.     /************************************************************************/  
  20.     void inItStack()   
  21.     {   
  22.         top=-1;   
  23.     }   
  24.     /************************************************************************/  
  25.     /* 入栈                                                                     */  
  26.     /************************************************************************/  
  27.     void push(int a)   
  28.     {     
  29.         top++;  
  30.         if(top < MAX)  {     
  31.             arr[top]=a;   
  32.         }   else   {     
  33.             cout<<"STACK FULL!!"<<top;     
  34.         }     
  35.     }     
  36.     /************************************************************************/  
  37.     /* 出栈                                                                     */  
  38.     /************************************************************************/  
  39.     int pop()  
  40.     {      
  41.         if(isEmpty())   {     
  42.             cout<<"STACK IS EMPTY ";  
  43.             return NULL;     
  44.         } else {     
  45.             int data=arr[top];   
  46.             arr[top]=NULL;   
  47.             top--;  
  48.             return data;   
  49.         }     
  50.     }     
  51.   
  52.     /************************************************************************/  
  53.     /* 是否为空                                                                     */  
  54.     /************************************************************************/  
  55.     bool isEmpty()  
  56.     {  
  57.         if(top == -1) return true;  
  58.         else return false;  
  59.     }  
  60. };     
  61. int main()     
  62. {     
  63.     stack a;     
  64.     a.push(3);     
  65.     a.push(10);     
  66.     a.push(1);     
  67.     cout<<"Pop:"<<a.pop();        
  68.     return 0;     
  69. }  

结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。

 

1.3 栈的链式存储
若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作"链栈"。链栈通常用一个无头结点的单链表表示。如图所示：

栈的操作是线性表操作的特例。

简单用c实现：

 

  1. // Test.cpp : Defines the entry point for the console application.    
  2. //    
  3. #include "stdafx.h"    
  4. #include <stdio.h>    
  5. #include "stdlib.h"  
  6. #include <iostream>  
  7. using namespace std;  
  8. //宏定义    
  9. #define TRUE   1    
  10. #define FALSE   0    
  11. #define OK    1    
  12. #define ERROR   0    
  13. #define INFEASIBLE -1    
  14. #define OVERFLOW -2   
  15. #define STACKEMPTY -3    
  16.   
  17. #define LT(a,b)   ((a)<(b))    
  18. #define N = 100           
  19.   
  20. typedef int Status;    
  21. typedef int ElemType;    
  22.   
  23. typedef struct LNode{    
  24.     ElemType        data;                 
  25.     struct LNode   *next;       
  26. }LNode, *LinkList;   
  27.   
  28. typedef struct stack{  
  29.     LinkList top;  
  30. } STACK;  
  31.   
  32.   
  33. /************************************************************************/  
  34. /*     接口： 
  35. */  
  36. /************************************************************************/  
  37. void InitStack(STACK &S);  
  38. void Push(STACK &S,ElemType e);  
  39. void Pop(STACK &S, ElemType *e);  
  40. ElemType GetTop(STACK S,ElemType *e);  
  41. int StackEmpty(STACK S);  
  42.   
  43. /************************************************************************/  
  44. /*  
  45. */  
  46. /************************************************************************/  
  47. void InitStack(STACK &S)  
  48. {  
  49.     S.top=NULL;  
  50. }  
  51.   
  52. /************************************************************************/  
  53. /* 入栈  
  54. */  
  55. /************************************************************************/  
  56. void Push(STACK &S,ElemType e)  
  57. {  
  58.     LinkList p;  
  59.     p = (LinkList )malloc(sizeof(LNode));  
  60.     if (!p) exit(OVERFLOW);  
  61.     p->data = e;  
  62.     p->next = S.top;  
  63.     S.top = p;  
  64. }  
  65. /************************************************************************/  
  66. /* 出栈 
  67. */  
  68. /************************************************************************/  
  69. void Pop(STACK &S, ElemType *e)  
  70. {  
  71.     LinkList p;  
  72.     if(StackEmpty(S)) exit(STACKEMPTY);  
  73.     *e = S.top->data;  
  74.     p = S.top;  
  75.     S.top = p->next;   
  76.     free(p);  
  77. }  
  78. /************************************************************************/  
  79. /* 获取栈顶元素内容 
  80. */  
  81. /************************************************************************/  
  82. ElemType GetTop(STACK S, ElemType *e)  
  83. {  
  84.     if(StackEmpty(S)) exit(STACKEMPTY);  
  85.     *e = S.top->data;  
  86. }  
  87.   
  88. /************************************************************************/  
  89. /* 判断栈S是否空  
  90. */  
  91. /************************************************************************/  
  92. int StackEmpty(STACK S)   
  93. {  
  94.     if(S.top==NULL) return TRUE;  
  95.     return   FALSE;  
  96. }  
  97.   
  98. void main()    
  99. {    
  100.   
  101.     STACK S;  
  102.     InitStack( S);  
  103.     Push(S, 3);  
  104.     Push(S, 4);  
  105.     ElemType e;  
  106.     Pop(S,&e);  
  107.     cout<<"Pop elem:"<<e;  
  108. }    

 

1.4 栈的应用

1)  数制转换

2）语法词法分析

3）表达式求值等

 

1.5 栈的递归和实现

汉诺塔的问题：

解决：

1）如果有一个盘子，直接从X移到Z即可。
2）如果有n个盘子要从X移到Z，Y作为辅助。问题可以转化为，先将上面n-1个从X移动到Y，Z作为辅助，然后将第n个从X移动到Z，最后将剩余的n-1个从Y移动到Z，X作为辅助。

完整实现代码，包括栈的实现：

 

  1. // Test.cpp : Defines the entry point for the console application.    
  2. //    
  3. #include "stdafx.h"    
  4. #include <stdio.h>    
  5. #include "stdlib.h"  
  6. #include <iostream>  
  7. using namespace std;  
  8. //宏定义    
  9. #define TRUE   1    
  10. #define FALSE   0    
  11. #define OK    1    
  12. #define ERROR   0    
  13. #define INFEASIBLE -1    
  14. #define OVERFLOW -2   
  15. #define STACKEMPTY -3    
  16.   
  17. #define LT(a,b)   ((a)<(b))    
  18. #define N = 100           
  19.   
  20. typedef int Status;    
  21. typedef int ElemType;    
  22.   
  23. typedef struct LNode{    
  24.     ElemType        data;                 
  25.     struct LNode   *next;       
  26. }LNode, *LinkList;   
  27.   
  28. typedef struct stack{  
  29.     LinkList top;  
  30. } STACK;  
  31.   
  32.   
  33. /************************************************************************/  
  34. /*     接口： 
  35. */  
  36. /************************************************************************/  
  37. void InitStack(STACK &S);  
  38. void Push(STACK &S,ElemType e);  
  39. void Pop(STACK &S, ElemType *e);  
  40. ElemType GetTop(STACK S,ElemType *e);  
  41. int StackEmpty(STACK S);  
  42.   
  43. /************************************************************************/  
  44. /*  
  45. */  
  46. /************************************************************************/  
  47. void InitStack(STACK &S)  
  48. {  
  49.     S.top=NULL;  
  50. }  
  51.   
  52. /************************************************************************/  
  53. /* 入栈  
  54. */  
  55. /************************************************************************/  
  56. void Push(STACK &S,ElemType e)  
  57. {  
  58.     LinkList p;  
  59.     p = (LinkList )malloc(sizeof(LNode));  
  60.     if (!p) exit(OVERFLOW);  
  61.     p->data = e;  
  62.     p->next = S.top;  
  63.     S.top = p;  
  64. }  
  65. /************************************************************************/  
  66. /* 出栈 
  67. */  
  68. /************************************************************************/  
  69. void Pop(STACK &S, ElemType *e)  
  70. {  
  71.     LinkList p;  
  72.     if(StackEmpty(S)) exit(STACKEMPTY);  
  73.     *e = S.top->data;  
  74.     p = S.top;  
  75.     S.top = p->next;   
  76.     free(p);  
  77. }  
  78. /************************************************************************/  
  79. /* 获取栈顶元素内容  
  80.  
  81. */  
  82. /************************************************************************/  
  83. ElemType GetTop(STACK S, ElemType *e)  
  84. {  
  85.     if(StackEmpty(S)) exit(STACKEMPTY);  
  86.     *e = S.top->data;  
  87. }  
  88. void printStack(STACK S){  
  89.     LinkList p;  
  90.     p = S.top;  
  91.     printf("栈： ");  
  92.     while (p) {  
  93.         printf("%d ", p->data);  
  94.         p = p->next;  
  95.     }  
  96. }  
  97. /************************************************************************/  
  98. /* 如果有一个盘子，直接从X移到Z即可。 
  99. 如果有n个盘子要从X移到Z，Y作为辅助。问题可以转化为，先将上面n-1个从X移动到Y，Z作为辅助，然后将第n个从X移动到Z，最后将剩余的n-1个从Y移动到Z，X作为辅助。 
  100. */  
  101. /************************************************************************/  
  102.   
  103. void move(STACK &Sa,STACK &Sb)  
  104. {     
  105.     ElemType e;  
  106.     Pop(Sa,&e);  
  107.     Push(Sb, e);  
  108. }  
  109. void hanoi(int n,STACK  &X,STACK &Y,STACK &Z)  
  110. {  
  111.     if(n==1) return move(X, Z);     //将圆盘1号直接移到z  
  112.     hanoi(n-1,X,Z,Y);               //将x上的1大n-1圆盘移到y，z做辅助塔  
  113.     move(X, Z);                     //将编号为n的圆盘移z  
  114.     hanoi(n-1,Y,X,Z);               //将y上的1大n-1圆盘移到z，x做辅助塔  
  115. }  
  116.   
  117. /************************************************************************/  
  118. /* 判断栈S是否空  
  119. */  
  120. /************************************************************************/  
  121. int StackEmpty(STACK S)   
  122. {  
  123.     if(S.top==NULL) return TRUE;  
  124.     return   FALSE;  
  125. }  
  126.   
  127. void main()    
  128. {    
  129.   
  130.     STACK Sx, Sy,Sz;  
  131.     InitStack( Sx);  
  132.     InitStack( Sy);  
  133.     InitStack( Sz);  
  134.     int i, n = 10;  
  135.     for (i = 10 ; i>=1 ;i--) {  
  136.         Push(Sx, i);  
  137.     }  
  138.     printStack(Sx);  
  139.     hanoi(n,  Sx,Sy,Sz);  
  140.     printStack(Sz);  
  141. }    



 

 

1．队列

 

 

1.1 队列定义 

队列(Queue)也是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(rear)，允许插入的一端称为队头 (Front)

,队列的操作原则是先进先出的，所以队列又称作FIFO表(First In First Out)

队列的基本运算也有六种：

置空队 ：InitQueue(Q)

判队空： QueueEmpty(Q)

判队满： QueueFull(Q)

入队 ： EnQueue(Q,x)

出队 ： DeQueue(Q)

取队头元素： QueueFront(Q),不同与出队，队头元素仍然保留。

 

队列也有顺序存储和链式存储两种存储结构，前者称顺序队列，后者为链队。

对于顺序队列，我们要理解"假上溢"的现象。

我们现实中的队列比如人群排队买票，队伍中的人是可以一边进去从另一头出来的，除非地方不够，总不会有"溢出"的现象，相似地，当队列中元素完全充满这个向量空间时，再入队自然就会上溢，如果队列中已没有元素，那么再要出队也会下溢。

那么"假上溢"就是怎么回事呢?

因为在这里，我们的队列是存储在一个向量空间里，在这一段连续的存储空间中，由一个队列头指针和一个尾指针表示这个队列，当头指针和尾指针指向同一个位置时，队列为空，也就是说，队列是由两个指针中间的元素构成的。在队列中，入队和出队并不是象现实中，元素一个个地向前移动，走完了就没有了,而是指针在移动，当出队操作时，头指针向前(即向量空间的尾部)增加一个位置，入队时，尾指针向前增加一个位置，在某种情况下，比如说进一个出一个，两个指针就不停地向前移动，直到队列所在向量空间的尾部，这时再入队的话，尾指针就要跑到向量空间外面去了，仅管这时整个向量空间是空的，队列也是空的，却产生了"上溢"现象，这就是假上溢。

为了克服这种现象造成的空间浪费，我们引入循环向量的概念，就好比是把向量空间弯起来，形成一个头尾相接的环形，这样，当存于其中的队列头尾指针移到向量空间的上界(尾部)时，再加1的操作(入队或出队)就使指针指向向量的下界，也就是从头开始。这时的队列就称循环队列。

通常我们应用的大都是循环队列。由于循环的原因，光看头尾指针重叠在一起我们并不能判断队列是空的还是满的，这时就需要处理一些边界条件，以区别队列是空还是满。方法至少有三种，一种是另设一个布尔变量来判断(就是请别人看着，是空还是满由他说了算)，第二种是少用一个元素空间，当入队时，先测试入队后尾指针是不是会等于头指针，如果相等就算队已满，不许入队。第三种就是用一个计数器记录队列中的元素的总数，这样就可以随时知道队列的长度了，只要队列中的元素个数等于向量空间的长度，就是队满。


2.2 队列的顺序存储

顺序存储如图：


由于是顺序存储结构的存储空间是静态分配的，所以在添加数据的时，有可能没有剩余空间的情况。

解决这种“假溢出”情况，使用循环队列。在c语言中，不能用动态分配的一维数组来实现循环队列。若使用循环队列，必须设置最大队列长度，若无法估计最大长度，就使用链式队列。

c实现：

 

  1. // Test.cpp : Defines the entry point for the console application.    
  2. //    
  3. #include "stdafx.h"    
  4. #include <stdio.h>    
  5. #include "stdlib.h"  
  6. #include <iostream>  
  7. using namespace std;  
  8. //宏定义    
  9. #define TRUE   1    
  10. #define FALSE   0    
  11. #define OK    1    
  12. #define ERROR   0    
  13. #define INFEASIBLE -1    
  14. #define OVERFLOW -2   
  15. #define QUEUEEMPTY  -3    
  16.         
  17. #define MAX_QUEUE 10 //队列的最大数据元素数目  
  18.   
  19. typedef int Status;    
  20. typedef int ElemType;    
  21.   
  22. typedef struct queue{    
  23.     ElemType        elem[MAX_QUEUE] ;     ///假设当数组只剩下一个单元时认为队满            
  24.     int front;      //队头指针  
  25.     int rear;       //队尾指针     
  26. }QUEUE;   
  27.   
  28.   
  29. /************************************************************************/  
  30. /*     各项基本操作算法。 
  31. */  
  32. /************************************************************************/  
  33. void InitQueue(QUEUE *&Q);  
  34. void EnQueue(QUEUE *Q,ElemType elem);  
  35. void DeQueue(QUEUE *Q,ElemType *elem);  
  36. int QueueEmpty(QUEUE Q);  
  37.   
  38. /************************************************************************/  
  39. /*  
  40.   初始化 
  41.   直接使用结构体指针变量，必须先分配内存地址，即地址的指针 
  42. */  
  43. /************************************************************************/  
  44. void InitQueue(QUEUE *&Q)   
  45. {  
  46.   
  47.     Q = (QUEUE *) malloc (sizeof(QUEUE));  
  48.     Q->front = Q->rear = -1;  
  49.   
  50. }  
  51. /************************************************************************/  
  52. /*     入队                                                               
  53. */  
  54. /************************************************************************/  
  55.    
  56. void EnQueue(QUEUE *Q, ElemType elem)  
  57. {  
  58.     if((Q->rear+1)% MAX_QUEUE == Q->front) exit(OVERFLOW);  
  59.     Q->rear = (Q->rear + 1)%MAX_QUEUE;  
  60.     Q->elem[Q->rear] = elem;   
  61. }  
  62. /************************************************************************/  
  63. /*     出队                                                                
  64. */  
  65. /************************************************************************/  
  66. void DeQueue(QUEUE *Q,ElemType *elem)  
  67. {  
  68.     if (QueueEmpty(*Q))  exit(QUEUEEMPTY);  
  69.     Q->front =  (Q->front+1) % MAX_QUEUE;  
  70.     *elem=Q->elem[Q->front];  
  71. }  
  72. /************************************************************************/  
  73. /*    获取队头元素内容                                                             
  74. */  
  75. /************************************************************************/  
  76.   
  77. void GetFront(QUEUE Q,ElemType *elem)   
  78. {  
  79.     if ( QueueEmpty(Q) )  exit(QUEUEEMPTY);  
  80.     *elem = Q.elem[ (Q.front+1) % MAX_QUEUE ];  
  81. }  
  82. /************************************************************************/  
  83. /*    判断队列Q是否为空                                                              
  84. */  
  85. /************************************************************************/  
  86. int QueueEmpty(QUEUE Q)  
  87. {  
  88.     if(Q.front==Q.rear) return TRUE;  
  89.     else return FALSE;  
  90. }  
  91.   
  92. void main()    
  93. {    
  94.   
  95.     QUEUE *Q;  
  96.     InitQueue( Q);  
  97.     EnQueue( Q, 1);  
  98.     EnQueue( Q, 2);  
  99.     ElemType e;  
  100.     DeQueue( Q,&e);  
  101.     cout<<"De queue:"<<e;  
  102. }    


注意：InitQueue(QUEUE *&Q) 传的是指针的地址。

 

 

2.3 链式队列：

 

  1. // Test.cpp : Defines the entry point for the console application.    
  2. //    
  3. #include "stdafx.h"    
  4. #include <stdio.h>    
  5. #include "stdlib.h"  
  6. #include <iostream>  
  7. using namespace std;  
  8. //宏定义    
  9. #define TRUE   1    
  10. #define FALSE   0    
  11. #define OK    1    
  12. #define ERROR   0    
  13. #define INFEASIBLE -1    
  14. #define OVERFLOW -2   
  15. #define QUEUEEMPTY  -3    
  16.         
  17.   
  18. typedef int Status;    
  19. typedef int ElemType;    
  20.   
  21. typedef struct LNode {          //链式队列的结点结构  
  22.     ElemType elem;          //队列的数据元素类型  
  23.     struct LNode *next;      //指向后继结点的指针  
  24. }LNode, *LinkList;  
  25.   
  26. typedef struct queue{   //链式队列  
  27.     LinkList front;     //队头指针  
  28.     LinkList rear;      //队尾指针  
  29. }QUEUE;   
  30.   
  31. /************************************************************************/  
  32. /*     各项基本操作算法。 
  33. */  
  34. /************************************************************************/  
  35. void InitQueue(QUEUE *Q);  
  36. void EnQueue(QUEUE *Q,ElemType elem);  
  37. void DeQueue(QUEUE *Q,ElemType *elem);  
  38. void GetFront(QUEUE Q,ElemType *elem) ;  
  39. bool QueueEmpty(QUEUE Q);  
  40.   
  41. /************************************************************************/  
  42.   
  43.   
  44. /*初始化队列Q  */  
  45. void InitQueue(QUEUE *Q)  
  46. {  
  47.     Q->front = (LinkList)malloc(sizeof(LNode));  
  48.     if (Q->front==NULL) exit(ERROR);  
  49.     Q->rear= Q->front;  
  50. }  
  51. /*入队 */   
  52. void EnQueue(QUEUE *Q,ElemType elem)  
  53. {  
  54.     LinkList s;  
  55.     s = (LinkList)malloc(sizeof(LNode));  
  56.     if(!s) exit(ERROR);  
  57.     s->elem = elem;  
  58.     s->next = NULL;  
  59.     Q->rear->next = s;  
  60.     Q->rear = s;  
  61. }  
  62.   
  63. /*出队  */   
  64. void DeQueue(QUEUE *Q,ElemType *elem)  
  65. {  
  66.     LinkList s;  
  67.     if(QueueEmpty(*Q)) exit(ERROR);  
  68.     *elem = Q->front->next->elem;  
  69.     s = Q->front->next;  
  70.     Q->front->next = s->next;  
  71.     free(s);  
  72. }  
  73. /*获取队头元素内容  */   
  74.   
  75. void GetFront(QUEUE Q,ElemType *elem)   
  76. {  
  77.     if(QueueEmpty(Q)) exit(ERROR);  
  78.     *elem = Q.front->next->elem;  
  79. }  
  80. /*判断队列Q是否为空   */   
  81. bool QueueEmpty(QUEUE Q)  
  82. {  
  83.     if(Q.front == Q.rear) return TRUE;  
  84.     return FALSE;  
  85. }  
  86.   
  87. void main()    
  88. {    
  89.   
  90.     QUEUE Q;  
  91.     InitQueue( &Q);  
  92.     EnQueue( &Q, 1);  
  93.     EnQueue( &Q, 2);  
  94.     ElemType e;  
  95.     DeQueue( &Q,&e);  
  96.     cout<<"De queue:"<<e;  
  97. }    

 

 

2. 4．队列的应用
【举例1】银行排队
【举例2】模拟打印机缓冲区。
在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。
【举例3】CPU分时系统
在一个带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使CPU正常工作。

文章标签：
存储
算法
C++
C语言
自然语言处理
关键词：
面试栈
面试代码
面试队列
面试栈队列
代码面试
技术让梦想更伟大-李肖遥
目录
相关文章
热爱技术的小郑
|
4月前
|
Java 编译器 C++
【Java基础面试一】、为什么Java代码可以实现一次编写、到处运行？
这篇文章解释了Java能够实现“一次编写，到处运行”的原因，主要归功于Java虚拟机（JVM），它能够在不同平台上将Java源代码编译成的字节码转换成对应平台的机器码，实现跨平台运行。
热爱技术的小郑
83 3
【Java基础面试一】、为什么Java代码可以实现一次编写、到处运行？
土木林森
|
23天前
|
存储 网络协议 安全
30 道初级网络工程师面试题，涵盖 OSI 模型、TCP/IP 协议栈、IP 地址、子网掩码、VLAN、STP、DHCP、DNS、防火墙、NAT、VPN 等基础知识和技术，帮助小白们充分准备面试，顺利踏入职场
本文精选了 30 道初级网络工程师面试题，涵盖 OSI 模型、TCP/IP 协议栈、IP 地址、子网掩码、VLAN、STP、DHCP、DNS、防火墙、NAT、VPN 等基础知识和技术，帮助小白们充分准备面试，顺利踏入职场。
土木林森
66 2
服务端技术栈
|
4月前
|
存储 缓存 Java
面试问Spring循环依赖？今天通过代码调试让你记住
该文章讨论了Spring框架中循环依赖的概念，并通过代码示例帮助读者理解这一概念。
服务端技术栈
56 5
面试问Spring循环依赖？今天通过代码调试让你记住
qhhf_地道酬勤
|
4月前
|
存储 安全 Java
JVM常见面试题（二）：JVM是什么、由哪些部分组成、运行流程，JDK、JRE、JVM关系；程序计数器，堆，虚拟机栈，堆栈的区别是什么，方法区，直接内存
JVM常见面试题（二）：JVM是什么、由哪些部分组成、运行流程是什么，JDK、JRE、JVM的联系与区别；什么是程序计数器，堆，虚拟机栈，栈内存溢出，堆栈的区别是什么，方法区，直接内存
qhhf_地道酬勤
96 1
JVM常见面试题（二）：JVM是什么、由哪些部分组成、运行流程，JDK、JRE、JVM关系；程序计数器，堆，虚拟机栈，堆栈的区别是什么，方法区，直接内存
星河造梦坊丨程序开发
|
4月前
|
存储 设计模式 Java
Unity精华☀️ 面试“堆、栈”误区！这样做可能反而会降低吸引力
Unity精华☀️ 面试“堆、栈”误区！这样做可能反而会降低吸引力
星河造梦坊丨程序开发
45 2
游客ot6eft3qn37ga
|
4月前
|
JavaScript 前端开发 程序员
JS小白请看！一招让你的面试成功率大大提高——规范代码
JS小白请看！一招让你的面试成功率大大提高——规范代码
游客ot6eft3qn37ga
45 5
热爱技术的小郑
|
4月前
|
安全 Java
虚拟机栈的五道面试题
这篇文章提供了关于Java虚拟机栈的五个面试问题，涉及栈溢出的情况、栈大小调整、栈内存的分配、垃圾回收与虚拟机栈的关系以及局部变量的线程安全性。
热爱技术的小郑
29 0
杰哥在此
|
5月前
|
存储 安全 Java
Java面试题：在JVM中，堆和栈有什么区别？请详细解释说明，要深入到底层知识
Java面试题：在JVM中，堆和栈有什么区别？请详细解释说明，要深入到底层知识
杰哥在此
90 3
杰哥在此
|
5月前
|
存储 缓存 监控
Java面试题：解释堆和栈的OutOfMemoryError通常在什么情况下会发生
Java面试题：解释堆和栈的OutOfMemoryError通常在什么情况下会发生
杰哥在此
49 3
杰哥在此
|
5月前
|
存储 设计模式 监控
Java面试题：简述JVM的内存结构，包括堆、栈、方法区等。栈内存优化的方法有 哪些？
Java面试题：简述JVM的内存结构，包括堆、栈、方法区等。栈内存优化的方法有 哪些？
杰哥在此
49 0

热门文章

最新文章

  • 1
    超有用的sql查询语句。项目、面试都有用
  • 2
    C# 面试题解析-请遍历页面上所有的TextBox控件并给它赋值为string.Empty
  • 3
    面试题1：赋值运算符函数
  • 4
    太为难我了，阿里面试了7轮（5年经验，拿下P7岗offer）
  • 5
    作为字节跳动的面试官，有些话我不得不说！
  • 6
    大厂高频面试真题详解：最长无重复字符的子串
  • 7
    [面试题～k8s] 云原生必问基础篇
  • 8
    面试官：素有Java锁王称号的‘StampedLock’你知道吗？我：这什么鬼？
  • 9
    【面试题精讲】MySQL连接器
  • 10
    Java面试（static 关键字）(final关键字)
  • 1
    面试官：素有Java锁王称号的‘StampedLock’你知道吗？我：这什么鬼？
    99
  • 2
    Spring Boot 源码面试知识点
    97
  • 3
    大厂高频面试题：ReentrantLock 与 synchronized异同点对比
    69
  • 4
    【Java多线程】面试常考 —— JUC(java.util.concurrent) 的常见类
    78
  • 5
    【Java多线程】面试常考——锁策略、synchronized的锁升级优化过程以及CAS（Compare and swap）
    67
  • 6
    【LeetCode力扣】面试题 17.14. 最小K个数（top-k问题）
    92
  • 7
    【刷题】 leetcode 面试题 08.05.递归乘法
    71
  • 8
    【刷题】 leetcode 面试题 01.06 字符串压缩
    69
  • 9
    MySQL第五战：常见面试题（下）
    60
  • 10
    MySQL第四战：视图以及常见面试题（上）
    65

    • 相关课程

    更多
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计

    • 相关电子书

    更多
  • 阿里云技术面试红宝书
  • 超全算法笔试-模拟题精解合集
  • 程序员面试宝典
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月