listAlgorithms.TwoStackQueue< T extends Comparable< T > > Class Reference

List of all members.

Public Member Functions
void	enqueue (T val)
T	peek ()
T	dequeue ()
Protected Member Functions
void	copyToStore ()
void	copyFromStore ()

---

Detailed Description

TwoStackQueue

This code implements a queue (first in first out) with two stacks.

Before a new item is pushed onto the queue that serves as a stack, all existing items are copied into a storage stack. The item is then added to the stack and the other items are copied back.

The time complexity of N queue pushes is O(N^2) copy operations. All of this could be avoided with a list head and a list tail pointer.

This is one of those alleged interview questions that would not actually come up in actual software. The question came from Cracking the Coding Interview by Gayle McDowell. Jun 20, 2013

Author:

Ian Kaplan, iank@bearcave.com

Definition at line 34 of file TwoStackQueue.java.

---

Member Function Documentation

void listAlgorithms.TwoStackQueue< T extends Comparable< T > >.copyFromStore

(

)

[protected]

Definition at line 45 of file TwoStackQueue.java.

void listAlgorithms.TwoStackQueue< T extends Comparable< T > >.copyToStore

(

)

[protected]

Definition at line 39 of file TwoStackQueue.java.

T listAlgorithms.TwoStackQueue< T extends Comparable< T > >.dequeue

(

)

dequeue a value

Returns:

the (logical) tail value of the queue

Definition at line 72 of file TwoStackQueue.java.

void listAlgorithms.TwoStackQueue< T extends Comparable< T > >.enqueue

(

T

val

)

Enqueue a value

Parameters:

val

Definition at line 56 of file TwoStackQueue.java.

T listAlgorithms.TwoStackQueue< T extends Comparable< T > >.peek

(

)

Definition at line 62 of file TwoStackQueue.java.

---

The documentation for this class was generated from the following file:

• listAlgorithms/TwoStackQueue.java