0
$\begingroup$

Is there any literature / research on the average size efficiency of stacks vs queues? I asked because I was recently working on a problem where, if using a queue, the size quickly blew up and the computer ran out of memory. If I used a stack the size stayed very small.

I think the reason in this case was that the search space was wide but shallow, which depth-first or LIFO optimal. I imagine that if it were narrow but deep a queue would have worked better.

Update: The algorithm was basically counting the number of palindromes which are substrings of a given string. My algorithm worked from the outside, pairing off letters and then sending the rest of the string back onto a stack/queue to be paired again.

Say there are 50 letters in the string, and 3 are already processed. The number of possible substrings with 47 digits is 2^47, so if I push these all to the queue before processing the next digit it blows up. But the stack would not push all 2^47 before processing the next string with 46 unprocessed, etc.

It comes back to what I said before about the size of the search space being much wider than it is deep - in this case the width is 2^50 and the depth is 50. So the stack is much more efficient. I just was wondering if there are any proven results related to this.

Update 2: At long last, here is the example I am referring to. Consider the following procedure to count the number of palindromes meeting a certain criteria:

int c = 0;
var PalStruct = new Struct<string>();
PalStruct.Add("00000");  // number of zeros tells how long palindromes to count are

while (!PalStruct.isEmpty()) {
  var nextString = PalStruct.Remove(); // ie Pop() if stack
  var nextPos = nextZero(nextString);  // returns next zero index from left, -1 if none
  if (nextPos==-1) {
    if MeetsCriteria(nextString) c++;
  }
  else {
    foreach  (char x in alphabet) {
      var sb = new StringBuilder(nextString);
      sb[nextPos] = x;
      sb[nextString.Length-1-nextPos] = x;      
      PalStruct.Add(sb.ToString()); // ie Push() if stack
    }
  }
}

// c is result

So here is the thing: if Struct is a stack, then the maximum size of the structure will be O(L), where L is the length of the palindrome. If Struct is queue, however, the maximum size of the structure will be O(a^L), where a is the size of the alphabet.

$\endgroup$
  • 2
    $\begingroup$ You must have been doing something wrong. $\endgroup$ – gnasher729 Aug 2 '17 at 20:18
  • 4
    $\begingroup$ @gnasher729 Why? Consider the standard tree search algorithm: "Get next node from the active set. If it's not the node you seek, put all its children in the active set. Repeat until you succeed or run out of nodes." If you implement the active set as a queue, this is BFS; if you implement it as a stack, it's DFS. Everybody knows that BFS and DFS can have wildly different memory requirements. $\endgroup$ – David Richerby Aug 2 '17 at 20:25
  • 1
    $\begingroup$ What do you mean, versus? The two data structures solve very different problems. $\endgroup$ – Raphael Aug 2 '17 at 20:26
  • 2
    $\begingroup$ There is no answer to your question, because the issue is not the efficiency of stacks vs queues in general (which isn't a well-defined notion) but rather the efficiency of a particular algorithm if defined to use a stack vs its efficiency if defined to use a queue. Since you haven't told us what that algorithm is, this question isn't answerable in its current form. If you'd like to make this answerable, I suggest you ask about a specific algorithm (and tell us which algorithm you have in mind). Can you edit the question to address these points? $\endgroup$ – D.W. Aug 2 '17 at 20:33
  • $\begingroup$ It's the algorithm, not the data structure. $\endgroup$ – xuq01 Aug 2 '17 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.