• 数据结构——队列

    目录

    1.队列元素逆置

    C语言

    C++

    2.约瑟夫环

    3.栈实现队列

    4.用队列实现栈

    1.队列元素逆置

    【问题描述】

    已知Q是一个非空队列，S是一个空栈。仅使用少量工作变量以及对队列和栈的基本操作，编写一个算法，将队列Q中的所有元素逆置。

    【输入形式】

    输入的第一行为队列元素个数，第二行为队列从首至尾的元素

    【输出形式】

    输出队列的逆置

    【样例输入】

    3
1 2 3

    【样例输出】

    3 2 1

    【评分标准】

    需采用队列与栈的知识，否则不能得分

    C语言

    1. #include 
    2. #include 
    3.  
    4. #define MAX_SIZE 3000
    5.  
    6. typedef struct {
    7.     int data[MAX_SIZE];
    8.     int front;
    9.     int rear;
    10. } Queue;
    11.  
    12. void initQueue(Queue *q) {
    13.     q->front = 0;
    14.     q->rear = -1;
    15. }
    16.  
    17. int isEmpty(Queue *q) {
    18.     return q->front > q->rear;
    19. }
    20.  
    21. void enqueue(Queue *q, int item) {
    22.     if (q->rear == MAX_SIZE - 1) {
    23.         printf("Error: Queue is full\n");
    24.         exit(1);
    25.     }
    26.     q->rear++;
    27.     q->data[q->rear] = item;
    28. }
    29.  
    30. int dequeue(Queue *q) {
    31.     if (isEmpty(q)) {
    32.         printf("Error: Queue is empty\n");
    33.         exit(1);
    34.     }
    35.     int item = q->data[q->front];
    36.     q->front++;
    37.     return item;
    38. }
    39.  
    40. typedef struct {
    41.     int data[MAX_SIZE];
    42.     int top;
    43. } Stack;
    44.  
    45. void initStack(Stack *s) {
    46.     s->top = -1;
    47. }
    48.  
    49. int isStackEmpty(Stack *s) {
    50.     return s->top == -1;
    51. }
    52.  
    53. void push(Stack *s, int item) {
    54.     if (s->top == MAX_SIZE - 1) {
    55.         printf("Error: Stack is full\n");
    56.         exit(1);
    57.     }
    58.     s->top++;
    59.     s->data[s->top] = item;
    60. }
    61.  
    62. int pop(Stack *s) {
    63.     if (isStackEmpty(s)) {
    64.         printf("Error: Stack is empty\n");
    65.         exit(1);
    66.     }
    67.     int item = s->data[s->top];
    68.     s->top--;
    69.     return item;
    70. }
    71.  
    72. void reverseQueue(Queue *q) {
    73.     if (isEmpty(q)) {
    74.         return;
    75.     }
    76.     Stack s;
    77.     initStack(&s);
    78.  
    79.     while (!isEmpty(q)) {
    80.         push(&s, dequeue(q));
    81.     }
    82.  
    83.     while (!isStackEmpty(&s)) {
    84.         enqueue(q, pop(&s));
    85.     }
    86. }
    87.  
    88. int main() {
    89.     Queue q;
    90.     initQueue(&q);
    91.  
    92.     int size;
    93.     scanf("%d", &size);
    94.     int i;
    95.     for ( i = 0; i < size; i++) {
    96.         int item;
    97.         scanf("%d", &item);
    98.         enqueue(&q, item);
    99.     }
    100.     reverseQueue(&q);
    101.  
    102.     while (!isEmpty(&q)) {
    103.         printf("%d ", dequeue(&q));
    104.     }
    105.     printf("\n");
    106.  
    107.     return 0;
    108. }

    C++

    1.  
    2. #include
    3. int main()
    4. {
    5. 	int QUEUE[1000],STACK[1000],i,n,temp,top,front,rear;
    6. 	front=rear=top=-1;
    7. 	scanf("%d",&n);
    8. 	for(i=0;i
    9. 	{
    10. 		scanf("%d",&temp);
    11. 		rear++;
    12. 		QUEUE[rear]=temp;
    13. 	}
    14. 	for(i=0;i
    15. 	{
    16. 		temp=QUEUE[++front];
    17. 		STACK[++top]=temp;
    18. 	}
    19. 	while(top!=-1)
    20. 	{
    21. 		printf("%d ",STACK[top]);
    22. 		top--;
    23. 	}
    24. 	return 0;
    25. }

    2.约瑟夫环

    【问题描述】

    n个人围成一个圈，按顺时针方向一次编号1、2、3、……、n，从第一个人开始顺时针方向依次报数1、2、3、……，报数m的人被淘汰，然后下一个人再从1开始报数，一直重复该过程。由于人数是有限的，因此最后一定只会剩下一个人，求这个人的编号。

    【输入形式】

    第一行，一个整数n，表示约瑟夫环的总人数。

    第二行，一个整数m，表示报到m的人被淘汰。

    【输出形式】

     一行，一个整数，约瑟夫环最终剩下的人的编号。

    【样例输入】

    5
2

    【样例输出】

    3

    【样例说明】

    5个人围成一圈，编号1，2，3，4，5；

    第一轮，2号淘汰，剩下1，3，4，5；

    第二轮，从3开始报数，4号淘汰，剩下1，3，5；

    第三轮，从5开始报数，1号淘汰，剩下3，5；

    第四轮，从3开始报数，5号淘汰，剩下3。
    【评分标准】

    通过所有数据

    1. class Queue:
    2.     #initialization
    3.     def __init__(self):
    4.         self.q = []
    5.     
    6.     #入队
    7.     def enqueue(self, num):
    8.         self.q.append(num)
    9.         
    10.     #出队
    11.     def dequeue(self):
    12.         if self.isEmpty():
    13.             return "The queue is EMPTY!"
    14.         else:
    15.             return self.q.pop(0)
    16.         
    17.     def get_len(self):
    18.         return len(self.q)
    19.     
    20.     def isEmpty(self):
    21.         return self.get_len()==0
    22.     
    23. joseph = Queue()
    24. n = int(input())
    25. m = int(input())
    26. for i in range(1,n+1):
    27.     joseph.enqueue(i)
    28.  
    29.  
    30.  
    31. while(joseph.get_len()!=1):
    32.     count = 1
    33.     while(True):
    34.         
    35.         if(count!=m):
    36.             joseph.enqueue(joseph.dequeue())
    37.             count += 1
    38.         else:
    39.             joseph.dequeue()
    40.             break
    41.     
    42.  
    43. print(joseph.dequeue())

    3.栈实现队列

    【问题描述】

    请使用栈类实现队列的类。

    【输入形式】

    第一行一个整数n，

    接下来n行，每行一个整数，依次表示已经在队列中的数。

    接下来一行，一个整数m。

    接下来m行，有两种情况：1. 一个整数，请将其入列。2. 字符串"D"，表示出列操作。

    【输出形式】

    若干行，每行一个出列的输出。

    【样例输入】

    3
1
2
3
2
4
D

    【样例输出】

    1

    【样例说明】

    队列中原来有1，2，3三个数，第一个操作使4入列，第二个操作出列，弹出队头的1
    【评分标准】

    通过所有数据

    1. class Stack:
    2.     def __init__(self):
    3.         self.s = []
    4.         
    5.     def push(self, num):
    6.         self.s.append(num)
    7.     
    8.     def out(self):
    9.         return self.s.pop()
    10.     
    11.     def empty(self):
    12.         return len(self.s)==0
    13.     
    14.     
    15. class Queue:
    16.     def __init__(self):
    17.         self.s1 = Stack()
    18.         self.s2 = Stack()
    19.         
    20.     def enq(self, num):
    21.         self.s1.push(num)
    22.         
    23.     def deq(self):
    24.         while(not self.s1.empty()):
    25.             self.s2.push(self.s1.out())
    26.         temp= self.s2.out()
    27.         while(not self.s2.empty()):
    28.             self.s1.push(self.s2.out())
    29.         return temp
    30.  
    31. n = int(input())
    32. q = Queue()
    33. for i in range(n):
    34.     q.enq(int(input()))
    35.  
    36. m = int(input())
    37. for i in range(m):
    38.     op = input()
    39.     if op.isdigit():
    40.         q.enq(int(op))
    41.     elif op=="D":
    42.         print(q.deq())

    4.用队列实现栈

    【问题描述】

    用队列实现一个栈。本题要求使用队列实现栈，其他实现方式不计分。
    【输入形式】

    第一行输入数n，接下来n行输入一些数，表示已经在栈里的数

    接下来输入数m，接下来m行输入指令，A表示入栈，B表示出栈，具体看样例
    【输出形式】

    第一行输出弹出栈的数字们，用空格隔开

    第二行弹出栈内剩余的数，并用空格隔开
    【样例输入】

    3
1
2
3
5
A 5
A 6
B 
B
B

    【样例输出】

    6 5 3
2 1

    【样例说明】

    出现异常还是输出一行‘No’
    【评分标准】

    1. class SQueue(object):
    2. 	def __init__(self, init_len=8):
    3. 		self.__elem = [0] * init_len
    4. 		self.__len = init_len
    5. 		self.__head = 0
    6. 		self.__num = 0
    7.  
    8.  
    9. 	def __extend(self):
    10. 		old_len = self.__len
    11. 		self.__len *= 2
    12. 		new_elems = [0] * self.__len
    13. 		for i in range(old_len):
    14. 			new_elems[i] = self.__elem[(self.__head + i) % old_len]
    15. 		self.__elem, self.__head = new_elems, 0
    16.  
    17.  
    18. 	def is_empty(self):
    19. 		return self.__num == 0
    20.  
    21.  
    22. 	def peek(self):
    23. 		if self.__num == 0:
    24. 			raise QueueUnderflow
    25. 		return self.__elem[self.__head]
    26.  
    27.  
    28. 	def enqueue(self, e):
    29. 		if self.__num == self.__len:
    30. 			self.__extend()
    31. 		self.__elem[(self.__head + self.__num) % self.__len] = e
    32. 		self.__num += 1
    33. 		
    34. 		
    35. 	def dequeue(self):
    36. 		if self.__num == 0:
    37. 			raise QueueUnderflow
    38. 		e = self.__elem[self.__head]
    39. 		self.__head = (self.__head + 1) % self.__len
    40. 		self.__num -= 1
    41. 		return e
    42.  
    43. 	def get_elem(self):
    44. 		print(self.__elem)
    45.  
    46.  
    47. class Stack():
    48. 	def __init__(self):
    49. 		self.__stack = SQueue()
    50. 		self.__temp = SQueue()
    51.  
    52.  
    53. 	def push(self, e):
    54. 		while not self.__stack.is_empty():
    55. 			self.__temp.enqueue(self.__stack.dequeue())
    56. 		self.__stack.enqueue(e)
    57. 		while not self.__temp.is_empty():
    58. 			self.__stack.enqueue(self.__temp.dequeue())
    59.  
    60.  
    61. 	def pop(self):
    62. 		return self.__stack.dequeue()
    63.  
    64.  
    65. 	def is_empty(self):
    66. 		return self.__stack.is_empty()
    67.  
    68.  
    69.  
    70. n = int(input())
    71. stack = Stack()
    72. for i in range(n):
    73. 	stack.push(int(input()))
    74. mark = 0
    75. tmp = []
    76. m = int(input())
    77. for i in range(m):
    78. 	o = input()
    79. 	if 'A' in o:
    80. 		o = int(o.strip().split()[1])
    81. 		stack.push(o)
    82. 	elif 'B' in o:
    83. 		try:
    84. 			tmp += [stack.pop()]
    85. 		except:
    86. 			mark = 1
    87. 			break
    88. if mark == 1:
    89. 	print('No')
    90. else:
    91. 	tmp = [str(i) for i in tmp]
    92. 	print(' '.join(tmp))
    93. 	_ = []
    94. 	while not stack.is_empty():
    95. 		_ += [str(stack.pop())]
    96. 	print(' '.join(_))

  • 相关阅读:
    461. 汉明距离
    un7.29:Linux——如何在docker中安装tomcat？
    笔记 记录
    今天的码农女孩学习了关于react的组件的知识
    D. Divide and Sum(组合数学)
    GD32与STM32在使用过程中的区别
    【计算机系统结构】指令级高度并行的超级计算机
    现货白银实时交易平台的成长阶段 你出在哪个阶段？
    前端·在线随机生成图片 & 免费 API
    【C语言库函数模拟实现 】# Strlen()
  • 原文地址：https://blog.csdn.net/timberman666/article/details/133844422