TY - GEN

T1 - Simulating a stack using queues

AU - Kaplan, Haim

AU - Tarjan, Robert E.

AU - Zamir, Or

AU - Zwick, Uri

N1 - Funding Information:
∗Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv, Israel. E-mail: haimk@tau.ac.il. Research Supported by ISF grant no. 1595/19 and the Blavatnik research fund. †Department of Computer Science, Princeton University, NJ, USA. Intertrust Technologies, Sunnyvale, CA, USA. E-mail: ret@princeton.edu. ‡Institute of Advanced Study, Princeton, NJ, USA. Part of this research was done at Tel Aviv University and supported by ISF grants no. 1595/19 and 2854/20 and the Blavatnik Fund. §Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv, Israel. E-mail: zwick@tau.ac.il. Research Supported by ISF grant no. 2854/20.
Publisher Copyright:
Copyright © 2022 by SIAM.

PY - 2022

Y1 - 2022

N2 - It is well known that a queue can be simulated by two stacks using a constant number of stack operations per queue operation. In this paper we consider the forgotten converse problem of simulating a stack using several queues. We consider several variants of this problem. For the offline variant, we obtain a tight upper and lower bounds for the worst-case number of queue operations needed to simulate a sequence of n stack operations using k queues. For the online variant, when the number of queues k is constant, and n is the maximum number of items in the stack at any given time, we obtain tight Θ(n1/k) upper and lower bounds on the worst-case and amortized number of queue operations needed to simulate one stack operation. When k is allowed to grow with n, we prove an upper bound of O(n1/k + logk n) and a lower bound of on the amortized number of queue operations per stack operation. We also prove an upper bound of O(kn1/k) and a lower bound of Ω(n1/k + logk n) on the worst-case number of queue operations per stack operation. We also show that the specific but interesting sequence of n pushes followed by n pops can be implemented much faster using a total number of only Θ(n logk n) queue operations, for every k ≥ 2, an amortized number of Θ(logk n) queue operations per stack operation, and this bound is tight. On the other hand, we show that the same sequence requires at least Ω(n1/k) queue operations per stack operation in the worst case.

AB - It is well known that a queue can be simulated by two stacks using a constant number of stack operations per queue operation. In this paper we consider the forgotten converse problem of simulating a stack using several queues. We consider several variants of this problem. For the offline variant, we obtain a tight upper and lower bounds for the worst-case number of queue operations needed to simulate a sequence of n stack operations using k queues. For the online variant, when the number of queues k is constant, and n is the maximum number of items in the stack at any given time, we obtain tight Θ(n1/k) upper and lower bounds on the worst-case and amortized number of queue operations needed to simulate one stack operation. When k is allowed to grow with n, we prove an upper bound of O(n1/k + logk n) and a lower bound of on the amortized number of queue operations per stack operation. We also prove an upper bound of O(kn1/k) and a lower bound of Ω(n1/k + logk n) on the worst-case number of queue operations per stack operation. We also show that the specific but interesting sequence of n pushes followed by n pops can be implemented much faster using a total number of only Θ(n logk n) queue operations, for every k ≥ 2, an amortized number of Θ(logk n) queue operations per stack operation, and this bound is tight. On the other hand, we show that the same sequence requires at least Ω(n1/k) queue operations per stack operation in the worst case.

UR - http://www.scopus.com/inward/record.url?scp=85130720513&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85130720513&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85130720513

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1901

EP - 1924

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

PB - Association for Computing Machinery

T2 - 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

Y2 - 9 January 2022 through 12 January 2022

ER -